acceptodds
Under review as a conference paper at ICLR 2027

Learning to Allocate Solver Freedom: Adaptive Reoptimization for Mixed-Integer Programming

Abstract

Can correction signals learned on smaller mixed-integer programs (MIPs) guide reoptimization at million-variable scale? Given a feasible anchor, we learn which integer decisions to release and adapt the amount of solver freedom to each instance. We study this question through anchor-conditioned reoptimization. A quality–freedom frontier characterizes the tradeoff between attainable solution quality and the number of anchor decisions left free. A lightweight gradient-boosted decision tree ranks variables using structural, root-LP, and anchor-conditioned features; a cumulative-score rule selects the free set, and a MIP solver jointly optimizes the released variables and continuous decisions. We derive a correction-coverage bound under marginal correction probabilities and show why high partial recall alone cannot guarantee objective improvement. Across three structurally distinct MIP families, our method improves gap–time tradeoffs and reduces mean optimality gaps by 14%-94% on larger instances relative to matched-budget unrestricted solving. On MILPBench, family-specific predictors trained using feasible references on 20,000-40,000-variable instances transfer to problems with up to two million variables without target-scale retraining or retuning, achieving competitive objective values in 175–397 seconds of measured online runtime. The framework operates entirely on CPUs without GPU acceleration, providing a practical and scalable interface between learning and MIP solving.

Primary area:
optimization
Keywords:
Mixed-integer programming, learning for combinatorial optimization

Reviews

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

This paper studies anchor-conditioned reoptimization for mixed-integer programs (MIPs). Given a feasible anchor solution xAx^A, it releases a subset SS of integer variables, fixes the remaining integer variables to their anchor values, and lets the MIP solver jointly optimize the released integer variables and all continuous variables. The paper defines the restricted objective

z(S;xA)=min⁡x∈X(S;xA)c⊤x,z(S;x^A)=\min_{x\in\mathcal{X}(S;x^A)} c^\top x,

and introduces a quality--freedom frontier relating the best attainable objective to the number of released variables. A gradient-boosted decision tree (GBDT) ranks variables using static, root-LP, and anchor-conditioned features. The method then selects the smallest prefix whose predicted correction scores contain a fixed fraction ρ\rho of the total score mass, and solves the resulting restricted MIP. The paper also derives a marginal-probability coverage bound and gives a construction showing that high partial correction recall need not imply objective improvement.

The empirical study has two parts. Controlled experiments on Set Cover, combinatorial auctions, and capacitated facility-location instances use exact minimum-correction labels, several neighborhood baselines, and a development-selected cumulative-mass threshold. A separate MILPBench study trains family-specific LP-aware and NoLP GBDTs on easy-scale instances and evaluates them on medium- and hard-scale instances, including problems with up to two million variables. The reported results show favorable gap--time tradeoffs in the controlled setting and competitive objective values in the MILPBench setting. Overall, the method is coherent and practically motivated, but the central coverage bound is not calibrated or finite-time, the large-scale evaluation has only five test instances per setting and uses nonoptimal reference solutions, and some comparisons are not strictly end-to-end time matched. These limitations make the evidence insufficient for acceptance in its current form.

Critical strengths
  1. Feasible anchor-preserving reoptimization. Fixing variables to a feasible anchor preserves feasibility, while enlarging the released set cannot worsen the restricted optimum. This gives the learned policy a safe interface to an off-the-shelf solver: the model chooses where freedom is useful, and the solver still determines the released values.

  2. A practical adaptive-sizing study with reproducible artifacts. The controlled experiments include exact-label oracle references, fixed-budget curves, and an adaptive-versus-fixed sizing ablation. The supplementary code, frozen models, solver versions, and timing conventions make the work substantially easier to audit and reproduce than many learned-MIP papers.

Critical weaknesses
  1. The theoretical guarantee is not operationally informative for the reported method. Equation (19) depends on the unknown marginal correction probabilities qiq_i and the unmeasured score error

εout=∑i∉Sρ∣pi−qi∣.\varepsilon_{\mathrm{out}}=\sum_{i\notin S_\rho}|p_i-q_i|.

The paper explicitly states that this quantity is not estimated, and the resulting bound is often capped at one when the total score mass is large. Thus, the theorem explains the heuristic but does not provide a non-vacuous quality guarantee, a calibration result, or a finite-time solver guarantee for the reported GBDTs.

  1. The empirical evidence is too limited and not fully comparable to support the main transfer claims. Each MILPBench scale/family setting uses only five official test instances, reports means without uncertainty intervals, and evaluates objectives against reference solutions whose easy-scale gap estimates are approximately 4.1%, 10.3%, and 8.6% for the three families. In addition, EnCore-PS excludes graph construction, GPU inference, and early-solution generation from the paired timer, so it is explicitly not an end-to-end matched baseline. The default MILPBench feature set also contains raw instance-size features that are far outside the training range at hard scale, yet a scale-invariant ablation is not reported. These issues make it difficult to determine whether the observed gains reflect the proposed adaptive freedom allocation or protocol- and distribution-specific effects.
Questions for authors
  1. Uncertainty and paired statistics. Please provide per-instance results, confidence intervals or bootstrap intervals, and paired significance/effect-size analyses for all controlled and MILPBench tables. In particular, how stable are the six MILPBench conclusions when each setting contains only five test instances?

  2. Quality of MILPBench references. Which reported reference objectives are proven optimal, and which are only feasible solutions with a solver gap estimate? Please recompute the comparisons against a common high-quality or certified reference wherever possible, rather than interpreting objective differences from a nonoptimal xRx^R as optimality improvements.

  3. Selection of thresholds and gates. What exact development data and objective were used to select ρLP=0.96\rho_{\mathrm{LP}}=0.96, ρNoLP=0.825\rho_{\mathrm{NoLP}}=0.825, the exact-half threshold τhalf=0.5\tau_{\mathrm{half}}=0.5, and ϵ=10−6\epsilon=10^{-6}? Were the LP method, gate, and both thresholds frozen before any medium/hard test instance or test reference was inspected?

  4. Scale-invariant features. The MILPBench default representation includes n_vars, n_cons, and family indicators, while the hard-scale instances are much larger than the easy-scale training instances. Can you report a matched ablation that removes all instance-constant and raw-size features, together with the feature-range and score-distribution shift across scales? How does a tree model extrapolate when n_vars is outside its training range?

  5. Runtime and memory accounting. Please report the full online decomposition by scale and family: anchor generation, static feature construction, root-LP computation, GBDT inference, restricted reoptimization, peak memory, and total wall time. Also report the same pipeline with one and eight threads. In the controlled experiments, what would the conclusions be if static feature preprocessing were charged to the online budget?

  6. Strict end-to-end baseline matching. For every baseline, which stages are included in the reported budget, including incumbent generation, graph/feature construction, model inference, solver model construction, and solver setup? Since the paper states that EnCore-PS is not end-to-end time matched, can you provide a strict end-to-end rerun or remove it from claims based on matched budgets?

  7. Baseline tuning and implementation. How were Local Branching radii, RINS parameters, ACP schedules, Random-LNS partitions, and EnCore-PS schedules selected? Were all choices made on the same development instances and with the same solver/version constraints as the proposed method? Please specify which baselines were independently reimplemented and which used official code.

  8. Solver and anchor sensitivity. How do results change with the anchor budget, root-LP budget, root-LP algorithm, number of solver threads, and solver random seed? Do the gains remain when all methods are evaluated under a prespecified common end-to-end budget rather than a budget derived from the realized runtime of Ours?

  9. Score calibration and the cumulative-mass rule. Can you estimate qiq_i and εout\varepsilon_{\mathrm{out}} on held-out data, and report the numerical value of the bound in Equation (19)? How sensitive are release sets and objective results to monotone score transformations, probability calibration, or replacing cumulative mass with a ranking-only top-kk rule?

  10. Noise in reference-derived labels. MILPBench trains on DRD_R from feasible references with nonzero reference gaps. What is the label noise rate relative to a stronger teacher or exact minimum-correction labels on a tractable subset? Do multiple feasible references for the same anchor produce materially different correction supports and model rankings?

  11. Certification and stability of Dmin⁡D_{\min}. For controlled labels, how are optimality and nearest-optimum certification performed under solver tolerances? How often are there multiple nearest optima with different supports, and how stable are the labels under the objective tolerance used in the auxiliary problem?

  12. Scope beyond binary variables. The theory allows general integer variables, but most experiments use binary variables and Facility has only 100 binary facility-opening variables plus continuous recourse. What happens on instances with many nonbinary integer variables, general integer bounds, or mixed integer types? Is the Hamming release unit still the right computational cost proxy there?

  13. Reliability-gate robustness. Please provide sensitivity to the half-integrality tolerance, the rhalfr_{\mathrm{half}} threshold, LP solver/method, and small numerical perturbations of the LP solution. What are the per-instance results with the gate disabled, and how often does the gate switch paths for reasons unrelated to genuine loss of variable-level discrimination?

  14. Transfer contamination and auditability. Please provide an immutable manifest of training, development, and test instance IDs, seeds, threshold-selection runs, and all reference files used. Can you confirm that no test-scale labels, test references, test objective values, or post-hoc test outcomes influenced the model, gate, thresholds, or selection of the five reported test instances?

  15. Isolating the contribution beyond existing neighborhoods. Since the binary frontier F(k;xA)F(k;x^A) is the optimal radius-kk Local Branching neighborhood, which ablation isolates the incremental value of (a) the learned ranking, (b) cumulative-mass sizing, and (c) the anchor warm start? In particular, can you compare against a tuned adaptive-radius Local Branching policy under the same strict end-to-end protocol?

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

The paper studies anchor-conditioned reoptimization for MIPs: given a feasible anchor xAx^A from a short solver run, choose which integer variables to release (leave free), fix the rest to anchor values, and re-solve the restricted MIP. Contributions: (i) a quality–freedom frontier — F(k;xA)F(k;x^A) (the best objective reachable with at most kk free integer variables, equivalent to radius-kk Local Branching) and its inverse K(β;xA)K(\beta;x^A) — with the notion of minimum correction support Dmin⁡D_{\min}; (ii) a coverage result (Theorem 1) giving the sharp worst-case probability that a support is covered given marginal correction probabilities, plus an interpretation (Eq. 19) of a cumulative-score sizing rule and an analysis of why high partial correction recall alone cannot guarantee objective improvement; (iii) a practical policy: a 23-feature gradient-boosted decision tree ranks correction evidence per variable, a cumulative-score rule retains a fraction ρ\rho of total score mass to size the release set, and the same solver re-optimizes. Experiments: on controlled Set Cover/Auction/Facility families with matched wall-clock budgets against seven baselines (Local Branching, RINS, Random-LNS, ACP, EnCore-PS, Value-Fixing, unrestricted), the method achieves mean optimality gaps of 1.00%/0.44%/1.67% vs. 3.94%/1.02%/17.26% for unrestricted solving at medium scale, and frozen-transfer gaps of 0.87%/0.30%/4.84%. On MILPBench, family-specific GBDTs trained on 20–40k-variable instances with feasible-reference labels transfer to 1–2M-variable SC/MVC/MIS instances without retraining or retuning (gated LP-aware/NoLP models), achieving the best objectives among strictly matched-budget methods on the hard variants (e.g., hard SC objective 159,664 vs. ≥275,605 for matched baselines) in 175–397 CPU seconds; offline cost is small (26–36 min feature collection per family, under 13 s of GBDT fitting).

Critical strengths
  1. An unusually honest bridge between light learning and optimization theory. The frontier/Dmin⁡D_{\min} formalization, the sharp coverage theorem for marginal probabilities, the explicit statement that Eq. 19 is an interpretation rather than a certified guarantee (the discrepancy ϵout\epsilon_{\text{out}} is not estimated), and the recall-insufficiency analysis together provide principled grounding for learned incumbent-based methods. The observation that complementary variables make partial recall insufficient is a genuinely useful insight for the predict-then-fix literature.

  2. Practically significant scale results from a deliberately lean model. A 23-feature GBDT trained on small instances with merely feasible (not optimal) references transfers frozen to 1–2M-variable MILPBench instances — best matched-budget objectives on all hard settings in 175–397 CPU seconds, with seconds of offline fitting — directly addressing the deployability gap of GPU-heavy GNN/LNS pipelines, under a rigorous matched-budget online-time accounting protocol (Eq. 20).

Critical weaknesses
  1. The generalization scope is narrower than the headline framing suggests. Models, ρ\rho, and the LP/NoLP gate are family-specific, and transfer is a within-family scale-up under a fixed generator; cross-family or heterogeneous-instance transfer — the practically common case — is explicitly not established. This limits the impact of the "learning transfers to million-variable scale" story to a per-family training recipe.

  2. Thin margins and small evaluation sets in several settings. On MILPBench medium cells the matched-budget gains are small (MVC medium: 26,895.8 vs. 27,095.1 for ACP, with long-budget unrestricted better at 26,793; MIS medium: 23,081.3 vs. 23,154.3 for long-budget unrestricted), the large-scale results rest on five test instances per cell without variance reporting, and on Auction the absolute transfer gain is 0.05 percentage points. The "14–94% gap reduction" claim is well supported at the hard end but modest at the medium end, and its robustness is uncertain.

Questions for authors
  1. (Assessment) Are there any preliminary cross-family results (e.g., an SC-trained GBDT evaluated on MVC/MIS)? Even partial results would materially strengthen the transfer story; alternatively, the family-specific nature of the recipe should be stated more prominently.
  2. (Clarification) Please report per-instance objectives and variance for the five-instance MILPBench cells (Table 3), and the sensitivity of the results to the frozen thresholds ρLP=0.96\rho_{\text{LP}}=0.96 and ρNoLP=0.825\rho_{\text{NoLP}}=0.825.
  3. (Clarification) How were ACP and EnCore-PS configured and validated at 1–2M-variable scale, and how sensitive are the comparisons to their settings (EnCore-PS is not end-to-end time-matched)?
  4. (Clarification) The anchor budget is 0.5–1 s. How do conclusions change with moderately stronger anchors, which shift the correction-support statistics?
  5. (Suggestion, not blocking) Reporting GBDT feature importances would substantiate the "correction evidence" interpretation of the score.
Reviewer_DdEzOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper starts from a feasible MIP solution (the anchor). A GBDT predicts which integer variables should change, and the method frees the top-ranked ones until they hold a fraction ρ\rho of the total score. All other integer variables are fixed to the anchor, and the solver reoptimizes the restricted problem. The theory relates the number of freed variables to attainable quality and gives a coverage bound. Experiments on three small synthetic families and on MILPBench instances with up to two million variables show better gap–time tradeoffs than the baselines under the same time budget.

Critical strengths
  1. Simple and cheap. Fitting the predictor takes seconds once features are collected (Table 2). At million-variable scale, the pipeline is competitive with published learned methods at a lower reported runtime, and best on Set Cover (Table 9), although hardware differs.

  2. The adaptive sizing rule is well supported. In the runtime-matched ablation of Appendix E, adaptive sizing beats a fixed fraction matched to the same average size on Set Cover and Facility, and is close on Auction.

Critical weaknesses
  1. The theory adds little. The actual novelty is the GBDT ranking plus the score-mass sizing rule.

    • For binary MIPs, the quality–freedom frontier is the Local Branching value (l. 120–121).
    • Theorem 1 is a union bound.
    • The coverage bound (Eq. 19) depends on a calibration error that is never estimated. The paper calls it "an interpretation ... rather than a certified guarantee" (l. 226–227).
    • The bound is vacuous in all three controlled families even with perfectly calibrated scores: with the average correction densities in Fig. 2(a) and ρ=0.875\rho = 0.875, the term (1−ρ)PΣ(1-\rho)P_\Sigma is well above one, so the bound reduces to the trivial value 1.
    • On MILPBench, the training labels are the complement of EnCore's consistency labels for the same anchor–reference pair, as the authors note (App. H). The synthetic experiments use nearest-optimal labels instead, which is a genuine difference.
  2. At large scale, the experiments do not isolate the learned ranking. The large gains may come from fixing most variables, not from choosing which ones to fix.

    • In Table 3, several baselines stay at the same objective regardless of budget. Unrestricted Gurobi returns the same objective with the short and long budgets on SC medium and MIS hard.
    • No large-scale experiment releases a random set of the same size from the same anchor. Random-LNS is iterative and uses its own incumbent, so it is not this control.
    • Each setting has only five instances, and Tables 1 and 3 report means only.
Questions for authors
  1. On MILPBench, how does releasing a random set of the same size from the same anchor compare to your method? If it comes close, I would view the large-scale gains as a restriction effect rather than a learning effect.

  2. Why does unrestricted Gurobi not improve with a much longer budget on SC medium and MIS hard? The paper implies that the unrestricted solve is not warm-started with the anchor (l. 257–258). Were primal-focused settings (e.g., MIPFocus=1) tried?

  3. How is the MILPBench anchor obtained, and what is its objective? Please also report the anchor gap in Table 1.

  4. Was the root-LP reliability gate (App. F) designed before looking at the hard-scale test instances? If not, this conflicts with the claim of transfer without retuning.

Presentation:

  • The paper uses new terms for standard concepts. The "anchor" is the incumbent, and "solver freedom" is the number of unfixed integer variables, i.e., the neighborhood size. "Freedom" sounds broader than what is meant. Using standard MIP terms would make the paper easier to read for the optimization community.
  • The abstract presents running "entirely on CPUs without GPU acceleration" as an advantage. MIP solvers run on CPUs, and a GBDT does not need a GPU, so this is expected rather than a contribution.
  • The set P(q)\mathcal{P}(q) in Theorem 1 is unclear. I read it as all distributions over subsets of the index set with marginals Pr⁡(i∈D)=qi\Pr(i \in D) = q_i and no other assumption. Please say so explicitly. Also define q(j)q_{(j)} in Eq. (18), presumably the jj-th largest qiq_i.
  • GBDT is never spelled out as an acronym.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.