- 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
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.
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 whose rounding set contains the stored optimum . 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 , so both scores give the same results at the same threshold. The difference is the level they certify.
| Config | Score | fixed vars (%) | -opt (%) | time (s) | ||
|---|---|---|---|---|---|---|
| obstacle 10 | ours | 0.2 | 0.313 | 95.5 | 77.1 | 0.035 |
| obstacle 10 | stored optimum | 0.2 | 0.470 | 90.5 | 94.9 | 0.135 |
| obstacle 10 | stored optimum | 0.6 | 0.328 | 95.2 | 79.8 | 0.043 |
| helicopter 75 | ours | 0.2 | 0.369 | 99.5 | 82.7 | 0.020 |
| helicopter 75 | stored optimum | 0.2 | 0.423 | 99.4 | 96.3 | 0.029 |
| helicopter 75 | stored optimum | 0.4 | 0.266 | 99.7 | 77.3 | 0.021 |
| lane change 18 | ours | 0.2 | 0.484 | 39.9 | 80.3 | 12.6 |
| lane change 18 | stored optimum | 0.2 | 0.490 | 34.4 | 86.8 | 18.7 |
| lane change 18 | stored optimum | 0.4 | 0.477 | 44.2 | 71.0 | 10.9 |
To reach about 80% in practice, the simpler score must be calibrated at to , so it certifies only 40 to 60%. Calibrated at to certify 80%, it is -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 is one of possibly many -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.
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 ϵ-optimal solution at threshold δ exactly when its score is at most δ. Tuning to rate 1−α therefore selects the order statistic ⌈(1−α)n⌉ of the scores, and split conformal selects ⌈(1−α)(n+1)⌉. With n=800 and α=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 ϵ-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 ϵ-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 δ whose rounding set contains the stored optimum x⋆. 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 ϵ-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 ϵ-optimal more often than CONFORMAL and RCP at α=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 CONFORMAL is ϵ-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 and 0.5 (Table 12, Appendix K). At α=0.01, CONFORMAL is ϵ-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 the standard deviation of the held-out ϵ-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.