WorksMathematics
RPX: Certifying Agent-Generated MILP Reformulations at Scale
Abstract
We present RPX, an independent certificate checker for AI-generated reformulations of mixed-integer linear programs (MILPs). RPX verifies that every feasible solution of either the original or the reformulated model can be converted into a feasible solution of the other with no worse objective value. This guarantees equal optimal values and enables solution recovery in the original variables. The checker derives the required checks directly from both models and verifies the certificate using exact arithmetic and reusable reconstruction rules. RPX certifies an agent-generated reformulation for each of the 240 instances in MIPLIB 2017 Benchmark v2. The source models contain up to 27.3 million matrix nonzeros. The median time to decode and check a certificate is 0.312 s, with a 95th percentile of 10.1 s.
Introduction
AI agents can now reformulate optimization models directly. Such changes must preserve the intended optimization problem. This issue is becoming practical as large language models (LLMs) move beyond describing mathematical programs to producing and modifying solver-ready models. Systems such as OptiMUS and autoformulation generate optimization models and solver code from natural language [1, 3], while agents can also inspect numerical MILP structure, eliminate variables, aggregate constraints, and produce new formulations. More broadly, LLM4MIP reports resolving 52 of 217 open MIPLIB instances using LLM-assisted solver workflows [18]. As agents gain greater freedom to modify executable optimization artifacts, independently establishing the correctness of their reformulations becomes increasingly important.
The difficulty is that an incorrect reformulation can look successful. A missing constraint or an invalid integrality relaxation may make the target easier to solve by changing its feasible set; a lost objective constant can instead distort comparisons of objective values. An agent’s explanation does not provide a machine-checkable guarantee, and agreement between numerical solver runs tests only particular outcomes. At the same time, requiring the two models to have identical feasible sets is too restrictive: useful reformulations may intentionally remove dominated solutions or introduce a different set of variables. What is needed is therefore a precise correctness criterion that is strong enough to preserve the optimization result, flexible enough to permit such reformulations, and independently checkable from the resulting models.
The missing verification interface. Existing work studies reformulation verification through mapped-solution tests, formal theorem proving, and SMT [5, 22, 25]; proof logging also certifies solver reasoning and presolve reductions [8, 17]. For open-ended agent reformulation, we seek an interface that takes the final source and target MILPs together with a certificate, without requiring the agent’s search history or solving either model. The certificate must establish correctness for every feasible solution, including how solutions can be reconstructed when variables are eliminated or replaced.
This interface must also scale: our evaluation includes source models with up to 1.43 million variables and 27.3 million matrix nonzeros. Certification must therefore support changes in variable representation while checking the complete models exactly and efficiently.
Our approach. We introduce RPX, an independent checker for this interface. Its fixed criterion, MI_OPT, requires that every feasible solution of either model can be converted into a feasible solution of the other with no worse objective value. This preserves feasibility and the optimal objective value (§ 2). RPX generates checks for every variable bound, integrality condition, constraint, and objective comparison from the models themselves.
A small exact Core checks linear arithmetic, integer reasoning, and case analysis. Fixed reconstruction rules avoid enumerating combinations of discrete choices and support joint recovery of variables linked by shared constraints. This design separates discovery from acceptance: agents may search freely, but only the independent checker determines whether a reformulation is certified (Figure 1).

Figure 1. Flexible generation, independent acceptance. Given the complete source MILP, reformulated MILP, and certificate, RPX returns Accepted, Invalid, or ResourceLimit. Orange dashed boxes denote untrusted generation; the teal boundary denotes trusted exact model interpretation and checking.
Our contributions are:
A fixed certification interface for open-ended agent reformulation. We formulate correctness as a property of the final source–target model pair. The MI_OPT contract permits useful changes such as removing dominated solutions and changing the variable space, while preserving feasibility and the optimal objective value.
An exact and scalable checker for this interface. RPX derives the required checks from the complete models and combines a small exact reasoning core with fixed reconstruction rules for reformulations that eliminate or reorganize variables.
Evidence that final-pair certification is practical at MIPLIB scale. We evaluate RPX on 240 source–target pairs originating from agent reformulation runs over all MIPLIB 2017 Benchmark v2 instances [13]. The same checker and fixed rule set certify all 240 pairs. Median decoding-and-checking time is 0.312 s and the 95th percentile is 10.1 s. A separate robustness campaign rejects all 12,544 confirmed-invalid certificates.
The MI_OPT Correctness Criterion
RPX needs a fixed criterion for deciding whether a reformulated model is correct. Requiring the source and target models to have identical feasible sets, or even a bijection between their feasible solutions, would be too restrictive: a useful reformulation may deliberately remove solutions that can never improve the objective. We first illustrate this point with a small example, and then formalize the criterion used by RPX.
Why identical feasible sets are too restrictive
Consider a simple network in which an integer quantity must pass through two consecutive links. Opening the first link costs 1 and opening the second costs 2; each has capacity 2, and each unit delivered earns 2. With binary opening decisions , the source is
An agent replaces the two decisions by one binary :
Both models retain .
Source to target. Keep and set when , and otherwise. If , closing both links cannot increase cost. If , feasibility and binary domains force , so the target has the same cost. Target to source. Set and keep ; all constraints hold and the cost is unchanged. Figure 2 visualizes this proof.

Figure 2. Preserve the optimization task while discarding unnecessary decisions. The forward map removes wasteful activations; the reverse map reconstructs a valid original solution. No bijection is needed. This tiny example captures the same recovery obligation that large reformulations must satisfy.
The forward construction discards unnecessary openings: maps to and becomes cheaper. The two models therefore do not have identical feasible sets under a one-to-one correspondence. Nevertheless, every feasible source solution has a target solution with no greater cost, and every feasible target solution has a source solution with no greater cost. These two properties are enough to force the same optimal objective value.
The MI_OPT guarantee
We now formalize the property illustrated above. A rational mixed-integer linear program (MILP) has feasible set
and minimization objective . Finite coefficients are interpreted as exact rationals; continuous coordinates range over . Absent bounds denote infinity, and maximization is normalized by negating the complete objective, including its constant. Thus a decimal such as 0.333 denotes 333/1000.
Definition 1 (No-worse construction). We write when there exists a total map with
The fixed goal requires and .
Theorem 1 (Optimization preservation). If , the models are simultaneously feasible or infeasible, and their extended optimal values are equal:
where . Objective unboundedness is preserved, and either construction sends an attained optimum to an optimum of the other model.
Proof. A total map sends any feasible input to a feasible output, giving feasibility in both directions. The forward inequality gives ; the reverse gives the opposite inequality, also when the value is . For an attained optimum, a feasible no-worse image must attain this common value. □
MI_OPT therefore preserves the optimization outcome without requiring identical variable representations, feasible sets, or LP relaxations.
How RPX Certifies MI_OPT
RPX checks a construction in each direction required by MI_OPT. We describe the source-to-target direction; the reverse direction exchanges the two models.
Checking a directional construction
A directional certificate describes how to construct the target variables from an arbitrary feasible source solution. The source variables remain symbolic, so the construction must work for every feasible source solution.
Figure 3 illustrates the checks for the running example. The forward construction sets when and when . In each case, RPX establishes that is binary, the target capacity constraint holds, and the objective does not increase. The second case uses integer reasoning to derive from the source constraints.

Figure 3. Small checks compose into a full guarantee. Forward certificate for the running example. Both branches are checked, with no sharing of branch-local assumptions. A separate reverse proof is also required.
More generally, RPX generates every required variable bound, integrality condition, constraint, and objective comparison from the target model and checks them for the constructed variables. The certificate must justify this complete set of checks.
Core reasoning
The Core provides the elementary exact reasoning used to establish the requirements in § 3.1. It works with affine expressions, meaning linear combinations of variables plus a constant. Specifically, it records three kinds of statements: an inequality , an equality , or the fact that is integer-valued. A certificate may combine valid inequalities and equalities using exact rational arithmetic, use integrality to round a bound, or justify a weaker statement from known variable bounds. For example, together with implies . The Weaken instruction packages a variable-bound implication into one check, avoiding explicit multipliers for every participating bound.
The Core also supports exhaustive case analysis. Different cases may use different constructions, but assumptions introduced within a case remain local to that case. Appendix § 9 specifies the supported splits and their acceptance conditions.
These rules support common reasoning such as substitution, aggregation, integer rounding, and finite case analysis without introducing a separate rule for every named reformulation technique. Appendix § 9 gives their exact acceptance conditions and a formal characterization of the finite case-based constructions they can certify.
Reusable reconstruction rules
Elementary case analysis becomes cumbersome when repeated discrete selections duplicate subsequent checks, or when several variables must be recovered jointly to satisfy shared constraints. RPX provides six fixed reconstruction rules for these tasks (Table 1).
| Rule | What it reconstructs |
| Interval | One continuous variable satisfying several established lower and upper bounds. |
| Menu | Binary option variables from an on/off indicator and the index of the selected option. |
| Signed | A binary direction indicator consistent with the sign of a bounded quantity. |
| Flow | Destination-specific flows whose sum equals the aggregate flow on every edge. |
| Subflow | A smaller flow that preserves all deliveries and uses no more of any edge. |
| UnitFlowRound | Binary edge decisions that preserve net flow at every node and do not increase cost. |
Table 1. Fixed reconstruction rules. The first three avoid repeated case splitting for local choices; the last three reconstruct flow variables that must satisfy shared network constraints.
The certificate establishes a rule’s preconditions using the Core, then uses the reconstructed variables and the relations guaranteed by that rule to establish the complete model checks in § 3.1. Appendix § 10 gives the exact rule specifications.
Local example: Menu. Suppose the source model uses binary variables to represent an optional selection: either exactly one option is selected or no option is selected. The reformulated target stores only a binary variable , indicating whether a selection is active, and an integer , indicating the selected option.
Menu checks that , that is integer-valued, and that . It then reconstructs binary variables satisfying
If , exactly option is selected. If , all are zero. The pair therefore distinguishes selecting option 0 from selecting no option. Figure 4 illustrates these possibilities.

Figure 4. Recover a discrete choice once, then reuse its laws. Menu reconstructs the optional one-hot vector from activation and index . For , all four feasible input states are shown, including the distinction between selecting index 0 and making no selection.
Menu records these relations once, allowing subsequent checks to reuse them without explicitly enumerating the possible states.
Joint example: UnitFlowRound. Suppose a reformulated model contains edge variables , while the source model requires binary edge decisions. Choosing each edge independently may violate flow conservation. UnitFlowRound instead reconstructs all edge decisions together. When the net flow at every node is integer-valued, it supplies binary variables with the same net flow at every node and no greater total cost. Figure 5 illustrates why this joint choice is necessary.

Figure 5. Why recovery can require a joint construction. In this schematic unit-capacity network, the upper path costs 2 and the lower path costs 4. Half a unit on each path costs 3; choosing the whole upper path costs 2. Both send one unit from to and preserve the zero balance at . Independent arc rounding can break these balances. UnitFlowRound certifies existence of a binary, no-worse flow after checking its premises.
Soundness and the Acceptance Boundary
We now state what acceptance guarantees and identify the components on which that guarantee depends.
Acceptance boundary. RPX checks two models represented with exact rational coefficients and one binary certificate. It performs no optimization and no proof search. The checker returns one of three outcomes: Accepted certifies MI_OPT, Invalid reports a failed certificate check, and ResourceLimit reports an exhausted checking budget.
Table 2 identifies the trusted components. When checking starts from MPS or LP text, exact import is also trusted. Appendix § 13 reports implementation validation.
| Inside the acceptance boundary | Outside the acceptance boundary |
| Exact model interpretation | Reformulation agent |
| RPX decoding | Certificate author |
| Exact rational arithmetic | Python authoring API |
| Core and reconstruction-rule implementations | RPA compiler |
| Case scoping | Solvers or scripts used during discovery |
| Automatic generation of all target-model checks | Natural-language explanations |
Table 2. The RPX acceptance boundary. Components inside the boundary must correctly implement the specified checks; components outside it may use arbitrary methods.
Soundness.
Theorem 2 (RPX soundness). Assume that exact model interpretation and the RPX acceptance boundary correctly implement the formal rules specified in Appendices § 9 and § 10. If RPX accepts a certificate for models and , then
Proof. Consider one direction, from to . Each Core step preserves a statement that holds for every feasible input solution. Case splits cover all feasible inputs, and assumptions introduced in one case cannot be used in another. Each reconstruction rule supplies variables satisfying its fixed guarantee once its checked preconditions hold. At the end of every feasible case, the checks generated from establish that the constructed solution is feasible and has no larger objective value. The accepted directional certificate therefore establishes . The reverse direction similarly establishes , and Theorem 1 gives . A complete directional proof appears in Appendix § 9.§ 4. □
Certificate production. Authors may use a Python interface and the readable RPA representation to produce binary RPX certificates. RPX independently checks the compiler’s output against both models, placing the compiler outside the acceptance boundary. Appendix § 11 gives worked certificates; Appendix § 13 describes the reproduction workflow.
Evaluation
We evaluate RPX on 240 model pairs and certificates, measuring coverage, checking cost, the benefit of reconstruction rules, and enforcement of the acceptance boundary. Appendix § 12 gives the experimental setup and supplementary results.
Benchmark set and measurement protocol
The evaluation set contains 240 source-target pairs, one for each instance in the MPILIB 2017 Benchmark v2 collection [13]. The target models were produced by an AI reformulation agent, and certificates were prepared after target selection. Source models range from 30 to 1,429,098 variables, from 4 to 2,897,380 constraints, and from 123 to 27,329,856 matrix nonzeros.
Coverage and timing use one fixed checker configuration for all 240 pairs. Timing measurements start from canonical exact models and prepared binary certificates, and therefore include certificate decoding and checking but exclude text-model import and certificate production. On an Apple M5 with 16 GiB of memory, each pair is checked in five fresh processes after one warmup; we report the median for each pair. Appendix § 12 gives the measurement protocol and complete descriptive results; Appendix § 13 describes implementation validation and artifact reproduction.
Coverage across reformulation patterns
The same Core and six reconstruction rules certify all 240 supplied pairs: 176 certificates use only the Core and 64 invoke reconstruction rules. Figure 6 reports mechanism usage, and Table 3 links representative reformulations to the mechanisms used to certify them. Median target/source ratios are 0.886 for variables, 0.822 for constraints, and 0.748 for nonzeros, although some targets grow. Appendix § 12.§ 3 gives the full distributions.
Figure 6. A shared reasoning vocabulary across reformulations. Bars count certificates using each mechanism among the 240 certified model pairs. Categories overlap because one certificate can use multiple mechanisms.
| Strategy | Example | What the agent changes | What RPX checks |
| Algebraic elimination and sparsification | square47, square41 | Replaces variables by their known values or formulas, and cancels repeated terms between equations. | Exact linear combinations and complete recovery obligations. |
| Boolean structure compression | k1mushroom | Merges variables for identical yes/no conditions and reuses common parts of those conditions. | Integer case reasoning and objective reconstruction. |
| Auxiliary-variable relaxation | roi5alpha10n8 | Allows fractional auxiliary values and replaces pairwise conflicts with group constraints allowing at most one selection. | Rounding, cases, and Interval witnesses for auxiliary recovery. |
| Shipment aggregation | n5-3 | Combines shipments from the same source, dropping the separate variables for each destination. | Forward summation and joint Flow decomposition in reverse. |
| One-hot block reformulation | neos-4532248-waihi | Allows fractional choices and replaces separate cost constraints with one bound on their weighted sum. | Joint binary recovery with equal balances and no greater cost via UnitFlowRound. |
| Global fixing or contradiction | enlight_hard, neos859080 | Fixes all values when only one feasible solution exists, or writes an explicit contradiction when none exists. | Modular linear reasoning, rounding, and exhaustive cases. |
Table 3. Representative certified reformulations. The examples illustrate distinct changes in model structure and the RPX mechanisms used to certify them.
Two cases quantify these changes. In square47, algebraic elimination reduces matrix nonzeros from 27.3 million to 138, 331. The certificate justifies exact cancellations using Core linear reasoning, and RPX checks the complete pair in 10.1 s. In n5-3, aggregating destination-specific shipments reduces variables from 2,550 to 850. The reverse certificate uses the Flow rule to reconstruct shipments preserving every destination demand and network balance; the complete check takes 7.95 ms.
Cost of complete model-pair checking
RPX checks every generated variable bound, integrality condition, constraint side, and objective comparison without solving either MILP. Across the 240 pairs, the median certificate decoding-and-checking time is 0.312 s, and 95% of pairs complete within 10.1 s. The maximum is 57.8 s. Median peak memory is 69 MiB, while the largest case reaches 4.16 GiB.
The certificates contain 57.9 million checked derivation steps and occupy 11.397 GB in total. Summed over the per-pair medians, decoding and checking takes 510 s, corresponding to an observed certificate throughput of 22.3 MB/s. Figure 7 shows the full latency distribution, and Table 4 reports certificate size, checking time, and memory use. The largest certificate occupies 1.06 GB, leaving substantial scope for reducing certificate storage.
Figure 7. Distribution of decoding-and-checking time across 240 model pairs. Points are per-pair medians of five fresh-process runs after one warmup, ordered by latency. Coverage and timing use the common configuration in Appendix § 12.§ 2; text-model import and certificate production are excluded.
| Metric | Median | P95 | Max. |
| Certificate (MB) | 8.46 | 233 | 1,059 |
| Kernel (s) | 0.288 | 9.99 | 55.6 |
| Decode + check (s) | 0.312 | 10.1 | 57.8 |
| Process wall (s) | 0.382 | 11.6 | 61 |
| Peak RSS (GiB) | 0.0673 | 1.11 | 4.16 |
Table 4. Checking cost over 240 cases. Times are per-case medians of five processes; RSS is each case’s largest measured peak. MB is decimal and GiB is binary.
Why reusable reconstruction rules matter
To measure the benefit of Menu, we compare it with explicit Core cases encoding the same reconstruction.
The controlled family contains independent optional selections. Both certificate variants use the same model pairs and preserve the same source variables; they differ only in whether each selection is represented by one Menu invocation or expanded into explicit cases. All certificates are checked by the same production checker under the same limits.
At , the Menu certificate occupies 3, 326 bytes and takes 74 s to decode and check. The explicit Core cases occupy 9.99 MB and take 126.4 ms. For this fixed construction, Menu is therefore approximately 3, 000 times smaller and 1, 700 times faster inside the checker. Figure 8 shows that the gap grows rapidly as independent selections are added.
Figure 8. The same reconstruction encoded with a Menu rule or explicit Core cases. For each , the two certificates use identical model pairs, preserve the same input variables, and are checked under identical resource limits. Points show median decoding-and-checking times over five measured runs after one warmup; error bars show the observed minimum and maximum.
Both variants encode the same preserved-coordinate reconstruction, isolating the cost of explicit case expansion. Appendix § 12.§ 4 gives the construction and protocol.
Validation of the acceptance boundary
| Validation campaign | Property exercised | Result |
| Targeted invalid certificates | Arithmetic rules, case scope, complete output coverage, reconstruction-rule premises, and binary encoding | 12,544 / 12,544 rejected |
| Wrong model-pair binding | A certificate must match both source and target models | 240 / 240 rejected |
| Deterministic reassembly | RPA compiler reproducibility and stored-artifact consistency | All 240 assembled twice to byte-identical RPX files, matching the stored certificates and passing independent checking |
| Exact-import tests | Objective constants, bounds, integrality defaults, ranged rows, malformed inputs | 24 regression tests and 160 independent LP vectors passed |
| Implementation size | Size of RPX-owned acceptance implementation | 3,893 production SLOC excluding tests |
Table 5. Validation campaigns and implementation size.
Table 5 summarizes the validation campaigns. RPX rejects all 12,544 targeted invalid certificates and all 240 tested model-pair mismatches. Import regressions and independent exact-number comparisons test model interpretation, while repeated assembly tests reproducibility. The RPX-owned acceptance modules contain 3,893 production source lines excluding tests. Appendix E gives the test construction, results, and counting scope.
Related Work
Verification of AI-generated reformulations
Table 6 compares the checked objects and guarantees of reformulation-verification systems. EquivaMap [25] discovers mappings between optimization formulations and, in its implemented verification procedure, applies the inferred mapping to a computed optimum before checking feasibility and objective agreement. RPX instead checks a symbolic construction for every feasible solution.
FLARE [22] uses Lean to prove reformulation theorems for parameterized MILPs. Its guarantees are conditional on the faithful formalization of the formulations, with import from concrete numerical models forming a separate bridge. RPX focuses on instance-level certification of concrete source-target pairs. FLARE and RPX also use different objective relations: FLARE permits strictly increasing objective rescaling, whereas MI_OPT retains the original numerical scale and permits pointwise objective improvement in both directions.
| Approach | Checked object | Guarantee | Connection to concrete source–target models |
| EquivaMap [25] | Formulations, inferred mapping, computed optimum | Mapped optimum passes feasibility and objective tests | Uses extraction and solver-produced solutions |
| FLARE [22] | Lean theorem and proof for parameterized formulations | Universal theorem under formalized semantics | Numerical-model import is a separate bridge |
| SOVER [5] | Extracted mappings and SMT conditions | Cross-feasibility and objective-order properties | Depends on extracted formulas and SMT encoding |
| Certified presolve [17] | Reduction trace or proof log | Correctness of logged reductions and recovery | Assumes or records a transformation sequence |
| RPX | Two concrete rational MILPs and a certificate | Bidirectional no-worse reconstruction over all feasible solutions | Derives complete checks directly from both models |
Table 6. Comparison of verification interfaces. Checked objects, guarantees, and their connection to concrete source–target models.
SOVER [5] separates LLM-based mapping extraction from SMT verification. Its linear path checks cross-feasibility and a global weak objective-order condition, while its nonlinear path provides a tolerance-aware guarantee. RPX instead uses exact rational semantics and checks the complete destination-model requirements induced by bidirectional constructions. These systems therefore occupy complementary points in the design space of reformulation verification.
Certification of optimization transformations
VIPR and rational MIP frameworks certify optimality, bounds, or infeasibility conclusions for a single model [8, 10, 11]. Certified MIP presolve records and verifies reduction steps, including solution recovery for 0-1 models through VeriPB [17]. More general dominance and symmetry proof systems already support solution repair, objective nonincrease, and substantial changes to the represented search space [6, 7, 24].
An RPX certificate establishes the relation between the final rational MILPs directly, including recovery across different variable representations.
Specialized proof systems for CP, MaxSAT, subgraph algorithms, dynamic programming, and arithmetic constraints likewise show that domain-specific certificate vocabularies can make complex reasoning independently checkable [4, 9, 14, 15, 20]. Multi-stage proof logging [12] and proof-carrying code [21] further motivate separating unrestricted artifact production from a restricted acceptance mechanism.
Practical and formally trusted checking
Practical proof logging depends on the logical guarantee, certificate representation, and checking overhead. VeriPB and CakePB demonstrate high-performance checking with formal guarantees for pseudo-Boolean optimization [19], while end-to-end verified subgraph solving combines a specialized checker with formally verified infrastructure [16]. PBLean uses reflection inside Lean to avoid the memory cost of constructing large explicit proof terms [23].
Scope and Limitations
Scope of the guarantee. RPX certifies the relation between the supplied numerical models. Faithful translation from a natural-language specification requires separate validation. Exact rational semantics can also yield different conclusions from floating-point solver statuses near feasibility tolerances. A general executor for applying certified recovery constructions to concrete solver outputs remains future work.
Trusted implementation. The acceptance implementation has not been mechanically verified. The tests in § 5 provide implementation evidence; formally verifying the checker or a translation into a verified backend remains future work.
Coverage of the certificate language. The Core and fixed reconstruction rules determine the constructions expressible in RPX. Other correct reformulations may require a different certificate, additional checking resources, or a new fixed reconstruction rule. Such extensions retain the same MI_OPT criterion and complete model checks.
Evaluation scope. The benchmark measures certification of prepared model pairs and certificates. End-to-end autonomous reformulation and certificate production remain future work.
Conclusion
RPX turns the acceptance of an agent-generated MILP reformulation into a fixed, exact model-pair checking task. Its MI_OPT criterion requires feasible no-worse constructions in both directions, preserving feasibility and the optimal objective value while allowing the two models to use different variables and discard dominated solutions. A small exact Core and fixed reconstruction rules establish the complete checks generated from both models.
Across 240 source-target pairs covering all MIPLIB 2017 Benchmark v2 instances, the same checker and rule set certify every supplied pair with a median decoding-and-checking time of 0.312 s. These results show that exact certification of flexible agent-generated reformulations is practical at realistic MILP scale. More broadly, RPX separates discovery from acceptance: agents may search for reformulations using arbitrary methods, while adoption of the resulting model rests on independently checkable evidence tied to the complete source and target models.
Formal RPX Semantics and Core Rules
This appendix formalizes the certificate semantics used in § 3.2. The fixed reconstruction rules introduced in § 3.3 are specified separately in Appendix § 10.
Throughout, let be the input MILP and the destination MILP for one direction of the certificate. All coefficients are exact rationals, continuous variables range over , and declared integer variables range over . As in § 2, both objectives are written as minimization objectives.
Directional certificate semantics
A complete RPX certificate contains one directional certificate for and one for . We describe a single direction.
Core statements and case scopes. For a normalized affine expression , the Core records three kinds of statements:
A directional certificate starts with the valid statements induced by the input model , including its finite variable bounds, finite constraint sides, and declared integrality conditions. Derived statements may then be added using the rules in Appendix A.2.
Case analysis creates nested scopes. A statement derived inside one case is visible only in that case and its descendants. Sibling cases cannot use one another’s assumptions or derived statements. A reconstruction rule from Appendix B may additionally introduce fresh variables and fixed relations among them; these variables and relations are likewise local to the scope in which they are introduced.
Specifying and checking the destination variables. RPX checks a symbolic construction under the assumption that the source variables satisfy .
For a construction defined by case analysis, a terminal case is a final case that either specifies every destination variable or is closed by a proved contradiction. Without case analysis, the whole direction has a single such case. In each case not closed by contradiction, the certificate gives an affine expression for every destination variable , interpreted as the assignment . These expressions may use the source variables and any variables introduced by fixed reconstruction rules that are available in the current scope. Write for this vector of formulas, where is the number of destination variables.
RPX substitutes the vector for the destination variables throughout . The destination model determines all feasibility conditions that must be established, and MI_OPT additionally requires . The certificate then justifies every generated condition.
Suppose has variable bounds , row bounds , integer-variable set , and objective . For each finite variable bound or constraint side, RPX generates the corresponding check below after substituting .
For every , RPX additionally generates the integrality requirement . Finally, RPX generates the no-worse objective requirement
equivalently,
Every generated requirement must be justified by a statement visible in the current scope, subject only to the restricted terminal discharges described in Appendix A.2.
A terminal case may instead be closed as infeasible, but only after an exact contradiction has been derived. A directional certificate is accepted only if its cases cover every feasible source assignment and each terminal case either derives an exact contradiction or justifies every generated condition above.
Exact Core inference rules
The Core provides a small collection of exact scalar rules. Fixed rules in Appendix B handle more elaborate reconstruction patterns.
Linear and integer inference. Let , , and denote affine expressions whose corresponding statements are visible in the current scope.
Linear inequality. From visible and , the Core may derive
provided , , and . Thus valid inequalities may only receive nonnegative multipliers, whereas equalities may receive arbitrary rational multipliers. The nonpositive rational constant permits exact weakening by a constant.
Linear equality. From visible equalities , the Core may derive
No additional nonzero constant may be introduced.
Integer combination. From and , the Core may derive
where . Rational multiples of equalities are valid because each visible equality establishes in the current scope.
Equality from opposite inequalities. From and , the Core derives .
Integrality-aware rounding. Suppose both and are visible, and and have identical variable coefficients. They therefore differ only by a rational constant: . Since and is integer-valued,
The Core therefore derives . This rule rounds only the constant term. It does not round variable coefficients.
Exact weakening from variable bounds. Suppose or is visible and the certificate proposes . The weakening is accepted only when the exact maximum of over the currently declared variable box is at most zero. Every nonzero coefficient of must therefore have a finite declared bound in the direction required to compute this maximum. If such a bound is unavailable, the weakening is rejected. This check uses the declared variable box rather than tighter inequalities derived inside the current case. Weaken packages a linear-combination argument over these bounds into one instruction: the checker computes the box maximum directly, avoiding a potentially long list of bound multipliers in the certificate.
Exhaustive case analysis. The Core supports exhaustive real and integer case splits. For a rational affine expression , a real split covers and . For an integer-valued affine expression , once has been established, an integer split covers and . There are two forms of case analysis.
Fact-producing cases. The two child cases must derive the same Core statement . Only is exported to the parent scope; all child assumptions and other derived statements remain local. These internal child derivations use Core scalar rules and do not invoke reconstruction rules.
Terminal cases. Instead of exporting a single statement, each child may continue independently until it constructs all destination variables and establishes the complete requirements generated in Appendix A.1. Fixed reconstruction rules from Appendix B may be invoked inside such terminal cases.
In both forms, case exhaustiveness is checked by RPX rather than asserted by the certificate.
Contradiction and administrative operations. A case may be closed as infeasible only when the current scope contains either a strictly positive constant inequality asserted to be at most zero, or a nonzero constant equality asserted to be zero. These are exact contradictions. A certificate may explicitly discard a statement that it no longer needs. This operation changes only storage and visibility; it has no logical effect.
Terminal discharge of trivial requirements. Normally, a generated requirement from Appendix A.1 must match a visible Core statement. RPX additionally permits a distinguished trivial discharge for the following cases:
an equality whose expression is exactly the zero constant;
an inequality whose expression is a nonpositive constant;
an integrality requirement whose expression is an affine integer combination of actual integer variables currently in scope, with an integer constant.
This terminal discharge does not create a reusable Core statement. In particular, it cannot justify a nonconstant inequality. Table A.1 summarizes the logical Core.
| Rule | Required information | Result |
| Linear inequality | Valid inequalities, equalities, permitted rational multipliers | New valid inequality |
| Linear equality | Valid equalities | New valid equality |
| Integer combination | Integer-valued expressions and equalities | New integer-valued expression |
| Equality pairing | and | |
| Round | Bound on an integer-valued affine expression | Rounded constant bound |
| Weaken | One valid statement plus finite declared variable bounds | Box-valid weaker inequality |
| Real case split | Rational affine expression | Exhaustive cases , |
| Integer case split | Integer-valued affine expression | Exhaustive cases , |
| Contradiction | Exact inconsistent constant statement | Close infeasible case |
Table A.1. The logical Core.
What the Core can express
Exhaustive case analysis allows different affine constructions in different regions of the source feasible set.
Proposition 1 (Finite case-based affine encodability). Let be a finite decision tree over . Each internal node performs one of the following exhaustive tests: (1) for a rational affine expression , or ; (2) for an integer-valued affine expression , or .
Each leaf assigns a rational affine destination tuple . Assume that, at every integer split, the required statement has a finite Core derivation under the assumptions leading to that node. Assume also that, under the assumptions leading to every feasible leaf , all destination-model and objective requirements generated for have finite Core derivations. Every infeasible leaf must instead have a finite Core derivation of an exact contradiction. Then, given sufficient implementation resources, the Core can certify .
Proof. Traverse recursively. At each integer node, emit the assumed derivation of and perform the corresponding exhaustive integer split. At each real node, perform the exhaustive real split. At a feasible leaf, emit the assumed derivations of all generated destination requirements and return the corresponding tuple . At an infeasible leaf, emit the assumed contradiction derivation and close the case. Exhaustiveness ensures that every feasible source solution reaches at least one feasible leaf, and the generated checks at that leaf establish a feasible destination solution with no larger objective value. Hence the resulting directional certificate establishes .
The proposition covers, among other patterns, fixed-variable substitution, affine aggregation, bounded integer enumeration, Boolean case constructions, sign-dependent mappings, and removal of dominated solutions.
Directional soundness
Theorem 3 (Directional soundness). Assume exact interpretation of the two models and exact arithmetic. Assume further that the Core rules and case-scoping semantics of Appendix A.2 are implemented correctly and that every fixed reconstruction rule used by the certificate correctly instantiates its theorem in Appendix B. If RPX accepts a directional certificate from to , then .
Proof. Fix an arbitrary feasible input . All initial Core statements induced by are valid for . We follow the finite case structure of the accepted certificate and show inductively that every visible Core statement remains valid for the current input and for any variables introduced by previously applied reconstruction rules.
The linear inequality and equality rules preserve validity by exact linear combination with the permitted multiplier signs. Integer combination preserves integer-valuedness. Equality pairing is immediate from the two opposite inequalities. The rounding rule is valid by integrality of the matched affine expression. The weakening rule checks the proposed implication exactly over the declared variable box.
At a fact-producing case split, the two children cover the parent domain exhaustively and establish the same exported statement; therefore that statement is valid in the parent scope. At a terminal split, the children again cover the parent domain exhaustively, but each continues independently toward a complete destination construction. Assumptions and derived statements remain within their case scopes.
Whenever a reconstruction rule is invoked, its Core-checked preconditions hold for the current input. By the corresponding theorem in Appendix § 10, there exists a joint valuation of the introduced variables satisfying the fixed relations supplied by that rule. Extending the current construction by such a valuation preserves all previously valid statements and makes the rule’s guaranteed relations valid.
A case closed by contradiction contains no feasible realization and therefore requires no destination construction. Every other terminal case specifies all destination variables. Because RPX generates every finite destination bound, integrality condition, row side, and the no-worse objective comparison, acceptance implies that the constructed tuple satisfies and .
Thus every feasible admits a feasible no-worse destination solution. Fixing the certificate’s deterministic case order and one valid choice for each fixed reconstruction rule yields a total map with for all . Therefore . □
Applying Theorem 3 to both directional certificates gives and . By Theorem 1, .
The soundness argument is independent of which fixed reconstruction rules are available. Adding a new rule can enlarge the set of certificates that RPX can express compactly, but it does not alter the MI_OPT acceptance criterion or remove any of the complete destination-model checks defined in Appendix § 9.§ 1.
Fixed Reconstruction Rules
Section 3.3 introduced six fixed reconstruction rules for cases that are cumbersome to express using only the Core. This appendix gives their exact interfaces and soundness arguments. We use the notation of Appendix § 9: , , and denote, respectively, that an affine expression satisfies , , or .
Common rule interface
A reconstruction-rule invocation, called a lift in the RPX instruction format, instantiates a fixed theorem of the form . Here, denotes the variables already available before the invocation. The precondition is a fixed collection of affine inequalities, equalities, integrality statements, and structural parameters. The tuple contains new variables, and is the fixed collection of bounds and relations guaranteed for those variables.
The certificate must justify every premise in using statements visible in the current case. If all premises are valid, RPX extends that case with the new variables and the relations . Subsequent Core steps may use those relations when constructing the destination-model variables.
A reconstruction rule does not remove or modify any existing variable, constraint, or objective coefficient. It only extends the current proof state. When execution leaves a case, variables introduced inside that case are discarded together with its local assumptions.
For batched invocations, every premise is interpreted in the state before the batch. Items in the same batch may refer to the same existing expressions, but one item may not use variables introduced by another item in that batch. Variables and relations generated by the completed batch are available to subsequent instructions.
The certificate producer cannot introduce a new theorem or modify the conclusion of an existing rule. Adding a reconstruction rule requires adding a fixed checker implementation together with a soundness argument. Regardless of which rules are used, RPX still generates and checks every destination-model bound, integrality condition, constraint, and objective comparison.
Local reconstruction rules
The first three rules introduce variables whose values can be selected locally from established bounds or a finite set of cases. Each admits a direct constructive proof.
Interval
Let be affine lower bounds and be affine upper bounds. Either list may be empty.
The Interval rule requires a proof of
When one list is empty, no cross-list premise is required. The rule introduces one continuous variable and guarantees
Lemma B.1 (Interval soundness). For every fixed value of satisfying the premises in (B.1), there exists a real number satisfying (B.2).
Proof. If both lists are nonempty, choose . This choice satisfies every lower bound. Let attain the maximum. For every , premise (B.1) gives , so every upper bound also holds.
If only the lower-bound list is nonempty, choose its maximum. If only the upper-bound list is nonempty, choose its minimum. If both lists are empty, choose . □
Lemma B.1 justifies introducing a variable satisfying the generated inequalities once all pairwise premises have been established.
Menu
Fix . Let and be affine expressions available before the rule invocation.
Menu requires
The rule introduces variables and guarantees
Lemma B.2 (Menu soundness). For every fixed value of satisfying (B.3), variables satisfying (B.4) exist.
Proof. Because is integer-valued and lies in , . If , then (B.3) implies . Set for every . These values satisfy (B.4).
If , then is an integer in . Set and set every other to zero. Then the unweighted sum in (B.4) is one, and the weighted sum is . This argument also covers . □
Signed
Fix a rational capacity . Let and be affine expressions available before the rule invocation.
Signed requires
The rule introduces one variable and guarantees
Lemma B.3 (Signed soundness). For every fixed value of satisfying (B.5), a variable satisfying (B.6) exists.
Proof. As in Lemma B.2, (B.5) implies .
If , then (B.5) forces . Choose . All conclusions follow.
Suppose . If , choose . Then , follows from , and the last inequality in (B.6) reduces to .
If , choose . Then and hold, while the last inequality in (B.6) follows from . The construction also covers and . □
The rule may be combined with Interval to derive the familiar positive and negative decomposition. Define . The generated relations imply and . There exist nonnegative continuous variables satisfying , , and . For example, if , choose and ; if , choose and ; and if , choose both variables to be zero. The authoring interface implements this construction by composing Signed with Interval.
Network reconstruction rules
The remaining rules introduce several edge variables that must satisfy shared network constraints. Their soundness follows from standard flow-decomposition and network-integrality arguments.
Notation
Let be a finite directed multigraph. Parallel edges and loops are allowed. For an edge vector , define its outgoing-minus-incoming balance at node by
A loop appears once in each sum and therefore contributes zero balance.
Fix a source node . Commodity has sink and nonnegative rational demand . Its required balance vector is , where denotes the unit vector of node . If , then .
Flow
Flow reconstructs destination-specific shipments from an aggregate edge flow while preserving every aggregate edge total.
Lemma B.4 (Common-source flow decomposition). Let be a finite directed multigraph with source . Let , and for each , let and . Suppose satisfies . Then there exist nonnegative edge vectors such that for each , and for every $e\in E. Repeated sinks, parallel edges, loops, disconnected components, and zero demands are allowed.
Proof. Maintain a nonnegative residual flow , initially , together with the unsatisfied demand of every commodity. Commodities with have zero balance and require no path flow.
Consider a commodity with positive unsatisfied demand. We first show that its sink is reachable from through edges with positive residual flow. Let be the set of nodes reachable from through positive-residual edges. If the sink were outside , no positive-residual edge would leave . Therefore,
On the other hand, the residual balance over equals the total unsatisfied demand of commodities whose sinks lie outside , which is positive. This contradicts (B.7). Hence a positive-residual -to-sink path exists.
Remove cycles from the path so that it is simple. Send along it the smaller of the path bottleneck and the commodity’s remaining demand. Subtract this amount from the residual and add it to the commodity flow. Each iteration either satisfies one remaining demand or reduces at least one positive residual edge to zero. A zero residual edge never becomes positive again, so finitely many iterations satisfy every demand.
After all demands have been met, the remaining residual has zero balance, . Because , add this residual circulation to any one commodity flow. This preserves that commodity’s balance and makes the edgewise sum of the commodity flows equal to . Nonnegativity is maintained throughout. □
RPX instantiation. Flow takes a directed multigraph , a source , sinks with exact nonnegative rational demands , and an old-scope affine expression for each edge. The certificate proves on every edge and at every node. RPX introduces nonnegative continuous variables satisfying for each commodity and on every edge. Any objective comparison or additional side constraints on these flows must be established through the destination-model checks.
Subflow
Subflow removes excess circulation from an aggregate flow while preserving all required node balances. Let denote the total demand.
Lemma B.5 (Demand-bounded subflow). Let satisfy , where . Then there exists satisfying and, for every edge , and . Loops, parallel edges, repeated sinks, disconnected components, and zero demands are allowed.
Proof. Apply the path-extraction procedure from the proof of Lemma B.4, but discard the final zero-balance residual instead of assigning it to a commodity. Let be the sum of all extracted path flows.
Each extracted path carries flow that was available in the current residual, so the total extracted amount on any edge does not exceed . Hence . The extracted paths meet every nonzero source-to-sink demand, so their sum has balance .
Each path can be chosen simple. It therefore uses any fixed edge at most once. The total weight of all extracted paths is at most the total demand , implying for every edge. A demand whose sink is the source contributes zero balance and requires no path. A loop cannot appear in a simple extracted path. □
RPX instantiation. Subflow takes the same input data as Flow, with . The certificate proves on every edge and . RPX introduces continuous variables satisfying , , and on every edge. The rule may remove zero-balance circulation and gives no objective guarantee; any required objective comparison remains part of the complete destination-model checks.
Figure B.1 illustrates the distinction. Flow preserves every edge total but separates it by destination; Subflow may reduce edge values by discarding circulation while preserving the required deliveries.

Figure B.1. Flow and Subflow solve different reconstruction problems. Flow decomposes an aggregate flow into destination-specific flows while preserving the total on every edge. In (b), commodity carries the unit circulation , giving on and on while delivering three units to . Subflow may remove circulation, but preserves the required node balances and never exceeds the supplied edge flow or total demand.
UnitFlowRound
UnitFlowRound reconstructs binary edge decisions from fractional edge values while preserving all node balances and not increasing a fixed linear cost.
Lemma B.6 (Cost-nonincreasing binary unit-flow existence). Let be a finite directed multigraph with . Let be its outgoing-minus-incoming incidence operator, and let be fixed. For every satisfying , there exists such that and . Loops, parallel edges, disconnected graphs, isolated nodes, negative costs, and are allowed.
Proof. Call an edge fixed if its current value is 0 or 1. Initially freeze every fixed edge and consider the undirected multigraph induced by the remaining strictly fractional edges.
Suppose this multigraph contains a cycle. Choose a signed unit circulation supported on that cycle. For an edge aligned with one orientation of the cycle, set its component in to 1; for an oppositely oriented edge, set it to . A loop gives a one-edge cycle, and parallel edges may give a two-edge cycle. In every case, . Replace by if necessary so that . Because every edge in the cycle is strictly inside , there exists such that and at least one additional edge reaches 0 or 1. Choose the largest such . This update preserves the node balances because , and it does not increase the cost because
Freeze every newly integral edge and repeat. Each iteration fixes at least one additional edge, so the procedure terminates after at most iterations.
At termination, the undirected graph induced by the remaining fractional edges is a forest. Suppose this forest is nonempty and take a leaf node. Contributions from all fixed edges are integer because their values are binary. The total node balance is also integer by assumption. The leaf is incident to exactly one remaining fractional edge, so that edge’s signed contribution must be integer. This contradicts its value being strictly between 0 and 1.
Therefore no fractional edge remains. The resulting vector is binary, has the same node balances as , and has no greater cost. The argument applies independently to disconnected components; isolated nodes and an empty edge set require no update. □
This is the unit-capacity form of the standard integrality property of minimum-cost network flow [2].
RPX instantiation. UnitFlowRound takes a directed multigraph with nodes and ordered edges, an old-scope affine expression for each edge, and a fixed exact rational cost vector . The certificate proves on every edge and at every node. RPX introduces integer variables with , hence binary, and generates
The cost vector is stored sparsely as a strictly increasing list of distinct edge indices with nonzero exact rational coefficients; omitted edges have zero cost.
The generated relations preserve node balances and bound the cost, as specified in (B.8)–(B.9).
Soundness and integration with the Core
Lemmas B.1-B.6 establish the extension property required by Appendix A.4: whenever a rule’s premises hold, its introduced variables can satisfy all generated relations. During checking, RPX verifies the premises and introduces the guaranteed relations into the proof state.
Worked Certificates
Appendix A defines the exact semantics of directional certificates and the Core rules. Appendix B specifies the six fixed reconstruction rules. This appendix combines these components in two worked examples.
Section C.1 gives an executable certificate for the same two-link running example used in Sections 2–3. It illustrates exhaustive case analysis, integer rounding, and complete destination-model checks using only the Core. Section C.2 presents a benchmark reformulation in which UnitFlowRound reconstructs hundreds of binary choices jointly.
The companion artifact contains the concrete models, executable RPA sources, binary RPX certificates, and canonical disassemblies. Appendix E.4 gives the reproduction workflow.
Running two-link example
We use exactly the source and target models from Section 2.1:
and
The source has two opening decisions ; the target contracts them into one decision . Both constructions retain .
Constructions and return checks
The constructions are those of Sections 2–3. Both retain : forward chooses when and when , satisfying ; reverse sets , so . Each of the two forward returns binds eight target-model checks, while the reverse return binds twelve source-model checks. Table C.1 maps the source lines in Listing 1 to these checks.
Executable RPA certificate
Listing 1 is the complete executable RPA certificate, including both directions and every return binding. In the forward block, x0, x1, x2 denote , , , and r0.hi, r1.hi denote the two source capacity inequalities. In reverse, coordinates restart at the target: x0, x1 denote , . Comments identify the arithmetic consequences.
1 RPA 13
2 .forward
3 split x0, int v0.int ; q=0 or q>=1, using integer q
4 left a0
5 lin.le f0, v1.lo + 2*v2.lo ; -a-2b <= 0
6 ret (x0, 0) (v0.lo, v0.hi, v0.int, exact, exact, exact, a0, f0)
7 right a0
8 lin.le f1, 1/2*a0 + 1/2*r0.hi ; 1/2-a <= 0
9 lin.int f2, -v1.int
10 round f3, f1, f2 ; 1-a <= 0
11 lin.le f4, 1/2*a0 + 1/2*r1.hi ; 1/2-b <= 0
12 lin.int f5, -v2.int
13 round f6, f4, f5 ; 1-b <= 0
14 lin.le f7, f3 + 2*f6 ; 3-a-2b <= 0
15 ret (x0, 1) (v0.lo, v0.hi, v0.int, exact, exact, exact, v0.hi, f7)
16 end
17 .reverse
18 ret (x0, x1, x1) (
19 v0.lo, v0.hi, v0.int, v1.lo, v1.hi, v1.int,
20 v1.lo, v1.hi, v1.int, r0.hi, r0.hi, exact)
Listing 1: Complete executable RPA certificate for the running two-link example.
| Lines | Generated model checks | Evidence |
| 6, 15 | , | The first three bindings retain the source domain of . |
| 6, 15 | , , | The chosen constants 0 and 1 satisfy all three checks. |
| 6, 15 | The left assumption gives ; the right return uses . | |
| 5–15 | Lower bounds prove the left objective check; two integer roundings prove the right one. | |
| 18–20 | , | Copy the target coordinate . |
| 18–20 | , | Both reconstructed coordinates copy the binary target variable . |
| 18–20 | , | Bind the same target capacity inequality to both source rows. |
| 18–20 | Substitution gives zero, so the objective check is an exact equality. |
Table C.1. Source-line bindings for the generated model checks in Listing 1.
The companion artifact provides both models, the RPA source, the assembled RPX certificate, and its canonical disassembly. RPX accepts the certificate, and reassembling the disassembly reproduces the same bytes.
Joint reconstruction in neos-4532248-waihi
Model pair
The instance contains 145 selection blocks, each with 574 binary choice variables , binary availability variables , and a binary activation variable . The blocks share a nonnegative variable , with objective min . For one block, the source requires
where each is a positive rational. The target retains the selection and availability constraints and the domains of , relaxes the choices to , and replaces the individual cost rows by
Across all blocks, 83,230 rows are replaced by 145 aggregate rows.
Forward construction
The forward construction retains every variable value. If , all , so (C.4) follows from . If , exactly one , and its source row gives . Thus the target is feasible with unchanged objective.
Network representation
The reverse direction must recover binary choices while preserving selection, availability, and the weighted-cost bound. Figure C.1 shows the network encoding. For each block, construct a network with choice nodes and two additional nodes . Edge carries with cost ; edge carries with zero cost. All edge values lie in . Their outgoing-minus-incoming balances are at node , at , and at , hence integer-valued. This 576-node, 1,148-edge network therefore satisfies the premises of UnitFlowRound.

Figure C.1. Network encoding of one selection block. For each choice , edge carries with cost , and edge carries with zero cost. UnitFlowRound makes the edge values binary while preserving node balances, yielding , , and .
The rule supplies binary edge variables on and on , with
These relations recover the selection and availability constraints, including , without increasing weighted cost.
Complete source-model checks
Replace by , retaining and all variables outside the selection blocks. Since , , and , the cost bound in (C.5) implies, for every ,
Thus every original cost row holds, and the objective remains . The certificate applies this construction to all 145 blocks. RPX then generates and checks every bound, integrality condition, constraint, and objective comparison for the complete recovered source solution.
Evaluation Details
This appendix describes the evaluated model pairs, measurement protocol, supplementary statistics, and controlled Menu experiment. Implementation validation and artifact reproduction are reported in Appendix E.
Evaluation set and scope
The evaluation comprises 240 source–target pairs, one for each MIPLIB 2017 Benchmark v2 instance. An AI agent produced the target formulations under a 30-minute execution budget, with instructions to justify its changes or report that no justified improvement was found. Certificates were prepared after target selection.
We evaluate the coverage and checking performance of RPX on these pairs using one common Core and the same six reconstruction rules.
Measurement protocol
Coverage and timing use the same fixed configuration: charged work units, 8,000,000 simultaneously stored statements, and case depth 64. All 240 pairs are accepted. A charged work unit counts a deterministic implementation operation, such as an expression-term traversal or a statement-table probe.
Timing uses an Apple M5 with 16 GiB of memory. Cases run sequentially, with one excluded warmup followed by five fresh-process measurements; filesystem caches are warm and scheduling is unpinned. All five measured runs of every pair return Accepted. Reported times are per-pair medians; peak RSS is the largest observed process peak for each pair.
Inputs are prepared canonical exact models and binary certificates. Agent execution, certificate production, text-model import, downstream solving, and numerical solution recovery are excluded. Table D.1 defines the timing boundaries. Decode + check is the primary metric used in § 5.
| Metric | Included work | Total |
| Kernel | Certificate execution and generated model checks | 472 s |
| Decode + check | Binary certificate decoding and kernel execution | 510 s |
| CLI total | Complete measured work inside the RPX command | 544 s |
| External wall | Elapsed time around the fresh RPX process | 548 s |
Table D.1. Timing boundaries. Totals denote the sum of per-pair medians across all 240 pairs.
Supplementary model and certificate statistics
Table D.2 supplements the mechanism counts in Figure 6 with the number of variables introduced by reconstruction rules, summed over all calls and cases. Certificate counts overlap. Of 149 UnitFlowRound invocations, 145 occur in neos-4532248-waihi; the remaining four occur in neos-960392, rail02, supportcase6, and tbfp-network.
| Rule | Certificates | Introduced variables |
| Interval | 42 | 424,216 |
| Menu | 20 | 1,083,853 |
| Signed | 22 | 343,352 |
| Flow | 1 | 2,350 |
| Subflow | 2 | 50,726 |
| UnitFlowRound | 5 | 640,430 |
Table D.2. Reconstruction-rule use. Introduced variables are summed over all calls and cases.
Figure D.1(a) shows the distributions of target/source model-size ratios. Targets have more variables, constraints, and matrix nonzeros than their sources in 6, 32, and 21 pairs, respectively. Figure D.1(b) relates certificate size to checking time and distinguishes Core-only certificates from those using reconstruction rules. These distributions describe variation across the benchmark pairs. § 5.3 and Table 4 report aggregate cost quantities.
Controlled Menu experiment
Model family and fixed construction. For independent selections, each instantiating Menu with , the compact model has
The expanded model retains these variables and adds binary satisfying
Figure D.1. Supplementary statistics for all 240 model pairs. (a) Empirical cumulative distributions of target/source variable, constraint, and matrix-nonzero counts; the vertical line at one denotes unchanged size. (b) Certificate size and median decoding-and-checking time for each pair, grouped by use of reconstruction rules.
Both models minimize . The compact-to-expanded construction preserves and supplies their uniquely determined option variables; the reverse construction projects away .
Certificate variants and protocol. The Menu certificate uses one batched invocation. The explicit Core-case certificate splits each into its four feasible states, , , , , producing combinations and repeating subsequent checks in each case. Both variants therefore certify the same model pair and the same construction using the same production checker.
All six explicit case expansions complete under construction ceilings of 256 MiB, one million generated instructions, depth 60, and 60 s. Both variants use identical checker limits. Timing follows Appendix § 12.§ 2, with Menu-rule and explicit-case runs alternating in order.
Results and interpretation. Figure 8 reports all six values of . Table D.3 adds timing ranges and fresh-process times at . The Menu certificate is approximately 3,000 times smaller and 1,700 times faster to decode and check than this explicit case expansion.
| Representation | Size | Decode + check (ms) | Process time (ms) |
| Menu rule | 3,326 bytes | 0.074 [0.073–0.076] | 3.61 |
| Explicit Core cases | 9.99 MB | 126.4 [126.2–127.1] | 130.6 |
Table D.3. Controlled comparison at . Brackets give the observed minimum–maximum over five measured runs; MB is decimal.
Generated models, certificates, and raw measurements accompany the reproduction artifact described in Appendix § 13.§ 4.
Implementation Validation and Reproducibility
This appendix describes input interpretation, implementation tests, code size, and the reproduction workflow.
Accepted input semantics
RPX interprets integers, finite decimals, scientific notation, and integer fractions as exact rationals; continuous variables range over the reals, and declared integer and binary domains are enforced without feasibility tolerances. Import resolves the default bounds and declarations of the supported MPS/LP formats; an absent bound side in the resulting canonical model denotes infinity. Duplicate coefficients are summed exactly, and maximization is normalized by negating the complete affine objective, including its constant. Contradictory finite bounds remain a description of an infeasible model.
When checking starts from MPS/LP text, import is part of the acceptance boundary. The importer supports linear and ranged rows, explicit bounds, and integrality declarations. It rejects ambiguous syntax, nonlinear terms, SOS and indicator constraints, and multiple RHS, range, or bound vectors in MPS input.
Validation campaigns
Targeted invalid certificates and resource limits. The targeted suite modifies valid small certificates, with 256 fixtures per category. All 12,544 fixtures in the 49 invalid categories return Invalid. Two additional categories impose insufficient work or stored-statement budgets on otherwise valid certificates; all 512 return ResourceLimit. Table E.1 gives the category groups. The suite includes out-of-scope statements, omitted destination variables, invalid arithmetic, false contradiction claims, incompatible reconstruction premises, and malformed encodings.
| Category group | Categories | Fixtures | Observed result |
| Core inference, case scope, branching, and complete output arity | 18 | 4,608 | All Invalid |
| Local reconstruction rules: premises and dimensions | 7 | 1,792 | All Invalid |
| Network reconstruction rules: dimensions, endpoints, costs, and premises | 17 | 4,352 | All Invalid |
| Binary encoding: opcodes, rational canonicality, truncation, and trailing bytes | 7 | 1,792 | All Invalid |
| Work and stored-statement limits | 2 | 512 | All ResourceLimit |
Table E.1. Targeted validation categories, with 256 fixtures per category. Resource-limit fixtures contain otherwise valid certificates.
Model-pair binding. The 240 valid benchmark certificates are cyclically reassigned to incorrect source–target pairs. All 240 checks return Invalid.
Exact model import. The 14 MPS and 10 LP regressions cover objective constants and maximization, integer markers, default and negative upper bounds, binary-domain intersections, ranged rows, duplicate coefficients, multiline LP syntax, malformed inputs, and resource outcomes. All 24 pass. An independent comparison uses 160 generated LP models and canonical models constructed with Python’s Fraction type. All 160 match, with expected rational coefficients computed independently of the production scalar parser.
Network reconstruction rules. The small-network suite contains 128 Flow, 128 Subflow, and 896 UnitFlowRound instances, with at most five nodes and eight directed edges. All instances pass. The UnitFlowRound inputs include 257 fractional and 639 integral flows; known binary witnesses are used to check the balance and cost relations.
Deterministic certificate assembly. Assembling each of the 240 RPA certificates twice produces byte-identical RPX files matching the stored certificates. All 240 pass independent checker invocations. The default assembler ceiling suffices for 238 inputs; k1mushroom and supportcase12 increase the assembler’s syntax and expression-node budget from 20 million to 64 million. The larger budget applies only to assembly.
Binary-stream mutation. In 50,000 bounded mutation trials starting from three valid certificates, RPX accepts 429 inputs: 277 unchanged certificates and 152 modified certificates that remain valid. Independent exact-arithmetic checks validate all 152 modified certificates by checking the constant inequalities or enumerating both binary choices for the one-node UnitFlowRound case.
Implementation size
Table E.2 counts nonblank, noncomment physical source lines, excluding tests. The RPX acceptance implementation comprises 3,893 lines across the model, certificate, codec, verifier, support, and reconstruction-rule modules.
| Code region | Source lines | Counting scope |
| RPX-owned acceptance implementation | 3,893 | Complete owned acceptance modules |
| Six reconstruction-rule modules | 1,380 | Included in the 3,893-line total |
| RPA compiler and assembler | 10,128 | Authoring software outside the acceptance boundary |
Table E.2. Implementation size. The reconstruction-rule modules are included in the acceptance-implementation total.
The count excludes the CLI and I/O facade, text-import utilities, third-party arithmetic libraries, and platform software. The artifact documents these dependencies.
Reproduction workflow
The artifact provides the implementation, all 240 model pairs and certificates, validation suites, raw measurements, and reproduction scripts. A checksum manifest identifies the distributed files. REPRODUCE.txt lists reproduction commands; docs/FORMAT.md specifies grammars, file formats, and resource policies. The numeric header in Listing 1 identifies the serialization format. A minimal workflow from the artifact root is:
cargo build -p kernel-core --release --locked
target/release/rpx canonical source.mps source.mcm
target/release/rpx canonical target.lp target.mcm
target/release/rpx assemble proof.rpa proof.rpx
target/release/rpx verify source.mcm target.mcm proof.rpxReferences
- [1]Ali AhmadiTeshnizi, Wenzhi Gao, and Madeleine Udell. OptiMUS: Scalable optimization modeling with (MI)LP solvers and large language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 577–596, 2024.arxiv.org/abs/2402.10172
- [2]Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. ISBN 9780136175490.
- [3]Nicolás Astorga, Tennison Liu, Yuanzhang Xiao, and Mihaela van der Schaar. Autoformulation of mathematical optimization models using LLMs. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 1864–1886, 2025.arxiv.org/abs/2411.01679
- [4]Jeremias Berg, Bart Bogaerts, Jakob Nordström, Andy Oertel, and Dieter Vandersande. Certified core-guided MaxSAT solving. In Automated Deduction – CADE 29, volume 14132 of Lecture Notes in Computer Science, pages 1–22, 2023. doi: 10.1007/978-3-031-38499-8_1.DOI
- [5]Swapnil Bhattacharyya and Mayank Baranwal. SOVER: Formal certification of optimization reformulations via LLM-assisted SMT verification. In Findings of the Association for Computational Linguistics: EMNLP 2026, pages 40213–40230. Association for Computational Linguistics, 2026. doi: 10.18653/v1/2026.findings-emnlp.1886.arxiv.org/abs/2609.00728
- [6]Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, and Jakob Nordström. Certified symmetry and dominance breaking for combinatorial optimisation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3698–3707, 2022. doi: 10.1609/aaai.v36i4.20283.DOI
- [7]Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, and Jakob Nordström. Certified dominance and symmetry breaking for combinatorial optimisation. Journal of Artificial Intelligence Research, 77:1539–1589, 2023. doi: 10.1613/jair.1.14296.DOI
- [8]Kevin K. H. Cheung, Ambros Gleixner, and Daniel E. Steffy. Verifying integer programming results. In Integer Programming and Combinatorial Optimization, volume 10328 of Lecture Notes in Computer Science, pages 148–160. Springer, 2017. doi: 10.1007/978-3-319-59250-3_13.DOI
- [9]Emir Demirović, Ciaran McCreesh, Matthew J. McIlree, Jakob Nordström, Andy Oertel, and Konstantin Sidorov. Pseudo-boolean reasoning about states and transitions to certify dynamic programming and decision diagram algorithms. In 30th International Conference on Principles and Practice of Constraint Programming, volume 307 of Leibniz International Proceedings in Informatics, pages 9:1–9:21, 2024. doi: 10.4230/LIPIcs.CP.2024.9.DOI
- [10]Leon Eifler and Ambros Gleixner. A computational status update for exact rational mixed integer programming. Mathematical Programming, 197:793–812, 2023. doi: 10.1007/s10107-021-01749-5.DOI
- [11]Leon Eifler and Ambros Gleixner. Safe and verified gomory mixed-integer cuts in a rational mixed-integer program framework. SIAM Journal on Optimization, 34(1):742–763, 2024. doi: 10.1137/23M156046X.DOI
- [12]Maarten Flippo, Konstantin Sidorov, Imko Marijnissen, Jeff Smits, and Emir Demirović. A multi-stage proof logging framework to certify the correctness of CP solvers. In 30th International Conference on Principles and Practice of Constraint Programming, volume 307 of Leibniz International Proceedings in Informatics, pages 11:1–11:20, 2024. doi: 10.4230/LIPIcs.CP.2024.11.DOI
- [13]Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco E. Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13:443–490, 2021. doi: 10.1007/s12532-020-00194-3.DOI
- [14]Stephan Gocht, Ciaran McCreesh, and Jakob Nordström. Subgraph isomorphism meets cutting planes: Solving with certified solutions. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 1134–1140, 2020.DOI
- [15]Stephan Gocht, Ciaran McCreesh, and Jakob Nordström. An auditable constraint programming solver. In 28th International Conference on Principles and Practice of Constraint Programming, volume 235 of Leibniz International Proceedings in Informatics, pages 25:1–25:18, 2022. doi: 10.4230/LIPIcs.CP.2022.25.DOI
- [16]Stephan Gocht, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordström, Andy Oertel, and Yong Kiam Tan. End-to-end verification for subgraph solving. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 8038–8047, 2024. doi: 10.1609/aaai.v38i8.28642.DOI
- [17]Alexander Hoen, Andy Oertel, Ambros Gleixner, and Jakob Nordström. Certifying MIP-based presolve reductions for 0–1 integer linear programs. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, volume 14742 of Lecture Notes in Computer Science, pages 310–328. Springer, 2024. doi: 10.1007/978-3-031-60597-0_20.DOI
- [18]Yicheng Huang, Wenzhi Gao, Dongdong Ge, Madeleine Udell, and Yinyu Ye. How much can LLMs help solve MIPs?, 2026. URL https://llm4mip.github.io/. Research website.
- [19]Wietze Koops, Daniel Le Berre, Magnus O. Myreen, Jakob Nordström, Andy Oertel, Yong Kiam Tan, and Marc Vinyals. Practically feasible proof logging for pseudo-boolean optimization. In 31st International Conference on Principles and Practice of Constraint Programming, volume 340 of Leibniz International Proceedings in Informatics, pages 21:1–21:27, 2025. doi: 10.4230/LIPIcs.CP.2025.21.DOI
- [20]Matthew J. McIlree and Ciaran McCreesh. Certifying bounds propagation for integer multiplication constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 11309–11317, 2025. doi: 10.1609/aaai.v39i11.33230.
- [21]George C. Necula. Proof-carrying code. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 106–119. ACM, 1997. doi: 10.1145/263699.263712.DOI
- [22]Henry Robbins, Connor Lawless, Madeleine Udell, and Ellen Vitercik. FLARE: Verifying MILP reformulations with LLM-based theorem proving, 2026. arXiv:2608.25220.arxiv.org/abs/2608.25220
- [23]Stefan Szeider. PBLearn: Pseudo-boolean proof certificates for Lean 4, 2026. arXiv:2602.08692.arxiv.org/abs/2602.08692
- [24]Jasper van Doornmalen, Leon Eifler, Ambros Gleixner, and Christopher Hojny. A proof system for certifying symmetry and optimality reasoning in integer programming, 2023. arXiv:2311.03877.
- [25]Haotian Zhai, Connor Lawless, Ellen Vitercik, and Liu Leqi. EquivMap: Leveraging LLMs for automatic equivalence checking of optimization formulations. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 74288–74305, 2025.arxiv.org/abs/2502.14760



