acceptodds
Under review as a conference paper at ICLR 2027

Conformal Variable Fixing for Mixed-Integer Optimization

Abstract

We present a method for accelerating repeated solves of mixed-integer optimization problems with fixed structure and varying data. A learned predictor maps problem data to binary variable assignments. We use conformal prediction to decide which assignments we can be confident to fix, leaving the remaining binary variables and all continuous variables to an optimization solver. This yields a reduced problem with fewer binary variables. We also introduce a nonconformity score that measures how far the predicted assignments must be relaxed for the reduced problem to contain a near-optimal solution. Under exact optimization, our method returns a feasible solution for every feasible instance. For calibration and test instances drawn independently from the same distribution, the returned solution is near-optimal with probability at least a user-specified level. Experiments on four benchmark families in control, robotics, and transportation show that the method can reduce solve times while maintaining high solution quality.

Primary area:
optimization
Keywords:
Conformal prediction, mixed-integer optimization, learning to optimize, variable fixing, probabilistic guarantees

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_E4tnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes conformal variable fixing for repeated mixed-integer optimization. A learned predictor proposes binary assignments, and an optimization-aware nonconformity score determines which variables to fix while retaining a near-optimal solution with a prescribed marginal probability. A repeated-solve variant progressively releases fixed variables to recover feasibility. The authors establish guarantees under i.i.d. sampling and exact optimization assumptions and evaluate the framework on four benchmark families.

Critical strengths

The nonconformity score is well aligned with optimization quality and naturally accommodates multiple optimal or near-optimal solutions. The feasibility recovery mechanism is clear, and the framework can be integrated with existing solvers. The substantial runtime reductions reported on helicopter and school-bus routing demonstrate its potential for repeated optimization.

Critical weaknesses

My main concern is that the experiments do not sufficiently isolate the practical contribution of the proposed calibration. There is no comparison using the same predictor and retry procedure with a validation-tuned fixing threshold at a matched empirical near-optimality rate, nor an ablation against simpler nonconformity scores. The solver comparisons also leave the time–quality tradeoff incompletely characterized: GRB seeks a per-instance 1% MIP-gap certificate, whereas the proposed method allows 20% marginal near-optimality failures, and GRB HEUR stops at the first feasible solution. Comparisons across intermediate solver budgets would therefore be more informative. Empirical advantages are also uneven: for 10 obstacles in Table 3, NEAR is faster than RCP (0.107 versus 1.499 seconds) and achieves a higher near-optimality rate (89.3% versus 81.8%), although it lacks the same theoretical guarantee. Furthermore, evaluating only alpha = 0.2 and epsilon = 0.01 leaves the benefits at higher reliability levels unclear, while offline data-generation, training, and calibration costs are not quantified. These gaps leave the incremental empirical contribution insufficiently established and make me toward rejection in its current form.

Questions for authors

With the predictor and retry procedure held fixed, how does the proposed calibration compare with validation-tuned thresholds and simpler conformal scores at matched empirical near-optimality rates? Do the speedups persist for alpha = 0.05 or 0.01, across repeated calibration splits, and against solver configurations evaluated at comparable runtime or solution quality? What are the total offline data-generation, training, and calibration costs, and how many subsequent solves are needed to amortize them?

3 comments
AuthorsOpenReview ↗

Response to Reviewer E4tn

Thank you for the careful review. We uploaded a revised PDF. Table and appendix numbers below refer to it. Your main concern is whether conformal calibration contributes anything beyond a tuned threshold. We answer that first.

1. Validation-tuned thresholds. We ran this ablation: same predictor, same fallback path, threshold tuned on held-out data to an empirical rate of 80% (Table 17, Appendix P). The two procedures nearly coincide, and there is a simple reason. An instance retains an ϵ\epsilon-optimal solution at threshold δ\delta exactly when its score is at most δ\delta. Tuning to rate 1−α1-\alpha therefore selects the order statistic ⌈(1−α)n⌉\lceil (1-\alpha) n \rceil of the scores, and split conformal selects ⌈(1−α)(n+1)⌉\lceil (1-\alpha)(n+1) \rceil. With n=800n = 800 and α=0.2\alpha = 0.2 these are the 640th and 641st scores. Our tuned threshold used a held-out half of the calibration set, so the two also differ by sampling. In our runs the thresholds differ by at most 0.024 (for example 0.313 and 0.316 on obstacle 10, 0.484 and 0.483 on lane change 18), and the ϵ\epsilon-optimality rates by at most 2.6 points.

So the contribution is not the quantile rule. It is the score. It tells us, for every threshold at once, whether the restricted problem still contains an ϵ\epsilon-optimal solution, with one optimization problem per instance. The conformal correction then gives the finite-sample guarantee at no cost.

A simpler score is the smallest δ\delta whose rounding set contains the stored optimum x⋆x^\star. It needs no optimization and is an upper bound on our score, so it is valid, but it fixes fewer variables whenever several near-optimal solutions exist. We will add this ablation to the final version.

2. Solver comparisons. You are right that a 1% gap certificate, a 20% marginal failure rate, and GRB HEUR are different criteria. We ran Gurobi at relative gaps of 0.1%, 0.5%, 5% and 10% on obstacle 10, school bus 18, lane change 18 and auctions with 200 items (Table 11, Appendix J). The speedup of CONFORMAL against Gurobi at each gap stays between 99.1% and 99.5% on obstacle avoidance, at 99.8% or more on school bus, and between 31.6% and 40.1% on lane change. On auctions Gurobi at a 10% gap is faster than CONFORMAL, but it is ϵ\epsilon-optimal on 0.2% of instances. Table 11 also reports Gurobi with its gap set to the mean suboptimality of CONFORMAL. There Gurobi returns better solutions than CONFORMAL, because its gap bounds the error on every instance while ours is an average. We keep GRB HEUR only as a reference point and now say so in Table 1.

3. NEAR on obstacle avoidance. Your reading is correct at every obstacle size: NEAR is ϵ\epsilon-optimal more often than CONFORMAL and RCP at α=0.2\alpha = 0.2. But NEAR has no reliability parameter and no guarantee. Its rate is 89.3% on obstacle 10, 78.2% on helicopter 75, 2.7% on lane change 18, and at most 1.5% on the auction instances we added, and nothing indicates in advance which case applies. Our method can be asked for more: at α=0.01\alpha = 0.01 CONFORMAL is ϵ\epsilon-optimal on 99.5% of obstacle 10 instances in 0.42 s (Table 12), against about 22 s for Gurobi.

4. Higher reliability levels. We added α=0.01\alpha = 0.01 and 0.50.5 (Table 12, Appendix K). At α=0.01\alpha = 0.01, CONFORMAL is ϵ\epsilon-optimal on 99.5% of obstacle 10 instances in 0.42 s, on 99.2% of school bus 18 instances in 0.025 s, and on 99.3% of helicopter 75 instances in 0.15 s. On lane change 18 the speedup does not survive: the calibrated threshold fixes no variable and the method reduces to the full solve. Calibration reports this instead of fixing variables it cannot support.

5. Repeated calibration splits. For each configuration we drew 10 independent calibration sets and recalibrated (Table 13, Appendix L). At α=0.2\alpha = 0.2 the standard deviation of the held-out ϵ\epsilon-optimality rate is between 0.25 and 3.95 points over the 23 configurations, and the mean rate is within 1.86 points of 80% wherever the threshold does not saturate.

6. Offline cost. We added the measured cost for every configuration (Table 15, Appendix N). Label generation takes 361 hours of solver time over the 23 configurations. Counting label generation only and using CONFORMAL, it is recovered after about 5,500 online solves on school bus 18, 7,800 on obstacle 10, 9,300 on helicopter 75, and 20,000 on lane change 18.

Thank you for the additional experiments. The results at stricter reliability levels clarify when the method can still accelerate solves. My main empirical concern remains unresolved. At matched empirical near-optimality rates, how many more variables can the optimization-aware nonconformity score fix, and how much solve time can it save, compared with the simpler score based on a stored optimum, which also provides a coverage guarantee? This comparison is central to assessing the practical benefit of the proposed score, so I maintain my rating of 2.

AuthorsOpenReview ↗

Simpler nonconformity score at matched rates

Thank you. We ran this comparison and added it to the revised PDF (Table 18, Appendix Q). The simpler score is the smallest δ\delta whose rounding set contains the stored optimum x⋆x^\star. Predictor, calibration set and test instances are the same as for our score.

The direct answer to your question: at matched empirical rates, the simpler score fixes about the same number of variables and runs about as fast. At test time the method depends only on δ\delta, so both scores give the same results at the same threshold. The difference is the level they certify.

ConfigScoreα\alphaδ\deltafixed vars (%)ϵ\epsilon-opt (%)time (s)
obstacle 10ours0.20.31395.577.10.035
obstacle 10stored optimum0.20.47090.594.90.135
obstacle 10stored optimum0.60.32895.279.80.043
helicopter 75ours0.20.36999.582.70.020
helicopter 75stored optimum0.20.42399.496.30.029
helicopter 75stored optimum0.40.26699.777.30.021
lane change 18ours0.20.48439.980.312.6
lane change 18stored optimum0.20.49034.486.818.7
lane change 18stored optimum0.40.47744.271.010.9

To reach about 80% in practice, the simpler score must be calibrated at α=0.4\alpha = 0.4 to 0.60.6, so it certifies only 40 to 60%. Calibrated at α=0.2\alpha = 0.2 to certify 80%, it is ϵ\epsilon-optimal on 87 to 96% of instances, fixes up to 5.5 points fewer variables, and is 1.4 to 3.8 times slower. Our score certifies 80% and observes 77 to 83%. So the benefit of the score is that the speed of an 80% rule comes with a guarantee at 80%, without a separate tuning step. The reason is that x⋆x^\star is one of possibly many ϵ\epsilon-optimal solutions, and our score accepts a threshold if the restricted problem keeps any of them.

The simpler-score runs used a different allocation, whose Gurobi baseline was 8 to 13% slower.

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

This paper proposes a conformal variable-fixing framework for accelerating repeated mixed-integer optimization problems with fixed structure and varying parameters. A neural predictor estimates binary variable assignments, while conformal calibration determines which variables can be safely fixed and which should remain free. The authors introduce a nonconformity score based on retaining an epsilon-optimal solution and develop a retry-aware procedure (RCP) that progressively relaxes variable fixings to ensure feasibility. Under exact optimization and i.i.d. assumptions, the method provides marginal probabilistic near-optimality guarantees. Experiments on four benchmark families demonstrate substantial speedups while maintaining good solution quality.

Critical strengths
  1. The paper addresses an important problem in learning-augmented mixed-integer optimization by combining variable fixing with formal solution-quality guarantees.
  2. The proposed nonconformity score is closely aligned with the optimization objective, since it measures the relaxation required to retain an epsilon-optimal solution rather than simply evaluating prediction accuracy.
  3. The retry-aware conformal procedure provides a principled mechanism for recovering feasibility while maintaining a marginal probabilistic near-optimality guarantee.
  4. The theoretical analysis is clearly presented, and the experiments cover four application-oriented benchmark families with substantial runtime improvements.
Critical weaknesses
  1. The empirical comparisons with existing learning-based MIP methods are limited. The main baselines are Gurobi, nearest-neighbor prediction, a constant predictor, and two fallback strategies. Comparisons with more competitive learned variable-fixing or optimization-strategy prediction methods would better establish the practical contribution.
  2. The reported online speedups exclude substantial offline costs. Each problem setting requires thousands of optimally solved instances, neural network training for 2,000 epochs, and additional calibration optimization. The paper does not provide an end-to-end cost analysis or estimate how many repeated solves are needed to amortize this overhead.
  3. The probabilistic guarantee is marginal and relies on calibration and test instances being drawn from the same distribution. The experiments do not investigate distribution shifts, despite their practical relevance to repeated optimization in dynamic environments.
  4. The experiments use a single choice of epsilon = 0.01 and alpha = 0.2. Without sensitivity analysis, it is difficult to assess how stronger reliability requirements affect the number of fixed variables, computational speedups, and solution quality.
  5. The evaluation is restricted to synthetic, fixed-structure problem families. The effectiveness of the framework on heterogeneous real-world MILPs, especially those with changing constraint structures, remains unclear.
  6. The theoretical guarantees assume exact optimization, whereas the implementation uses numerical tolerances and finite time limits. The paper does not sufficiently quantify how these practical solver settings affect the interpretation of its formal guarantees.
Questions for authors
  1. How does the proposed method compare with existing learning-based variable-fixing approaches under identical solver settings and datasets?
  2. What is the total offline computational cost, including optimal-solution generation, predictor training, and conformal calibration? How many online solves are required to amortize this cost?
  3. How do the runtime, fixing ratio, and empirical coverage change when epsilon and alpha are varied, particularly under more stringent accuracy requirements?
  4. How robust is the conformal calibration to distribution shifts between training, calibration, and deployment instances?
  5. Can the authors clarify how numerical solver tolerances and time limits affect the theoretical near-optimality guarantees in practice?
  6. How frequently does RCP require multiple retries, and how does the number of retries influence its runtime advantage?
1 comment
AuthorsOpenReview ↗

Response to Reviewer AXjy

Thank you for the review. We uploaded a revised PDF. Table and appendix numbers below refer to it.

W1, Q1. Learned baselines. We added the strategy-prediction method of Bertsimas and Stellato (MLOPT), with the same test sets and evaluation code as our methods (Table 16, Appendix O). It predicts the full binary assignment with a classifier over the assignments seen in training. Its training finished within our budget (one 24-hour job on 32 cores) on six configurations, and not on helicopter with n≥30n \ge 30, lane change with n≥4n \ge 4, or school bus. The two approaches are complementary. When few distinct assignments occur, MLOPT works very well: it is ϵ\epsilon-optimal on 99.5% of helicopter 15 instances, more often than our methods. When most instances have their own assignment it cannot succeed: on obstacle avoidance with n≥5n \ge 5 it returns no feasible solution on 36.7% to 83.6% of instances. Our method fixes only the variables it is confident about, so it degrades gradually and keeps its guarantee.

Learning-to-branch methods act inside the solver's search and could be applied to our restricted problems, so we did not treat them as competing baselines. We did not compare against graph-based fixing methods such as Neural Diving or predict-and-search. They target heterogeneous instances and come with no guarantee.

W2, Q2. Offline cost. We added the measured cost for every configuration (Table 15, Appendix N). Label generation takes 361 hours of solver time over the 23 configurations, from 0.29 hours (helicopter 15) to 86.8 hours (lane change 18). Calibration adds one score problem per calibration instance, and RCP also runs the repeated-solve procedure from several thresholds. We will add the measured training and calibration times to the final version. Counting label generation only and using CONFORMAL, the cost is recovered after about 5,500 online solves on school bus 18, 7,800 on obstacle 10, 9,300 on helicopter 75, and 20,000 on lane change 18.

W3, Q4. Distribution shift. We added a shift experiment on school bus (Tables 9 and 10, Appendix I). We perturb the home positions by Δ\Delta and keep the predictor and the threshold fixed. The ϵ\epsilon-optimality rate degrades, as expected, since the guarantee needs exchangeability. At n=18n=18, RCP goes from 98.8% to 87.0% at Δ=0.3\Delta = 0.3 and to 25.9% at Δ=0.5\Delta = 0.5, while its mean suboptimality grows from 0.04% to 1.12%. Recalibrating on shifted data needs no retraining and, in theory, restores the guarantee. We will add this experiment to the final version.

W4, Q3. Other values of α\alpha and ϵ\epsilon. We added α=0.01\alpha = 0.01 and 0.50.5 (Table 12, Appendix K) and repeated calibration splits (Table 13, Appendix L). On obstacle 10, CONFORMAL goes from 48.3% ϵ\epsilon-optimal at α=0.5\alpha=0.5 to 99.5% at α=0.01\alpha=0.01, and its mean solve time rises from 0.012 s to 0.42 s, against about 22 s for Gurobi. On lane change 18 at α=0.01\alpha = 0.01 the calibrated threshold fixes no variable, and the method reduces to the full solve. We varied α\alpha only.

W5. Fixed-structure families. This is true. The method needs one set of binary variables with a fixed ordering. We now state this in Section 2.3 and as a limitation in the conclusion. We added Combinatorial Auctions, a standard benchmark (Table 7, Appendix B.5): CONFORMAL reaches speedups of 77.5% to 87.1% with no infeasible instance.

W6, Q5. Tolerances and time limits. We added Appendix F. Calibration can use a solver lower bound in place of the exact optimal value and stay conservative. With the tolerances we used, our experiments certify the guarantee with ϵ=10−2\epsilon = 10^{-2} replaced by a value below 1.011×10−21.011 \times 10^{-2}. Solves that reach the 600-second limit carry no certificate, so the rates under that limit are empirical.

Q6. Retries in RCP. We added the mean and median number of retries (Table 14, Appendix M). The mean is below 2 everywhere and the median is zero in 19 of the 23 configurations. Retries cost time but leave most of the advantage: on obstacle 10 the speedup of RCP is 97.7%, against 99.4% for CONFORMAL, which returns no solution on 16.7% of instances.

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

This paper proposes conformal variable fixing for repeated mixed-integer optimization problems with a fixed structure and varying input parameters. A neural network predicts soft binary assignments, and an optimization-aware nonconformity score measures the minimum relaxation of these assignments needed to preserve at least one epsilon-optimal solution. Split-conformal calibration selects a fixing threshold, while a retry-aware variant (RCP) progressively releases fixed variables when the restricted problem is infeasible. Under exchangeable calibration/test instances, independence from the trained predictor, and exact optimization, the analysis establishes marginal epsilon-optimality coverage; the retry procedure also guarantees feasibility for originally feasible instances. Experiments on four synthetic problem families report substantial reductions in online solver time.

Critical strengths

Strength 1. The optimization-aware nonconformity score in Eq. (3) targets preservation of some epsilon-optimal solution, rather than agreement with one arbitrarily selected optimal binary assignment. This is a meaningful distinction in problems with multiple good solutions, and the score admits the explicit optimization formulation in Eq. (4).

Strength 2. The retry-aware formulation is conceptually clean. Enlarging the restricted feasible set ultimately recovers the original problem, and calibrating the output of the complete retry procedure is more appropriate than simply treating feasibility recovery as an optimality certificate.

Strength 3. The experiments report feasibility, epsilon-optimality rates, and solution time across several application domains, allowing some assessment of the speed–quality trade-off rather than reporting speed alone.

Critical weaknesses

Weakness 1. The evaluation tests only the same conditional instance distributions used for training and calibration, leaving generalization beyond the fixed environment unexamined. Section 3 and Appendix D explicitly draw training, calibration, and test instances from the same distribution conditional on fixed maps, home locations, and other family-level construction choices. However, it means the experiments do not test changed layouts, input-distribution shifts, or genuinely new problem environments. The school-bus setting makes the concern particularly concrete: the input is a finite binary attendance pattern while home positions are fixed; at n=10, there are at most 2^10=1,024 distinct input patterns but 7,200 training draws (Appendix B.4 and Table 2). Thus training duplicates are inevitable, and overlap with calibration/test inputs is plausible but not reported. Strong in-distribution results may partly reflect repeated decisions or memorization rather than reliable performance on new configurations. The empirical generalization claim therefore needs to be scoped much more narrowly.

Weakness 2. The benchmark suite does not establish applicability to more challenging or structurally diverse MILPs. All four evaluations use bespoke parametric families with stable variable identities and family-specific networks; the method assumes a fixed number and ordering of binary variables, h: Theta -> [0,1]^I. The paper does not evaluate common learning-to-optimize benchmarks such as Combinatorial Auctions (CA), Workload Appointment (WA), or a suitable structurally homogeneous subset of MIPLIB. These families would probe different coefficient patterns, constraint coupling, sizes, and difficulty profiles. That limitation should be acknowledged explicitly. Without such experiments or a compelling transfer study, broad applicability beyond the selected fixed-structure tasks remains unsupported.

Weakness 3. The reported speedups are based on comparisons with mismatched solution-quality and reliability requirements. The Gurobi baseline uses a 1% relative MIP gap tolerance, whereas RCP provides only a marginal ϵ\epsilon-optimality guarantee for the original problem. These criteria are not directly comparable, and the reported results show substantial differences in empirical ϵ\epsilon-optimality rates. Although the paper reports normalized suboptimality and ϵ\epsilon-optimality rates, it lacks objective values, absolute optimality gaps, and quality-matched time-to-target comparisons. Consequently, the reported speedups do not establish superior computational efficiency at comparable solution quality and reliability.

Weakness 4. The theoretical guarantees rely on exact optimal values and solver assumptions that are not established in practice. Computing the nonconformity scores in Eq. (4) requires the true optimal objective z⋆(θ)z^\star(\theta), whereas the experiments use reference solutions obtained with nonzero optimality tolerances. Substituting approximate objective values can underestimate the theoretical nonconformity scores, potentially invalidating the claimed coverage guarantee. Furthermore, the guarantees assume exact optimization of the restricted problems, while numerical tolerances and time limits are not explicitly accounted for. The dependence on exact reference optima and additional calibration solves also raises substantial scalability concerns. Consequently, the theoretical guarantees are sound under their stated assumptions, but their applicability to the implemented procedure remains insufficiently justified.

Questions for authors

Q1. Distribution shift, conditional environments, and repeated inputs. What happens if obstacle/island maps, school-bus home positions, or the input sampling distributions change after training and calibration? Please evaluate on new family-level configurations, explicitly distinguish recalibrated in-distribution performance from uncalibrated distribution shift, and report the number of distinct inputs and train/calibration/test exact-input overlaps in the school-bus experiments. How much performance remains on unseen input patterns and new layouts?

Q2. Standard and structurally diverse MILP benchmarks. Why are no CA, WA, or MIPLIB-based evaluations included? Please test on at least one or two more challenging families with meaningful changes in constraint matrices or variable coupling, and compare against established learned variable-fixing methods. If the fixed-dimensional soft-strategy representation prevents evaluation on heterogeneous MIPLIB instances, can the authors state this restriction clearly and evaluate a coherent family or structural subset instead?

Q3. Quality-matched solver comparison and actual objective gaps. Please report per-instance or distributional Obj and absolute primal gap relative to a clearly defined best-known/reference objective, in addition to the already reported normalized suboptimality. Can the authors plot objective-gap-versus-wall-clock-time and time-to-target curves for Gurobi, RCP, and FALLBACK under identical budgets? In particular, what happens when Gurobi is stopped as soon as it reaches the same empirical solution-quality target as RCP, rather than using the current 1% MIP-gap termination criterion? Please distinguish Gurobi's duality-gap certificate from epsilon-optimality measured against a stored reference objective.

Q4. Validity of the guarantee under numerical optimization. Which primal/dual bounds and solver tolerances are used to compute Eq. (4) and the retry-aware scores in Eq. (6)? If z*(theta) is unavailable, how are the estimated scores guaranteed to be conservative rather than underestimated? Can the authors provide a bound-based calibration construction or a rigorous numerical-error analysis, and clarify which claims remain certificates versus empirical observations under the 600-second time limit?

Q5. Scalability of the calibrated procedure. How many full MIP and auxiliary MIP solves, and how much total solver time, are needed to generate the reference labels and calibrate each problem family? How does this cost scale with the number of binary variables and the calibration size, and how many online queries are needed to amortize it? This is particularly relevant before claiming applicability to CA/WA-scale instances or larger MIPLIB families.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 1Wm9 (part 1 of 2)

Thank you for the detailed review. We uploaded a revised PDF. Table and appendix numbers below refer to it.

W1, Q1. Repeated inputs. You are right about school bus. We now report, for every configuration, the number of distinct inputs and optimal solutions and their overlap between training and test sets (Table 8, Appendix H). On school bus, 77% to 97% of test inputs also occur in training, so those results measure repeated decisions. In the other families no test input occurs in training, but optimal solutions can repeat: 92% to 99% of test optima on helicopter and 40% to 96% on obstacle avoidance. Lane change with n≥6n \ge 6 has almost no reuse (at most 0.4%). There the nearest-neighbor baseline is ϵ\epsilon-optimal on at most 14% of instances, while CONFORMAL and RCP stay at 79.9% to 84.7%. The auction instances with 150 and 200 items also have very little overlap.

W1, Q1. Distribution shift. We added a shift experiment (Tables 9 and 10, Appendix I). We perturb the school-bus home positions by Δ\Delta and keep the predictor and the calibrated threshold fixed. The home positions span an ℓ1\ell_1 diameter of 39. The ϵ\epsilon-optimality rate degrades, as expected, since the guarantee needs exchangeability. At n=10n=10, RCP goes from 100.0% to 95.4% at Δ=1\Delta=1 and to 0.4% at Δ=4\Delta=4. At n=18n=18 it goes from 98.8% to 87.0% at Δ=0.3\Delta=0.3 and to 25.9% at Δ=0.5\Delta=0.5, while its mean suboptimality grows from 0.04% to 1.12%. Many solutions cross the 1% threshold without becoming poor. Recalibrating on shifted data needs no retraining and, in theory, restores the guarantee. We will add this experiment to the final version. New maps or layouts require a new predictor, and we leave them to future work.

W2, Q2. Fixed structure and standard benchmarks. The method needs one set of binary variables with a fixed ordering. We now state this in Section 2.3 and as a limitation in the conclusion, together with the marginal nature of the guarantee. This excludes heterogeneous collections such as MIPLIB.

We added Combinatorial Auctions with the generator of Gasse et al. (2019), with 100, 150 and 200 items and five bids per item (Table 7, Appendix B.5, Figure 2). With 200 items and 1,000 binary variables, CONFORMAL fixes 64% of the variables, is ϵ\epsilon-optimal on 78.7% of instances, returns a feasible solution on every instance, and reaches a speedup of 87.1% (0.29 s against 2.44 s for Gurobi). Nearest neighbor is ϵ\epsilon-optimal on at most 1.5% of instances, so this is not memorization. Two caveats: these instances are easy for Gurobi, and at 100 and 150 items the constant predictor calibrated with our procedure does as well as the network. We did not have time to run Workload Apportionment.

For a learned baseline, we added the strategy-prediction method of Bertsimas and Stellato (Table 16, Appendix O). See our response to Reviewer AXjy (W1).

W3, Q3. Quality-matched comparison. We added absolute objective values and absolute gaps to Tables 3 to 7. We also ran Gurobi at relative gaps of 0.1%, 0.5%, 5% and 10% on obstacle 10, school bus 18, lane change 18 and auctions with 200 items (Table 11, Appendix J). The speedup of CONFORMAL against Gurobi at each of these gaps stays between 99.1% and 99.5% on obstacle avoidance, at 99.8% or more on school bus, and between 31.6% and 40.1% on lane change. On auctions Gurobi at a 10% gap is faster than CONFORMAL, but it is ϵ\epsilon-optimal on 0.2% of instances.

Table 11 also reports Gurobi with its gap set to the mean suboptimality of CONFORMAL. In this setting Gurobi returns better solutions than CONFORMAL (95.5% to 100% ϵ\epsilon-optimal), because its gap bounds the error on every instance while ours is an average.

A correction. While preparing these runs we found that the Gurobi row for lane change n=18n=18 in the submission (169 s) was inflated by CPU contention on our cluster. On the same instances Gurobi takes 28.1 s. The speedup of CONFORMAL at that size is 40.5%, not 92.3%, and that of RCP is 38.6%. We corrected Table 4, the text and Figure 2.

AuthorsOpenReview ↗

Response to Reviewer 1Wm9 (part 2 of 2)

W4, Q4. Guarantees under numerical tolerances. You are right, and we changed the paper (Section 3 and the new Appendix F).

Which tolerances. The reference values z⋆(θ)z^\star(\theta) are computed at Gurobi's default relative gap of 10−410^{-4} with no time limit. The 600-second limit applies only to the online evaluation solves. The score problems (4) need not be solved to optimality: any feasible point gives an upper bound on the score, and upper bounds preserve the guarantee (remark after Algorithm 1).

Bound-based calibration. Appendix F gives the construction you asked for. If the solver returns only a lower bound z~\tilde z on z⋆z^\star with relative accuracy τ\tau, we replace z⋆z^\star by z~\tilde z and ϵ\epsilon by ϵ(1−τ)\epsilon(1-\tau) in the score problem (equation (13)). Its feasible set is contained in that of (4), so the resulting scores are upper bounds and the guarantee holds as stated.

What our experiments certify. We used the incumbent value UU in place of z⋆z^\star, with relative gap τ=10−4\tau = 10^{-4}. A solution within ϵ(∥U∥+1)\epsilon(\|U\|+1) of UU is within ϵ+τ1−τ(∥z⋆∥+1)\frac{\epsilon+\tau}{1-\tau}(\|z^\star\|+1) of z⋆z^\star. So the guarantee holds with ϵ=10−2\epsilon = 10^{-2} replaced by a value below 1.011×10−21.011 \times 10^{-2}. The scores were not conservative as computed, and Appendix F now states this level.

Time limits. A solve that reaches the time limit carries no certificate. The rates we report under the 600-second limit are therefore empirical, and the theorems are statements about solves that terminate.

Q5. Offline cost and amortization. We added a table of the measured cost for every configuration, with the number of binary variables (Table 15, Appendix N). Label generation takes 361 hours of solver time over the 23 configurations, from 0.29 hours (helicopter 15) to 86.8 hours (lane change 18). Each configuration uses up to 9,000 instances (10,000 for school bus). Calibration adds one score problem per calibration instance, so at most 800 solves (1,000 for school bus). RCP also runs the repeated-solve procedure from several starting thresholds per calibration instance. We will add the measured training and calibration times to the final version.

Counting label generation only and using CONFORMAL, the offline cost is recovered after about 5,500 online solves on school bus 18, 7,800 on obstacle 10, 9,300 on helicopter 75, 11,000 on auctions with 200 items, and 20,000 on lane change 18. The method therefore pays off only when the same family is solved many thousands of times, which is the repeated-solve setting we target.

Thank you for the detailed responses and additional experiments. The revisions have addressed most of my concerns, particularly regarding data repetition, benchmark diversity, and numerical guarantees. However, some concerns remain, especially regarding the consistency between theoretical guarantees and practical implementation, as well as the fairness of solution-quality comparisons. Therefore, I will maintain my original rating.

Comments on the paper

1 comment
Area_Chair_WD63OpenReview ↗

Reminder: Reviewer–Author Discussion

Thank you to the reviewers who have already engaged in the discussion and provided valuable feedback. As the discussion deadline is approaching, I would kindly encourage the remaining reviewers to review the authors' responses and share their follow-up comments, particularly on whether their concerns have been adequately addressed.

Authors are also encouraged to respond promptly to any further questions.

Thank you all for your time and contributions to a constructive discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.