Learning-guided Infeasibility Relaxation for Mixed-Integer Linear Programming

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$\times$ while maintaining relaxation quality. We further demonstrate L-IR's strong generalization across varying relaxation hardness and unseen distributions.