Augmenting Operations Research with Auto-Formulation of Optimization Models From Problem Descriptions (2022)

Abstract: We describe an augmented intelligence system for simplifying and enhancing the modeling experience for operations research. Using this system, the user receives a suggested formulation of an optimization problem based on its description. To facilitate this process, we build an intuitive user interface system that enables the users to validate and edit the suggestions. We investigate controlled generation techniques to obtain an automatic suggestion of formulation. Then, we evaluate their effectiveness with a newly created dataset of linear programming problems drawn from various application domains.

## introduction many real-world decision-making problems can be formulated and solved as mathematical optimization problems. the field of operations research (or) has seen success in applications ranging from increasing bike-share ridership and efficiency @xcite , managing wastewater collection and treatment systems @xcite , to finding a revenue-maximizing pricing strategy @xcite . in fact, optimization solvers can tackle different types of problems as they are powered by efficient algorithms such as the simplex method @xcite or interior-point methods @xcite . however, modeling a problem into a proper formulation is a complex and time-consuming process. first, a domain expert must describe the problem and identify its variables, parameters, objective and constraints. then, an or expert needs to translate this problem description into a precise formulation using a modeling language, thus making the process inefficient and limits the accessibility of the solvers to non-experts @xcite . we propose an augmented intelligence system to simplify and enhance the modeling process. we partially automate the process using nlp models to suggest a formulation that the users can validate or edit the suggestions using an intuitive interface. partial automation avoids the manual writing of the formulation by using a modeling language, thereby reducing the time and expertise to build optimization models. the intuitive interface also makes solvers more accessible to non-technical users. from an nlp perspective, there are many challenges to parsing an optimization problem's formulation from its natural language description: in this paper, we describe the underlying system that addresses these challenges and that enables the augmented modeling application. our contributions are: semantic parsing and generation. semantic parsing maps natural language utterances into a machine-interpretable representation @xcite . this mapping has been extensively studied for output representations such as sql queries @xcite , unix commands @xcite , or logical forms for querying a knowledge base @xcite . we tackle a different and challenging semantic parsing task as explained in section 1. building on the success of attention models in sequence-to-sequence tasks @xcite , encoder-decoder architectures have been adopted for designing semantic parsers @xcite @xcite . we propose using an intermediate representation (ir) that serves as a bridge between natural language and the canonical output format. our twostage mapping strategy is different from @xcite , which initially generates a sketch of the query and then fills out the slots. in contrast to prior methods of constrained decoding @xcite , our approach uses a simple beam search and leverages a promptguided generation and copying mechanism to guide the decoding. ## augmented modeling interface we present an interactive system that enables users to model an optimization problem in collaboration with an ai system. to use this application, the user first describes the problem using natural language. then, the system will suggest to the user the formulation of the optimization model including the decision variables, objective, and problem constraints. the system suggests the components of the formulation one at a time allowing the users to accept, reject, or edit the suggestions. an example scenario of a portfolio optimization problem is shown in figure 1 . here, the system suggested the formulation of a balance constraint given the description "savings should not exceed 60% of her total investment". had the system presented an incorrect formulation (e.g. an upper bound constraint), the user can change the type using the interface and the system reformulates the constraint expression automatically. the user can also edit the description, which will be stored as metadata of the model. in the same fashion, the user can add variables or constraints manually or edit the problem description to update the model. when the user is satisfied with the formulation, the system forwards it to an optimization solver, which then returns either an optimal solution of the problem to the user or warnings for some infeasible constraints. figure 2 shows an overview of the underlying auto-formulation system. it consists of an entity tagger, a formulation generator, and an augmented modeling interface. given a problem description, the entity tagger labels the keywords that indicate the components of the optimization problem. for example, "return" and "at least" are tagged as an objective name and constraint direction, respectively. then, the formulation generator uses the text description and the corresponding tagged entities to generate the formulation suggestions, which are then presented to the user by the augmented modeling interface. in our implementation (experimental settings in the appendix), we used an xlm-roberta pre-trained transformer and fine-tuned it for entity recognition using the dataset described in section 5.2. ## optgen: controllable generation of optimization formulation here, we present the methods behind our model optgen, for generating the suggested formulation. ## conclusion we introduced an augmented modeling platform, in which users enter the descriptions of optimization problems and interact with an ai system to efficiently model their formulations. to this end, we described the underlying system for this emerging application and proposed controllable generation methods to enable it. we also created a training dataset of linear programming word problems to evaluate the effectiveness of the proposed methods. our findings showed that the design of generation models and methods can have significant impact on the accuracy of the system's suggested formula-tions and that the system should help the users to validate and edit the suggestions.