(458a) Diagnosing Infeasible Optimization Problems Using Large Language Models

Optimization models are mathematical abstractions of the problem of making the best decision while satisfying a set of requirements or constraints. Decision-making problems can be represented as mathematical optimization models, finding wide applications in fields such as economics, engineering and manufacturing, transportation, and health care [1]. However, one of the primary barriers to deploying these models in practice is the challenge of conveying non-experts’ ideas to models or interpreting model responses to non-experts. Thus, these models remain less accessible to practitioners, stakeholders, and operators without a solid technical background who often treat these models as black boxes.

When formulating real-world decision-making problems into mathematical representations, a common challenge is the infeasibility of the initial model, meaning no decision satisfies all the constraints. This issue often arises because the problems intended to be modeled are too idealized, with overly strict constraints. Although the optimization community has developed different mathematical concepts to characterize infeasible optimization models [2-4], non-experts often struggle to diagnose the root causes and comprehend the significance of different corrective actions. To resolve this, a Human-Computer Interaction (HCI) system is needed to help humans diagnose infeasible optimization models. One of the pioneering efforts to develop an HCI tool is the ANALYZE system [5, 6]. However, existing methods, both ANALYZE and current commercial software, still rely on specific syntax and modeling languages that necessitate significant domain knowledge from non-experts.

In this work, we introduce OptiChat, a first-of-its-kind natural language-based system equipped with a chatbot GUI for engaging in interactive conversations about infeasible optimization models. OptiChat can provide natural language descriptions of the optimization model itself, identify potential sources of infeasibility, and explore corrective actions to restore feasibility through users’ queries, all without requiring non-expert users to interact with the code.

The implementation of OptiChat is built on GPT-4, which interfaces with an optimization solver to identify the minimal subset of constraints that render the entire optimization problem infeasible, also known as the Irreducible Infeasible Subset (IIS). We utilize few-shot learning, expert chain-of-thought, key-retrieve, and sentiment prompts to enhance OptiChat’s reliability. Our user experiments demonstrate that OptiChat assists both expert and non-expert users in improving their understanding of the optimization models, enabling them to efficiently identify the sources of infeasibility and complete troubleshooting.

[1] R. L. Rardin, Optimization in operations research. Prentice Hall Upper Saddle River, NJ, 1998.

[2] J. W. Chinneck and E. W. Dravnieks, "Locating minimal infeasible constraint sets in linear programs," ORSA Journal on Computing, vol. 3, no. 2, pp. 157-168, 1991.

[3] O. Guieu and J. W. Chinneck, "Analyzing infeasible mixed-integer and integer linear programs," INFORMS Journal on Computing, vol. 11, no. 1, pp. 63-77, 1999.

[4] J. W. Chinneck, Feasibility and Infeasibility in Optimization:: Algorithms and Computational Methods. Springer Science & Business Media, 2007.

[5] H. J. Greenberg, "Enhancements of ANALYZE: a computer-assisted analysis system for linear programming," ACM Transactions on Mathematical Software (TOMS), vol. 19, no. 2, pp. 233-256, 1993.

[6] H. Greenberg, "A functional description of ANALYZE: A computer-assisted analysis system for linear programming models," ACM Transactions on Mathematical Software (TOMS), vol. 9, no. 1, pp. 18-56, 1983.