acceptodds
Under review as a conference paper at ICLR 2027

Observational Equivalence for MILP Formulations: Behavioral Evaluation via Sketch-and-Prove Formal Verification

Abstract

Mixed-integer linear programming (MILP) formulations are widely used in scheduling, logistics, finance, and other domains. The same optimization problem can be represented by different formulations, which makes automatic correctness evaluation difficult. To evaluate formulation equivalence more appropriately, we propose a behavioral evaluation criterion for MILP formulations, which, building on the notion of observational equivalence, compares two formulations through their observable optimality outcomes under any problem parameter. We realize this criterion with a sketch-and-prove process that produces a proof certified by Lean. The process first constructs an informal plan and a formal proof sketch, and then automatically identifies the unproved goals and proves them one by one. Finally, we extend the benchmark for MILP formulation equivalence verification with nine classes of model transformations. Experiments show that our evaluation criterion overcomes key limitations of existing evaluation methods by assessing formulation correctness at the formulation level through the observable optimal outcomes. This makes the criterion suitable for the practical evaluation of both automatically optimization modelling and their subsequent transformations.

Primary area:
optimization
Keywords:
MILP formulation equivalence, formal verification, Lean, LLM agents

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9diKOpenReview ↗
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.

  1. 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.

  2. 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.

  1. 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.

  2. 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.

  3. 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

We sincerely thank you for reviewing our paper and providing us with valuable feedback. We have addressed your concerns as follows.

The experimental evaluation covers only 189 formulation pairs, ... This controlled construction is useful for examining representative equivalence relations, but may not adequately reflect the diversity and complexity of real-world MILP reformulations.

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

MethodTPFPTNFNNDPrecisionRecallAccuracy
Execution0213111000%–34.3%
ORGEval03321000%–99.1%
EquivaMap01411710120%–52.8%
FLARE0032400––100%
OBEquival0032400––100%

MIPLIB-NL

MethodTPFPTNFNNDPrecisionRecallAccuracy
Execution38002122100%46.9%46.9%
ORGEval0004140–0%0%
EquivaMap6000021100%74.1%74.1%
FLARE5900220100%72.8%72.8%
OBEquival810000100%100%100%

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.

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.

DatasetLPILPMILP
MILP-EquivalBench608010
FormulationBench43333
EquivaFormulation291007
MIPLIB-NL01127

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 nn, their weights wiw_i and values viv_i, and the capacity CC, with decision variables x∈{0,1}nx \in \{0,1\}^n and capacity constraint ∑i=1nwixi≤C\sum_{i=1}^{n} w_i x_i \leq C. Changing nn 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 nn 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.

Reviewer_PkAcOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a criterion to evaluate the equivalance of two MILP formulations. It then proposes a sketch-and-prove pipeline to use Lean to prove such equivalance.

Critical strengths

The studied promblem is very interesting. The authors try to give fine definitions to measure the equivalance of two MILP formulations.

Critical weaknesses
  • The relationship between the proposed criteria and the optimization reduction is not discussed sufficiently. For example, many MILPs can be reduced to MIS promblems. Are they equivalant under the proposed criteria? If not, the authors should give some more illustrations for the equivalant classes.
  • In my understanding, the authors add many sematic constraints on the parameter mapping, but this is not strictly formalized. Moreover, this leads to a gap between the practice in experiments and definition 2.
  • The proof framework is not just a standard practice and not noval at all. It is more like a benchmark for evaluating the capability of models rather than a new method.
Questions for authors

See weaknesses.

2 comments

We sincerely thank you for reviewing our paper and providing us with valuable feedback. We have addressed your concerns as follows.

The relationship between the proposed criteria and the optimization reduction is not discussed sufficiently. ...

In the optimization reduction notion of reformulation of Audet et al. [1], instances of one optimization problem are mapped to instances of another, whose optimal solutions can be converted in polynomial time into optimal solutions of the original problem. Our definition shares the idea of preserving optimal outcomes through mappings. Our criterion operates at the formulation level, requiring these correspondences to hold across all admissible parameter values.

As described in Section 3.1, our definition draws on observational equivalence in programming-language semantics, which compares different internal implementations through their externally observable behavior. For MILP formulations, we treat optimal solutions and optimal objective values as observable outcomes. We compare parameterized formulations over their entire admissible parameter domains, rather than two instances with fixed parameter values. The required correspondences must therefore hold for all matched instances within these domains.

Beyond the optimization reduction described above, we require both bidirectional mappings between optimal solutions and an explicit relationship between optimal objective values through a strictly increasing map. This allows order-preserving changes in the objective scale while requiring the same conversion across the entire parameter domain. Consequently, a reduction from MILP to MIS that also satisfies these conditions falls within our notion of observational equivalence.

In my understanding, the authors add many sematic constraints on the parameter mapping, but this is not strictly formalized. ...

We thank the reviewer for pointing out that the parameter mapping was not explained clearly enough. Definition 2 characterizes equivalence through the existence of a parameter mapping. In our experiments, we verify equivalence under a reference parameter mapping supplied with the task. This mapping specifies the semantic correspondence between the parameters of the two formulations, preventing the agent from choosing a mapping that deviates from the intended task semantics. For example, when the weight parameters in both formulations represent the weight of the same object, both measured in kilograms, the task requires C′=CC'=C, rather than an arbitrary mapping such as C′=1000CC'=1000C, which would change the meaning of the instances being compared. This setup is consistent with FLARE [2], which also performs verification under a given parameter mapping. We will clarify this experimental setup in Appendix C.

Reference

[1] Charles Audet, Pierre Hansen, Brigitte Jaumard, and Gilles Savard. “Links Between Linear Bilevel and Mixed 0–1 Programming Problems.” Journal of Optimization Theory and Applications, 93(2):273–300, 1997. doi:10.1023/A:1022645805569.

[2] Henry Robbins, Connor Lawless, Madeleine Udell, and Ellen Vitercik. “FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving.” arXiv preprint, arXiv:2608.25220, 2026.

The proof framework is not just a standard practice and not noval at all. It is more like a benchmark for evaluating the capability of models rather than a new method.

Our proof framework builds on the Draft, Sketch, and Prove (DSP) paradigm from automated formal theorem proving in mathematics, as explicitly acknowledged in Section 3.2. One methodological contribution of our work is to transfer this paradigm to observational-equivalence verification for parameterized MILP formulations and develop a proof procedure tailored to this task.

This transfer requires turning equivalence evaluation into explicit, machine-checkable mathematical proof obligations. We introduce a criterion that treats optimal solutions and optimal objective values as observable outcomes and formalize it in Lean. It provides a more appropriate basis for evaluating optimization formulations and their transformations. Under the supplied reference parameter mapping, the planning stage identifies variable and objective-value mappings and develops the proof strategy. The sketching stage organizes these mappings and the certificate conditions into a Lean proof skeleton. The proving stage extracts and individually discharges the remaining problems. This task-specific transfer, adaptation, and integration enables the paradigm to support formal evaluation of optimization formulations and their transformations.

MILP-EquivalBench systematically evaluates whether different evaluation methods correctly handle transformations of variables, constraints, and objectives. It provides evidence for the evaluation criterion, alongside which our work contributes the formal certificate and its automated construction procedure. Furthermore, the ablation results on FormulationBench support the practical value of the proof procedure. The complete framework achieves 99.4% accuracy, compared with 95.1% without informal planning and 93.2% with single-session proving. These results demonstrate how the adapted procedure helps complete challenging equivalence proofs.

Reviewer_nvfBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes OBEquival, an observational equivalence criterion for MILP formulations, and provides formal definitions and theoretical justification. To operationalize this criterion, the authors develop an LLM-driven sketch-and-prove pipeline that generates equivalence certificates checked by Lean. The authors also introduce MILP-EquivalBench, an evaluation benchmark containing 135 formulation pairs. The proposed method is compared with existing evaluation approaches on FormulationBench and MILP-EquivalBench. The results show that the method achieves high accuracy and recall on both evaluated benchmarks.

Critical strengths
  1. The paper systematically analyzes the limitations of existing equivalence criteria for MILP formulations.
  2. The author provides rich theoretical analysis.
Critical weaknesses
  1. [The evaluation benchmark lacks sufficient persuasiveness.] The 135 formulation pairs in MILP‑EquivalBench are constructed from reference formulations for 15 problem classes using the same nine predefined transformations, which fails to adequately capture diversity in problem types and formulation structures. Therefore, high accuracy on this benchmark mainly only demonstrates that the method can handle these prescribed transformations. Although the paper also conducts evaluations on FormulationBench, the sample size remains small, which raises concerns about whether the results generalize to broader automated modeling scenarios.
  2. In some cases in Appendix D, the reference formulation has an optimal solution while the transformed variant is infeasible. By contrast, Definition 3 and the derivations in Appendix B assume that the optimum is attained for every considered parameter instance. The authors are asked to clarify how the system handles formulation pairs that violate this assumption.
  3. [The analysis of method cost is missing. ]The two case studies in Appendix E consume 728 seconds with 2.9 million input tokens and 2610 seconds with 6.5 million input tokens, respectively, showing that some proof tasks incur substantial computational overhead. However, the paper does not report runtime and token consumption across the full benchmark. Hence, it cannot be verified whether the method is suitable for batch automated modeling evaluation under resource constraints.
Questions for authors

Please check the weak points.

3 comments

We sincerely thank you for reviewing our paper and providing us with valuable feedback. We have addressed your concerns as follows.

In some cases in Appendix D, the reference formulation has an optimal solution while the transformed variant is infeasible ...

In Appendix D, all reference formulations have optimal solutions, whereas the pairs obtained by applying the "Optimality-destroying cut" transformation are labeled as non-equivalent. Observational equivalence requires that the optimal solutions of the two formulations can be mapped to each other and their optimal objective values correspond through order-preserving mappings. The assumption that optima are attained in Definition 3 and Appendix B is used to prove that the two formulations are observationally equivalent. It does not require every pair evaluated in the benchmark to satisfy this assumption.

When the reference formulation has an optimal solution but the transformed formulation is infeasible, the required correspondence between optimal solutions cannot be established. Moreover, because the reference formulation has a nonempty feasible set while the target formulation has an empty feasible set, no forward variable map can preserve feasibility. When the LLM identifies such a concrete contradiction, it outputs a natural-language explanation, which the framework uses to classify the pair as non-equivalent.

For example, for the optimality-destroying cut in the knapsack problem in Appendix D, the LLM outputs NOT EQUIVALENT in an actual run and gives the following explanation: "... The valid instance n = 2, C = 2, w₀ = w₁ = 2, and v₀ = v₁ = 1 has a feasible all-zero solution in A but no feasible solution in B, since B would require y₀ + y₁ ≤ 1 and 2 ≤ y₀ + y₁ simultaneously; hence no forward variable map can satisfy fwd_feasible. ... The framework accordingly records this pair as non-equivalent.

[The analysis of method cost is missing. ]

Thank you for highlighting the cost of our method. In Appendix E.3 of the revised paper, we report the accuracy, average runtime, and average cost of the evaluation methods on both benchmarks in Table 11, reproduced below.

FormulationBench

MethodAccuracyAvg. Time (s)Avg. Cost (USD)
Execution81.5%31.7N/A
ORGEval29.6%16.8N/A
EquivaMap87.0%10.10.12
FLARE77.8%386.50.77
OBEquival99.4%548.11.29

MILP-EquivalBench

MethodAccuracyAvg. Time (s)Avg. Cost (USD)
Execution88.9%1.2N/A
ORGEval22.2%2.2N/A
EquivaMap83.0%8.00.11
FLARE88.9%352.10.88
OBEquival100%401.90.90

All costs are computed from recorded token usage using the GPT-5.6-SOL pricing listed in Table 12 of Appendix E.3. The runtime and cost of OBEquival are in the same order of magnitude as those of FLARE. The overhead mainly comes from the multiple stages of formal proof construction: the system first generates a proof plan and a Lean proof sketch, decomposes unresolved proof obligations into subgoals, proves them individually, and then reassembles and compiles the complete certificate. This additional computation supports formulation-level verification of observational equivalence, a more precise criterion for assessing equivalence between optimization formulations, and provides machine-checkable Lean certificates for accepted equivalence claims.

[The evaluation benchmark lacks sufficient persuasiveness.] ...

Thank you for pointing out the concerns about benchmark diversity and external validity. To the best of our knowledge, MILP-EquivalBench is currently among the most comprehensive benchmarks in terms of the range of model transformations it implements. It systematically exposes the main limitations of existing methods for evaluating the equivalence of optimization models.

We agree that the current 15 problems and 9 predefined transformation types cannot exhaustively cover all MILP reformulations in practice. MILP-EquivalBench is designed to systematically evaluate optimization model evaluation methods under different structural transformations. The nine transformation types cover representative changes at the variable, constraint, and objective levels. They correspond to common formulation modifications in optimization modeling and cover major structural differences considered in existing formulation-level evaluation work. These transformations reveal limitations in the ability of existing evaluation methods to reliably assess model equivalence across diverse structural changes.

Our method is not restricted to these nine transformation types. Provided that a new transformation can be correctly formalized and the corresponding proof obligations can be discharged, the method can in principle evaluate transformations beyond the current set, including their compositions. To further examine its applicability, we added two evaluations using EquivaFormulation and MIPLIB-NL in Appendix E.2. The selection and construction procedures are described in Appendix E.2.2. The results are reproduced below. ND denotes runs without a decision and counts as incorrect.

EquivaFormulation

MethodTPFPTNFNNDPrecisionRecallAccuracyAvg. Time (s)Avg. Cost (USD)
Execution0213111000%–34.3%<0.1N/A
ORGEval03321000%–99.1%<0.1N/A
EquivaMap01411710120%–52.8%26.50.04
FLARE0032400––100%75.00.15
OBEquival0032400––100%212.20.47

MIPLIB-NL

MethodTPFPTNFNNDPrecisionRecallAccuracyAvg. Time (s)Avg. Cost (USD)
Execution38002122100%46.9%46.9%654.9N/A
ORGEval0004140–0%0%954.4N/A
EquivaMap6000021100%74.1%74.1%721.60.02
FLARE5900220100%72.8%72.8%112.40.32
OBEquival810000100%100%100%336.30.83

Excluding the overly simple and redundant cases in EquivaFormulation, our evaluation covers the vast majority of datasets used to assess optimization model equivalence. The results show that OBEquival ties FLARE for the highest accuracy on EquivaFormulation and outperforms the baseline methods on all remaining datasets, indicating that our method provides more accurate assessments of optimization model equivalence. In future work, we will construct more comprehensive benchmarks covering more complex formulations and transformations for evaluating optimization model equivalence.

Thank you for adding the external benchmark experiments, clarifying the knapsack example, and reporting average runtime and cost on both main benchmarks. The new cost figures largely address my third concern.

The additional experiments broaden the evaluation. However, all 108 pairs from EquivaFormulation are non-equivalent, while the 27 equivalent pairs from MIPLIB-NL use three transformation types already covered by the original benchmark. In my view, proving equivalence is generally more challenging than finding a counterexample to equivalence. The new results therefore leave open how reliably the method can certify equivalent pairs arising from new types of transformations.

I have one related question about the knapsack example. If both formulations are infeasible for every admissible parameter setting, can the framework certify them as equivalent, or is this case outside the scope of the criterion?

Taking these points into account, I will keep my current score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.