- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper is part of the recent line of research that aims to use LLMs for automated modeling of mathematical optimization problems---specifically linear programs and mixed integer linear programs. The benchmarks for these problems, such as NLP4LP, OptiBench, etc., typically consist of a natural language description of the problem, a mathematical formulation or “written mathematics” (the paper never spells out what exactly this means, but I presume it refers to a LaTeX formulation, for example?), and solver code. It’s important that these three elements all represent the same underlying optimization problem. This paper aims to use an SMT-based verification to diagnose mismatches between these three types of representations and then repair these representations using feedback from the diagnoses. The experiments apparently uncover many such mismatches (e.g., a match rate of 43% across 3034 problems), and the repair step repairs them (increasing the match rate to 88%).
Critical strengths
I have not seen SMT solvers used in the context of automated MILP formulation, so the paper introduces a novel method for an important problem. The problem itself is important because using LLMs for automated math optimization modeling is becoming an increasingly important approach in industry, and many benchmarks have been developed, as illustrated by Table 1. It’s important that these benchmarks are accurate (i.e., that the natural language descriptions and solver code represent the same problem).
Critical weaknesses
- I have been working on ML for integer programming for almost ten years, so I would expect a paper like this to be extremely easy for me to read and understand. On the contrary, I found much of it to be inscrutable. For example:
- Undefined mathematical notation or terms:
- Line 113: What is ?
- Line 240: What is ? What is an applicability condition and a logical obligation? Examples would help immensely.
- Line 261: What do you mean by reported coordinates?
- Line 279: What are and ? You say they’re “defined above,” but I don’t know what you’re referring to.
- Line 365: The table reports “Redundant constraint on this side only” and “Constraint absent from the other side.” What do “this side” and “the other side” refer to?
- Descriptions of methods that are far too high-level:
- Line 149: “The translator lowers admitted mathematical formulation into the model representation defined in Section 3.” What does it mean to “lower” a mathematical formulation into a model representation? How does the translator work---i.e., what is the underlying methodology? How do we know that the mathematical representation is faithful to the original formulation?
- Line 188: “The normalization may make implicit domains explicit and derive redundant constraints and auxiliary definitions needed for compilation, while preserving the semantic model objects used for verification.” How does the normalization operator work---i.e., what is the underlying methodology? What does it mean to derive redundant constraints and auxiliary definitions? How does it preserve the semantic model objects?
- Line 249: “Row entailment applies the same violation test to individual mathematical and executable restrictions. A written row violated by an implemented decision is missing from the implementation.” I have no idea what these two sentences mean.
- Sloppy writing:
- Line 206: Why aren’t you using the LaTeX proposition environment?
- Undefined mathematical notation or terms:
- Although the use of SMT solvers seems novel in this context, I walk away with almost no understanding of why SMT solvers are the right tool for this problem and what key challenges the authors faced and overcame for their application in this context.
Questions for authors
Unfortunately, this paper would need a complete rewrite before I'd change my assessment.
2 comments
- Line 249: Row entailment (revised lines 295–298). Thank you for pointing out that this description was unclear. We now explain a row as an individual constraint and state both checking directions in Section 5.2. For a constraint c of the mathematical model A over corresponding decision variables, ORSMT checks whether the instantiated solver model B admits a decision violating c. SAT supplies such a decision and identifies the constraint not enforced by B. UNSAT establishes that B implies c, even if it implements the restriction through different constraints. Conversely, testing a constraint of B against A identifies an additional restriction imposed by the implementation. These checks locate the specific constraint responsible for a disagreement and supply the counterexample used for revision.
Writing and proposition formatting
- Line 206: Proposition environment (revised lines 346–349). Thank you for pointing this out. Certified adoption is now presented using a numbered proposition environment. Proposition 1 in Section 5.4 states that adoption requires all policy checks to pass and that the original artifacts are retained when no candidate is adopted.
Why SMT is suitable and which challenges are addressed
Thank you for raising this question. LLM checking can miss a violated constraint, mistake an equivalent formulation for an error, or generate an explanation unsupported by the models. Repeated LLM review also adds generation cost without establishing whether the required relation holds. SMT addresses these problems by checking the relation itself. For optimization models, domains and constraints define feasible decisions, and objectives define their preferences. A query asks whether these decisions or preferences violate the relation being checked. SAT returns a concrete counterexample, which ORSMT traces to the implicated constraints or domains and their recorded source links. UNSAT certifies the checked relation. For these violation queries, the diagnosis is supported by a checkable assignment and acceptance by a formal check. The checks require no LLM generation and can be repeated efficiently after revision.
The difficulty is to compare the mathematical model with the model actually constructed by code, despite differences in syntax, redundant constraints, and auxiliary variables. ORSMT captures the instantiated solver model, aligns decision variables, and projects out auxiliary variables. Reconstruction preserves feasible decisions and objective preferences, and query reduction preserves the checked relations. These steps allow the counterexample to identify a specific problem for revision and the same verifier to check whether it has been resolved. This is the advantage of using SMT for both diagnosis and verification before adoption, as described in Sections 5.1–5.4.
Thank you for the detailed comments and for recognizing the value of applying SMT to optimization modeling. We have rewritten the problem setting and method sections and added a short SMT background. Below we follow the organization of your comments. Original line numbers identify your comments, and the corresponding revised line numbers are given in parentheses.
Undefined mathematical notation or terms
Line 113: Runtime extraction (revised lines 140–145 and 234–238). The extraction operator H executes the solver program P^ and captures the variables, constraints, and objective constructed at the solver call. Its output is the instantiated solver model B=H(P^). Written mathematics means the mathematical formulation M, expressed as equations or structured declarations, which is translated into A=L(M). Section 4 and Figure 2 make this distinction explicit.
Line 240: Applicability conditions and logical obligations (revised lines 154–156 and 276–281). Here k indexes a formal requirement. In (gk,ψk,Sk), gk specifies when the requirement applies, ψk states what must hold, and Sk identifies the supporting source text. For example, if an active facility must have positive capacity, the applicability condition is that the facility is active and the obligation is that its capacity is positive. A violation satisfies gk but not ψk. Definition 1 and Eq. (8) now state these roles explicitly.
Line 261: Reported coordinates (revised lines 282–289). We mean the decision variables whose values appear in the solver report. The set O indexes these variables. Other variables may be unreported, so Eq. (9) checks whether the reported values can be extended to a feasible assignment of the instantiated solver model. Section 5.2 now uses the term reported decision variables.
Line 279: Variable domains and constraint sets (revised lines 295–303). DA collects variable domains and bounds, while KA contains the constraints of the mathematical model A. In Eq. (11), we retain DA and all constraints except the one being tested, then ask whether that constraint can be violated. This establishes whether it is redundant. Section 5.2 defines both sets at their use.
Line 365: The two model sides (revised lines 390–395, Table 2). The two sides are the mathematical model A and the instantiated solver model B. We now name them explicitly in the table. The redundancy row counts constraints redundant only within the named model. The non-implication row counts constraints of that model that are not implied by the other model.
Descriptions of methods
Line 149: Translation methodology and fidelity (revised lines 140–149, 215–216 and 232–233). Thank you for asking how translation is performed and checked. We have replaced the term lowering with an explicit description of translation in Section 5.1. The translator reads the formulation M into the mathematical model A, recording decision and auxiliary variables, domains, constraints, the objective, and its optimization direction. Structured declarations are parsed directly. For mathematical text, an LLM supplies declarations that undergo the same parsing checks. The parser checks unique variable names and resolved references and stores finite decimal coefficients as exact rationals. Appendix A.2 specifies the supported formats, and Figure 2 shows the translation on an example. The original formulation is retained for inspecting the transcription, while requirements extracted from the problem statement are checked separately against A.
Line 188: Normalization and semantic preservation (revised lines 240–247 and 298–303). Thank you for highlighting the need to explain semantic preservation. The revised Section 5.1 specifies normalization as removal of constraints proved redundant. For each constraint, ORSMT retains the variable domains and other constraints and asks whether the selected constraint can be violated. UNSAT establishes that the remaining model already implies it, permitting removal. Each subsequent removal is tested against the constraints still retained. Before construction, ORSMT checks that normalization preserves both the feasible decisions and the pairs of decisions and objective values, after projecting out auxiliary variables. These are the two preservation conditions stated in Section 5.1 and justified in Appendix B.3.