- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the equivalence of mixed-integer linear programming (MILP) formulations and proposes a behavioral evaluation criterion based on observational equivalence. The proposed criterion focuses on preserving optimal solution sets and optimal objective values across problem parameters. The paper also introduces a sketch-and-prove framework for constructing machine-checkable equivalence certificates in Lean. To evaluate the proposed approach, the authors construct MILP-EquivalBench. Experiments on this benchmark and 54 pairs from FormulationBench show that the proposed method achieves higher reported accuracy than the compared baselines.
Critical strengths
Please identify one or two critical strengths of the paper that support acceptance. For each, explain briefly why it is consequential to your overall assessment. The goal is not to enumerate every positive point, but to identify and substantiate the considerations that most strongly determine your recommendation. Enter “None” if no substantive strength can be identified.
-
A meaningful extension of existing MILP formulation equivalence criteria. The paper introduces observational equivalence as a more flexible criterion for evaluating MILP formulations. Compared with FLARE's constructive reformulation criterion, the proposed approach allows transformations that modify the feasible region while preserving optimal behavior.
-
Integration of behavioral equivalence with machine-checkable formal verification. The paper combines the proposed criterion with a sketch-and-prove framework for generating Lean certificates. The use of informal proof planning, formal proof sketches, and subproblem decomposition provides a structured approach to automated verification.
Critical weaknesses
Please identify one or two critical weaknesses of the paper that support rejection. For each, explain briefly why it is consequential to your overall assessment. The goal is not to enumerate every negative point, but to identify and substantiate the considerations that most strongly determine your recommendation. Enter “None” if no material weakness can be identified.
-
The experimental evaluation covers only 189 formulation pairs, including 135 pairs from the newly constructed MILP-EquivalBench and 54 pairs from FormulationBench. More importantly, MILP-EquivalBench is generated by applying the same nine predefined transformations to 15 reference formulations. This controlled construction is useful for examining representative equivalence relations, but may not adequately reflect the diversity and complexity of real-world MILP reformulations.
-
The ablation results in Table 4 further raise concerns about the benchmark's ability to evaluate the proposed proof framework. On MILP-EquivalBench, removing the informal planning component still achieves 100% accuracy, while the single-session proof variant achieves 99.8%. The authors acknowledge that this benchmark is designed primarily to assess equivalence across representative transformations rather than challenging proof synthesis. Consequently, the near-perfect performance on this benchmark provides limited evidence for the necessity and robustness of the complete sketch-and-prove framework.
-
The paper does not provide a systematic analysis of formulation size, proof difficulty, or verification efficiency. Without additional experiments on more diverse and challenging formulations, it is difficult to assess how well the proposed approach generalizes or scales to practical applications. Evaluation on independently sourced MILP models , potentially including suitably constructed reformulation pairs derived from MIPLIB(https://miplib.zib.de/), would strengthen the empirical evidence.
Questions for authors
Q: Benchmark size, formulation complexity, and scalability. The evaluation includes only 189 formulation pairs. Could the authors report the distributions of variable counts, constraint counts, integer and continuous variables, and proof complexity across the benchmarks? Have the authors evaluated the method on larger or more realistic MILP formulations?
2 comments
The ablation results in Table 4 further raise concerns about the benchmark's ability to evaluate the proposed proof framework. ...
The ablation results on FormulationBench in Table 4 demonstrate the contributions of informal planning and proof sketches with subproblem decomposition. The complete framework achieves 99.4% accuracy, which decreases to 95.1% without informal planning and 93.2% with single-session proof. The corresponding number of false negatives increases from 1 to 8 and 11, respectively, indicating that removing these components makes the system more likely to fail to complete formal proofs for equivalent formulation pairs.
We adapt the planning, sketching, and decomposition workflow from mathematical theorem proving to optimization formulation equivalence verification, organizing each stage around the construction of equivalence certificates. Each component serves a distinct role: informal planning identifies mappings between parameters, variables, and objective values and develops the overall proof strategy; the formal proof sketch translates this strategy into a structured Lean proof skeleton. Subproblem decomposition splits unresolved proof obligations into subgoals, allowing the proof process to focus on individual goals before assembling and checking the complete certificate. Together, these components improve the completion rate of challenging proof tasks, as directly supported by the ablation results on FormulationBench.
Meanwhile, the primary design objective of MILP-EquivalBench is to expose limitations of existing criteria for evaluating optimization model equivalence. We construct representative transformations at the variable, constraint, and objective levels to systematically examine whether different evaluation criteria correctly assess equivalence under these structural changes. Thus, MILP-EquivalBench primarily demonstrates the value of the observational-equivalence criterion, while the ablation results on FormulationBench further demonstrate how the proof framework’s components contribute to completing challenging formal proofs.
The paper does not provide a systematic analysis of formulation size, proof difficulty, or verification efficiency. ... Q: Benchmark size, formulation complexity, and scalability.
Figures 3 and 4 in Appendix E.1 report formulation sizes and variable-count distributions across the four benchmarks. Table 7 summarizes the numbers of formulations by variable type, as reproduced below.
| Dataset | LP | ILP | MILP |
|---|---|---|---|
| MILP-EquivalBench | 60 | 80 | 10 |
| FormulationBench | 4 | 33 | 33 |
| EquivaFormulation | 29 | 100 | 7 |
| MIPLIB-NL | 0 | 11 | 27 |
Figures 3 and 4 show that MILP-EquivalBench and the supplementary dataset constructed from MIPLIB-NL cover a broader range of formulation sizes than the other evaluated datasets, spanning small formulations and substantially larger models. This size coverage is complemented by the representative transformations in MILP-EquivalBench and the additional models and transformation rules in our supplementary evaluations, enriching the diversity of formulations and transformations considered.
Our method verifies equivalence between abstract, parameterized optimization formulations without fixing the size of a particular instance. For example, a knapsack formulation is parameterized by the number of items , their weights and values , and the capacity , with decision variables and capacity constraint . Changing changes the number of decision variables and their associated domain restrictions, as well as the number of terms in the objective and capacity constraint. These instances are all described by the same parameterized formulation. The equivalence certificate establishes the required mappings and their properties for all admissible values of in the declared parameter domain. Thus, a single certificate covers instances of varying sizes, and our equivalence verification is not restricted to a fixed optimization model size.
We also report average runtime and cost for the main benchmarks in Table 11 of Appendix E.3, and for the supplementary evaluations in Tables 9 and 10 of Appendix E.2. All costs are computed from recorded token usage using the pricing listed in Table 12 of Appendix E.3. On the main benchmarks, the runtime and cost of OBEquival are in the same order of magnitude as those of FLARE. For further discussion of the computational overhead and the benefits of formal verification, please refer to our response to Reviewer nvfB's question about the cost of our method.
We sincerely thank you for reviewing our paper and providing us with valuable feedback. We have addressed your concerns as follows.
Thank you for highlighting the concerns about benchmark diversity and external validity. To the best of our knowledge, MILP-EquivalBench is among the most comprehensive benchmarks in terms of the range of formulation transformations it covers. It systematically reveals the main limitations of existing methods for assessing equivalence between optimization models.
MILP-EquivalBench is designed to systematically assess optimization model evaluation methods under different structural transformations. The nine transformation types span representative changes to variables, constraints, and objectives. They reflect common formulation modifications in optimization modeling and cover the major structural differences addressed by existing formulation-level evaluation work. These transformations expose limitations in how reliably existing methods assess model equivalence under diverse structural changes.
Our method is not limited to these nine transformation types. As long as a new transformation can be correctly formalized and its proof obligations can be discharged, the method can in principle assess transformations beyond the current set, including their compositions. To further evaluate its applicability, we added two evaluations based on EquivaFormulation and MIPLIB-NL in Appendix E.2. The selection and construction procedures are detailed in Appendix E.2.2. The results are reproduced below. ND denotes runs without a decision and is counted as incorrect.
EquivaFormulation
MIPLIB-NL
Excluding the overly simple and redundant cases in EquivaFormulation, our evaluation covers the vast majority of datasets used to assess optimization model equivalence. OBEquival ties FLARE for the highest accuracy on EquivaFormulation and outperforms the baseline methods on all other datasets, demonstrating that our method provides more accurate assessments of optimization model equivalence. In future work, we will develop more comprehensive benchmarks covering more complex formulations and transformations for evaluating optimization model equivalence.