PaperlayerView exact revision on arXiv

Source-linked AI summary

Diagnosing Infeasible Optimization Problems Using Large Language Models

Hao Chen, Gonzalo E. Constante-Flores, Can Li

arXiv:2308.12923v1cs.HCcs.CLcs.LGmath.OC

TL;DR

Practitioners without optimization expertise can struggle to diagnose infeasible models, while existing expert systems require domain knowledge. OptiChat combines GPT-4, a solver, and prompting techniques for natural-language model analysis and troubleshooting; study passages report positive user assessments and high accuracy across two metrics.

  • Problem

    Practitioners with limited mathematical-programming knowledge may struggle to identify infeasibility causes and take corrective action, while expert systems require optimization background.

    Source: Introduction · p. 2

  • Method

    OptiChat combines GPT-4 natural-language interaction with an optimization solver to analyze infeasibility and support model changes, using several prompting techniques.

    Source: Introduction · p. 2, Method · p. 3

  • Results

    Survey response modes were generally somewhat to strongly agree, and Table 3 reports high accuracy for satisfactory answers and troubleshooting success across study groups.

    Source: Quantitative Results · p. 7

  • Takeaways & Limitations

    A participant reported that OptiChat provided understandable explanations and systematic model understanding, with accurate first-round recommendations for a single parameter change.

    Source: Qualitative Results · p. 7

    Changing left-hand-side parameters can make repair a more expensive nonconvex MIQCP, and such parameters often represent physical properties that are difficult to change.

    Source: Resolving Infeasibility · p. 5

Abstract

from arXiv · show

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.

Introduction

Infeasible optimization models are difficult for practitioners without optimization expertise to diagnose, while existing expert systems require substantial domain knowledge. OptiChat uses natural-language interaction, a solver, and prompting techniques to explain models, identify infeasibility sources, and support repairs.

Introduction

  • An IIS is a minimal infeasible subset of constraints or variable bounds; every proper subset is feasible.This isolates the core conflicting constraints for diagnosis.Source: Introduction · p. 1, Figure 2 · p. 2
  • Practitioners with limited mathematical-programming knowledge may treat models as black boxes, limiting their ability to find infeasibility causes and take corrective action.Optimization experts can gain insight from the IIS.Source: Introduction · pp. 1–2
  • Existing expert systems require optimization background, while the authors report that a natural-language system for optimization models had not been developed to their knowledge.They connect the opportunity to recent large language models.Source: Introduction · p. 2
  • OptiChat combines a natural-language chatbot with an optimization solver to explain models, identify infeasibility sources, and adjust parameters to restore feasibility.The system uses GPT-4 and responds to user questions and feedback.Source: Introduction · p. 2
  • OptiChat combines few-shot learning, expert chain-of-thought, sentiment prompting, and key-retrieve prompting to improve reliability.Key-retrieve is proposed as an additional prompting technique.Source: Introduction · p. 2

Related Works

Prior work includes solver-based IIS isolation, expert systems and modeling platforms, and natural-language dialogue systems for machine-learning explanations. Prompt engineering offers techniques for directing LLM behavior without changing model weights.

Algorithms for Isolating IIS Constraints

  • A deletion filter can isolate an IIS by tentatively dropping constraints, restoring a constraint if the resulting model is feasible, and otherwise keeping it out.One pass over the constraints is guaranteed to find an IIS; commercial solvers also implement IIS methods.Source: Algorithms for Isolating IIS Constraints · p. 2

Expert Systems for Optimization Models

  • Expert systems and modeling platforms support optimization analysis, but their programming-like syntax requires users to know both optimization and programming.The related work names ANALYZE, AMPL, AIMMS, GAMS, Pyomo, and JuMP.Source: Expert Systems for Optimization Models · p. 2

Natural Language Dialogue Systems for Machine Learning Models

  • Machine-learning dialogue systems explain how input changes may affect outputs, but prior designs address specific contexts and lack flexibility.TalkToModel combines LLMs with external tools such as counterfactual explanations.Source: Natural Language Dialogue Systems for… · pp. 2–3

Prompt Engineering

  • Few-shot learning supplies example inputs and expected outputs, while chain-of-thought prompting elicits concise reasoning steps before an answer.Prompt engineering directs LLM behavior without altering model weights.Source: Prompt Engineering · p. 3

Method

OptiChat is an interactive, natural-language system for non-experts that coordinates an optimization model, solver, and LLM. It describes models, analyzes infeasibility, recommends feasibility changes, and answers follow-up questions.

Method

  • OptiChat coordinates the user, optimization model, solver, and LLM, with the LLM interpreting the model and conversation and deciding when to use the solver.The solver can obtain a solution status, retrieve an IIS, and solve with adjusted parameters.Source: Method · pp. 3–4
  • The system supports contextual model descriptions, infeasibility analysis, feasibility recommendations, and interactive answers to follow-up questions.Users can ask questions and make natural-language requests without needing to write code, as described in Figure 1.Source: Method · pp. 3–4

Illustrative Conversations with OptiChat

An on-the-job training example illustrates OptiChat’s workflow: it describes an infeasible model, explains its causes, recommends ways to regain feasibility, and supports further questions.

Illustrative Conversations with OptiChat

  • In the on-the-job training example, OptiChat explains the infeasible model, diagnoses causes, recommends measures to restore feasibility, and answers follow-up questions.Users can also request model-data changes to find feasible solutions.Source: Illustrative Conversations with OptiChat · p. 4

Usage of the Optimization Model and Solver

OptiChat combines an optimization model, solver, and LLM to help diagnose infeasibility and restore feasibility. It computes IISs and favors parameter adjustments with slack variables over removing constraints.

Usage of the Optimization Model and Solver

  • Experts inspect the model, compute an IIS to identify conflicting constraints, then restore feasibility by removing constraints or adding slack variables.OptiChat relies on the optimization model and solver because the LLM alone cannot provide an end-to-end infeasibility diagnosis.Source: Usage of the Optimization Model and… · p. 4

Computing IIS

  • For linear programs, supports of vertices of P give IISs, so enumerating IISs is equivalent to enumerating vertices; mixed-integer programs require logic-based methods.The Farkas’ lemma argument applies to linear programs, not mixed-integer linear programs.Source: Computing IIS · p. 4

Resolving Infeasibility

  • OptiChat restores feasibility by adding slack variables to model parameters rather than removing IIS constraints, which may be impractical in real-world applications.The slack approach can give decision-makers a concrete plan for making the model feasible.Source: Resolving Infeasibility · p. 4
  • Nonnegative slacks perturb selected entries of A or b, and the objective minimizes their total perturbation; selection depends on LLM judgment and user requests.Different slack weights could represent the costs of changing corresponding parameters.Source: Resolving Infeasibility · p. 5
  • With no A-parameter perturbations, recovery remains an MILP solvable as fast as the original; allowing A changes creates a more costly nonconvex MIQCP.OptiChat therefore avoids recommending changes to left-hand-side parameters unless users insist, since many correspond to physical properties that are difficult to change.Source: Resolving Infeasibility · p. 5

Implementation and LLM Prompt Engineering

OptiChat uses GPT-4 with expert-guided and task-specific prompts to analyze models, diagnose infeasibility, recommend adjustments, and converse with users. Its prompts combine model information with solver outputs and user feedback.

Implementation and LLM Prompt Engineering

  • OptiChat’s four task areas are model analysis, infeasibility diagnosis, troubleshooting recommendations, and interactive conversation.The prompting techniques are applied across these four tasks.Source: Implementation and LLM Prompt… · p. 5
  • Expert chain-of-thought supplies step-by-step expert procedures, while few-shot prompting provides simple optimization examples with expert answers.Examples include traveling-salesman and knapsack problems.Source: Implementation and LLM Prompt… · p. 5, Model analysis · p. 5

Model analysis

  • Key-retrieve extracts parameter and constraint names from Pyomo code and requires the LLM to retrieve them before acting, reducing mismatches and misidentification versus direct code summarization.The authors report this empirical comparison without giving a numerical effect size here.Source: Model analysis · p. 5
  • For model analysis, the LLM follows an expert sequence: overview, input parameters, decisions, then constraints.Few-shot demonstrations of traveling-salesman and knapsack problems accompany the expert steps.Source: Model analysis · p. 5

Infeasibility Diagnosis

  • For infeasibility diagnosis, Gurobi returns IIS constraints numerically; OptiChat maps them back to symbolic form and prompts the LLM to explain the conflicts.Expert chain-of-thought, few-shot, and key-retrieve prompts support this task.Source: Infeasibility Diagnosis · p. 5

Troubleshoot Recommendation

  • Troubleshooting recommendations weigh real-world adjustability and cost while avoiding left-hand-side changes that would turn the model into an MIQCP.The prompt examples distinguish adjustable storage-vessel capacity from an unchangeable number of hours in a day.Source: Troubleshoot Recommendation · p. 5

Interactive Conversation

  • During conversation, sentiment prompting lets OptiChat warn users about consequences without prohibiting requested changes; confirmed parameters alone are adjusted in the solver call.Users can accept or reject initial recommendations and request changes OptiChat would not initially recommend.Source: Interactive Conversation · pp. 5–6

Experiments

The study evaluates OptiChat with users of differing optimization experience, using troubleshooting tasks and surveys to assess model understanding, response quality, and repair. Participants reported positive experiences, while experienced users described repair strategies that can be time-consuming and error-prone.

Experiments

Dataset preparation

  • The test set contained 63 infeasible instances created by changing parameters or adding constraints to models drawn from several libraries and application areas.The source models included aircraft allocation, production scheduling, power generation, oil refining, ship allocation, and military manpower planning.Source: Dataset preparation · p. 6

Infeasiblity Troubleshooting Assessment

  • Experienced users repaired 38 instances using IIS verification, constraint activation or deactivation, and slack-variable relaxation; the latter two strategies can be error-prone and time-consuming.Model size can increase repair time even for experienced users, and most users spent 15–30 minutes analyzing a model.Source: Infeasiblity Troubleshooting Assessment · p. 6

Quantitative Results

  • Both user groups rated OptiChat’s responses mostly from somewhat agree to strongly agree, and Table 3 reports high accuracy for chatbot answers and troubleshooting success.Experienced users’ modal response was neutral on how easy it was to correct chatbot misunderstandings and errors.Source: Quantitative Results · p. 7, Table 3 · p. 7

Qualitative Results

  • Participants described OptiChat’s explanations as accessible to people with limited optimization background and highlighted systematic understanding and the ability to repair models after an initial recommendation.The paper attributes systematic understanding to chain-of-thought and few-shot prompting.Source: Qualitative Results · p. 7
  • Participants gave positive feedback on OptiChat’s clear, structured, insightful, and timely responses, and suggested tailoring explanations of models and infeasibility to users’ expertise.One participant praised explanations of parameters and their implications for real-life feasibility.Source: Qualitative Results · p. 7

Conclusions

The paper presents OptiChat, an LLM-powered agent for natural-language analysis and troubleshooting of infeasible optimization models. It combines prompting techniques with solver interaction and supports linear and mixed-integer linear optimization problems.

Conclusions

  • OptiChat uses natural-language interactions to help non-experts analyze and troubleshoot infeasible optimization models.The system is an LLM-powered agent.Source: Conclusions · p. 7
  • Its prompting approach combines expert chain-of-thought, few-shot learning, sentiment prompting, and key-retrieve, which extracts parameter and constraint names from model scripts.The paper describes key-retrieve as a technique to improve reliability.Source: Conclusions · p. 7
  • GPT-4 function calling connects OptiChat to optimization solvers, and the chatbot supports linear and mixed-integer linear problems across applications including finance, logistics, and critical infrastructure.Source: Conclusions · p. 7

Related papers

Loading 2308.12923v1…