- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper is part of a line of work that studies how to use LLMs for the automated formulation of mixed-integer linear programs (MILPs) – that is, methods that translate a natural language description of an optimization problem into a MILP. An important component of this pipeline is verification: given a benchmark’s gold-standard MILP formulation and an AI-generated MILP formulation, how do we determine whether the two MILP formulations represent the same problem? This task is not straightforward because there are many different ways to formulate the same optimization problem (e.g., by adding slack variables, cutting planes, etc.).
This paper proposes a method to determine whether two input formulations represent the same problem. First, it uses an LLM to determine, for each formulation, which decision variables are “auxiliary” (e.g., slack variables) and which are not—i.e., the “business” variables. The business variables must be shared between the two formulations. It then uses various substitution and elimination techniques to project the two formulations onto the business variables. Finally, it defines another pair of integer programs to determine whether the two formulations’ projected feasible regions are equal. The experiments show that the method has 100% accuracy on all tested reformulations, beating the most similar baseline EquivaMap (Zhai et al., ’25) on transformations that change the MILP’s feasible region but not its optimal solution.
Critical strengths
- I think it’s conceivable that follow-up work would build on this approach. The research community and industry have paid fair attention to automated MILP formulation in recent years. The most common techniques for evaluating model equivalence, such as solving both models and comparing their optimal objective values, have clear, straightforward failure cases. Better evaluation methods, such as Opt-Judger, are needed.
- This paper provides a decent conceptual advancement over EquivaMap. For large MILPs, one may not be able to solve to optimality, so it seems important to ensure that, if two MILPs are meant to be reformulations of each other, nearly optimal solutions to one don’t correspond to infeasible solutions to the other.
- The paper provides a new benchmark dataset in addition to its new method.
Critical weaknesses
- It would be helpful to provide some limitations of the method. For example, are there types of reformulations that wouldn’t be captured by this method? Are there examples of MILP reformulations that don’t have the same set of business variables?
- It would be helpful to clarify what the technical advances are in this paper, or if the advances are largely conceptual. Were there any technical challenges? Or are the techniques in Sections 4.2 or 4.4 largely straightforward from prior work?
- The writing is fine, and the paper was largely easy to read. I just have a few suggestions:
- The introduction could use a second pass. For example, the sentence “Our insight is that constraints determine which decisions a model permits” is not really pointing out an insight---it’s just stating the definition of a constraint.
- The term “business variable” was used several times before it was defined, and I didn’t know what it meant.
Questions for authors
Please see my questions in the "Critical Weaknesses" section.
Reminder: Please Engage in the Rebuttal Discussion
Dear Reviewers,
The rebuttal period is already halfway through, and the authors have submitted their responses. We kindly ask you to review the responses and engage in the discussion with the authors as soon as possible.
Thank you for your time and contribution.
Best regards, Area Chair