acceptodds
Under review as a conference paper at ICLR 2027

Learning-guided Infeasibility Relaxation for Mixed-Integer Linear Programming

Abstract

Real-world Mixed-Integer Linear Programs (MILPs) frequently face infeasibility. While recent learning-based methods accelerate MILP solving for feasible ones, infeasibility relaxation at scale remains a critical, unresolved bottleneck. To address this, we present L-IR, the first Learning-guided framework for accelerating MILP Infeasibility Relaxation. By formalizing relaxation as a constraint support set coverage task, L-IR learns to intelligently isolate the subset of constraints that, in hindsight, require relaxation and filters out the rest, yielding a reduced problem. Our L-IR is trained via a novel tripartite objective: a quality-weighted binary classification loss to learn multiple high-quality relaxations, a complete-support ranking loss to encourage early ranking of complete high-quality supports, and a coverage loss to dynamically truncate high-ranked subsets during inference. Architecturally, we introduce a constraint-centric geometric representation to explicitly capture conflict topology. Moreover, to address data scarcity, we construct a comprehensive benchmark of 20,000 infeasible MILPs across 580 problem classes. Extensive evaluations show that L-IR accelerates exact solvers by up to 6.08 while maintaining relaxation quality. We further demonstrate L-IR's strong generalization across varying relaxation hardness and unseen distributions.

Primary area:
optimization
Keywords:
Mixed-Integer Linear Programming, Infeasibility Relaxation, Graph Representation, Set coverage

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_NsaEOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes L-IR, a learning-guided framework for accelerating MILP infeasibility relaxation. A constraint-centric attention network ranks constraints and predicts an instance-adaptive candidate-set size. Slack variables outside this set are fixed to zero before solver optimization. Training combines quality-weighted classification, complete-support ranking, and coverage prediction using multiple reference repairs. The authors construct an LLM-assisted synthetic benchmark of approximately 20,000 instances across 580 classes and evaluate two relaxation objectives, reporting speedups over Gurobi and additional transfer results on MIPLIB.

Critical strengths
  1. The support-coverage formulation provides a coherent learning objective for infeasibility relaxation. Explicitly targeting the complete support of at least one high-quality repair addresses a limitation of independent constraint-level prediction and connects the training objective to the downstream optimization task.

  2. The paper provides a substantial benchmarking effort, including a large synthetic dataset, classical and neural baselines, two relaxation objectives, and component ablations. This offers a useful foundation for studying learning-guided infeasibility repair.

Critical weaknesses
  1. The evidence for practical generalization remains limited. The main results rely on synthetically injected conflicts derived from eight seed generators. ID evaluation shares generator classes with training, while OOD evaluation holds out a single GISP family. The experiments also use uniform violation penalties, leaving performance under application-specific relaxation priorities unclear. On MIPLIB, speedups are only 1.11–1.17×, and the constraint-count objective reduces the solved rate from 51.7% to 41.7%. These results leave uncertainty about how much of the synthetic performance transfers to practically representative repair tasks.

  2. The acceptance, fallback, and timing protocol is insufficiently specified. Success is defined relative to the unrestricted optimum, while fallback is triggered when the restricted repair fails the quality requirement. It is unclear how this decision is made online without knowing that optimum, how restricted solving and fallback share the time budget, and whether Gurobi and L-IR runtimes use matched solution-quality targets. These details are necessary to interpret the reported acceleration.

Questions for authors
  1. How is repair quality checked during inference without access to the unrestricted optimum? Please specify the information used to trigger fallback and how the restricted solve and fallback share the total time budget.

  2. Are Gurobi and L-IR timed against the same 10% solution-quality target? Please clarify their stopping conditions and the motivation for selecting this threshold.

  3. Which operational conflicts and relaxation priorities are the synthetic generators intended to represent? What evidence supports this correspondence, and how should the substantially smaller gains on MIPLIB be interpreted?

Reviewer_sospOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed L-IR, a learning-guided framework for infeasibility relaxation for MILPs. Specifically, a GNN is used to identify potentially important constraints, which will later be relaxed. The remaining constraints are then forced to be unchanged. The authors also introduced an LLM-based pipeline for generating synthetic infeasible MILP datasets.

Critical strengths
  1. The idea of predicting important constraints to relax is novel and sounding, which will significantly reduce the search space for the repair process.

  2. The proposed loss function for complete-support is well-motivated, which take dependencies among constraints into consideration, and utilize problem-specific information to enable high-quality relaxation support.

  3. The numerical results demonstrate remarkable performance gain on synthetic datasets, and ablation study is provided to show the effectiveness of the proposed framework.

Critical weaknesses
  1. The effectiveness of the synthetic dataset is not clear. Artificially introduce infeasibility into MILPs with specific mutation operators does not necessarily result in datasets comply to real-life problem distribution, which may be easily learnt by the model. The numerical result also complies with this concern, where L-IR only achieved 1.2x acceleration compared against 6x acceleration on synthetic dataset.

  2. The diversity of the dataset is not clear. The author claimed that 580 problem classes are mutated or permutated from 8 foundational families. This might also related to weakness 1, where the lack of diversity makes synthetic dataset too easy to be learnt.

  3. The novelty of the proposed framework, except the loss part, seems to be a simple accumulation of existing approaches.

  4. It is not clear if the fallback mechanism is actually feasible. It can be really hard to know if the predicted relaxation fails to meet the quality requirement. Especially for hard problems, where the optimal objective value cannot be obtained with acceptable time budget.

Questions for authors

Besides of those mentioned in weakness part, why is the ood test on synthetic dataset shows relatively worse performance? How is this enough to demonstrate the generalization ability? Besides, please justify whether this ood test is proper or not?

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

The paper proposes Learning-guided Infeasibility Relaxation (LIR), a framework for accelerating infeasibility relaxation for Mixed-Integer Linear Programming (MILP). Rather than allowing every constraint to be relaxed, the framework predicts a compact candidate set and fixes all remaining slacks to zero. A constraint-centric attention network jointly learns constraint scores and an instance-adaptive truncation ratio. The authors construct 19,628 infeasible instances across 580 generated problem classes. The experiments cover two relaxation objectives, synthetic in-distribution and held-out-family instances, and MIPLIB. The reported speedup reaches 6x on hard synthetic instances, with more modest gains on MIPLIB.

Critical strengths

The learning formulation addresses the structure of the repair problem. It predicts a candidate set that covers at least one complete high-quality support, which is better aligned with successful relaxation than independently classifying constraints. Proposition 2 shows this distinction, while the loss ablations and matched-budget coverage curves provide empirical support. This gives the method a clear technical rationale rather than applying a generic predictor to solver decisions. The paper combines a benchmark contribution with extensive validation. The generated dataset enables learning across hundreds of problem classes, and the evaluation includes classical heuristics, adapted neural baselines, two violation objectives, and component ablations. The large synthetic speedups, in particular on hard instances, it shows meaningful potential for the proposed reduction strategy.

Critical weaknesses

The operational quality check and runtime comparison are not enough specified. Section 4.2 invokes fallback when a restricted solution fails the quality requirement, while Section 5 defines success relative to the unrestricted optimum V^*. The optimum is generally unavailable during deployment, and an optimality certificate for the restricted problem does not certify quality relative to the unrestricted problem. It is also unclear whether Gurobi and L-IR stop at the same quality target, or whether Gurobi spends additional time proving optimality. It would be appreciable to specify an implementable acceptance rule, the allocation of the total time budget between restricted solving and fallback, and whether all preprocessing and verification costs are included. These details directly affect the interpretation of the headline speedups.

The evidence for broad practical generalization remains limited. The synthetic benchmark explicitly filters instances by relaxation time and the fraction of relaxed rows, favoring the sparse support regime targeted by L-IR. Its held-out-family evaluation remains within the generator’s seed-based construction. On MIPLIB, speedups shrink to 1.11x–1.17x; under the cardinality objective, the reported no-fallback high-quality success rate decreases from 51.7% to 41.7%. With only 23 and 20 evaluated instances and no uncertainty estimates for these gains, the evidence does not yet show broad claims of acceleration while preserving quality. The claims should be scoped accordingly, with paired runtime and quality results clarifying the practical tradeoff.

Questions for authors
  1. How is the decision to accept a restricted solution or invoke fallback made without access to the unrestricted optimum V^* ? Does the evaluation use precomputed reference optima for this decision ?
  2. Do Gurobi and L-IR have timed until reaching the same solution-quality target? How is the time budget shared between restricted solving and fallback and do the reported times include graph construction, prediction, and quality verification ?
  3. For MIPLIB, can you clarify the final high-quality success rates after fallback and provide paired per instance runtime and quality results from the existing runs ? These would help determine whether the modest aggregate speedups reflect consistent gains at comparable solution quality

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.