Diagnosing Infeasible Optimization Problems Using Large Language Models
Hao Chen Gonzalo E. Constante-Flores Can Li
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. Optimization models are
mathematical abstractions of the problem of making the best decision while
satisfying a set of requirements or constraints. One of the primary barriers to
deploying these models in practice is the challenge of helping practitioners
understand and interpret such models, particularly when they are infeasible,
meaning no decision satisfies all the constraints. Existing methods for
diagnosing infeasible optimization models often rely on expert systems,
necessitating significant background knowledge in optimization. In this paper,
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 offer suggestions to make the model feasible. 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
experiments demonstrate that OptiChat assists both expert and non-expert users
in improving their understanding of the optimization models, enabling them to
quickly identify the sources of infeasibility.