Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
Authors: jiajun Li
Yixuan Li
Ran Hou
Yu Ding
Shisi Guan
Jiahui Duan
Xiongwei Han
Tao Zhong
Vincent Chau
Weiwei Wu
Zhiyuan Liu
Wanyuan Wang
Venue: ICLR 2026 Poster (2026)
Keywords: Mixed-integer Linear Programming
Learning to Optimize
Model Reduction
Primary area: optimization

Abstract: Model reduction, which aims to learn a simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for a subset of variables. From a dual perspective, constraint reduction that transforms a subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-based model reduction approach for MILPs. Constraint-based MILP reduction has two challenges: 1) which inequality constraints are critical such that reducing them can accelerate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we label the tight-constraints at the optimal solution as potential critical constraints and design an information theory-guided heuristic rule to select a subset of critical tight-constraints. Theoretical analyses indicate that our heuristic mechanism effectively identify the constraints most instrumental in reducing the solution space and uncertainty. To learn the critical tight-constraints, we propose a multi-modal representation that integrates information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-the-art MILP solvers, our method improves the quality of the solution by over 50\% and reduces the computation time by 17.47\%.

Published as a conference paper at ICLR 2026
CONSTRAINT MATTERS: MULTI-MODAL REPRESEN- TATION FOR REDUCING MIXED-INTEGER LINEAR PRO- GRAMMING
Jiajun Li', Yixuan Li', Ran Hou', Yu Ding', Shisi Guan?, Jiahui Duan", Xiongwei Han?, Tao Zhong", Vincent Chau', Weiwei Wu' Zhiyuan Liu', and Wanyuan Wang".
School of Computer Science and Engineering, Southeast University Huawei Noah's Ark Lab
"Corresponding author: Wanyuan (ang(wywang@ssuu.co
ABSTRACT
Model reduction, which aims to learn simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for subset of variables. From a dual perspective, con- straint reduction that transforms subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-baser model reduction approach for MILPss Constraint-band based MILP reduction has two challenges: 1) which inequality con- straints are critical such that reducing them can accelcrate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we label the tight-constraints at the optimal solution as potential critical constraints and design information theory-guided heuristic rule to select a subset of critical fight-constraints. Theoretical analyses indicate that our heuristic mechanism effectively identify the constraints most instrumental in reducing the solution space and uncertainty. To learn the critical tight-constraints, we propose a multi-modal representation that integrates information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-thee thetter MILP solvers, our method improves the quality of the solution by over 50% and reduces the computation time by 17. 17.47%.
INTRODUCTION
Mixed-integer linear programming (MILP) has been widely used to model combinatorial optimization problems, such as production scheduling (Pochet & Wolsey 2006), supply chain (Chao et al. 2024). energy management (Morales-Espaänn
al. 2013), and chip design (Wang et al. 2024). Existing commercial solvers (e.g., Gurobi and SCIP) are based on exact solutions, yet they are computationally expensive and fail to meet the real-time requirements of industrial applications (Morales-Espalie et al.) 2013: Li et al. 202T). Machine learning (ML), learning the relationship between the model structure and the value of the MILP solution, has become the most promising approach solving large-scale MILPs (Bengio et al. Zhang et al. 2023 Hentenryck & Dalmeijer] [024]. Model reduction. which aims to learn simpler model of the original MILP, provides a direct way to speed up MILP solving (Liu et al. 2024). For example, Ding et al. (2020a) and ahhnn et al. (2023) construct graph neural networks (GNNs) to predict a solution and fix a subset variables to reduce the dimension of the problem (Ding al., 2020a Liu al. 2025). The prediction results of partial variables can be used for smaller MIPs to build high-quality joint solutions (Nair et al., 2020 Yoon et al. 2023 or to
improve local branches in the branch and bound tree search (Ding et al. 2020a Li et al. 2018 or to identify feasible high-quality solutions efficiently (Han et (023). However, most approaches to MILP reduction are based variable reduction, overlooking constraint reduction.

---

Published as a conference paper at ICLR 2026
Based dual theory, constraints and variables are inherently coupled, and it is suggested that predicting and fixing constraints can also reduce search space. This paper proposes a novel constraint- based model reduction approach that transforms subset of inequality constraints into equality constraints. As shown in Figure [. only 5% of high-quality constraint reduction can significantly improve MILP solving performance. However, the naive reduction of inequality constraints may result in suboptimal or infeasible solutions. Therefore, the first challenge of constraint reduction to identify which inequality constraints are critical so that reducing them can speed up the MILP solution. Consequently, the second challenge is how to efficiently predict these critical constraints. Existing GGNN-baeed MILP representations focus on variable representation rather than constraint and lack the ability to predict critical constraints.
We first use the concept tight constraint from Op- erations Research (Boyd & Vandenberghe 2204). to determine which constraints should be reduced. Given an MILP instance, tight constraints are in- equality constraints that become equalities at the
500
Impeowement
Computation Time (s)
SCIP Improvement Joea
300-
Constralnt Reduction (Gurobll
Constraint Reduction (SCP)
Baseline (Gurob)
Baswine (SCIP)
100-
optimal solution. The set of tight constraints pro-
Scale Break
vides sufficient information necessary to achieve the optimal solution and thus is safe to reduce. However, predicting a high-dimensional vector of tight constraints is often challenging due to the complex combinatorial nature of MIIP, insuffi- cient training data, and limited model capacity. In this paper, instead of reducing all the tight con- straints, we only reduce subset of critical tight constraints, resulting in a significant acceleration. In particular, we select these tight constraints that can provide the highest information gain and effectively reduce the uncertainty of the problem. Theoretical results show that these critical tight constraints can greatly reduce the feasible region of solutions, thereby accelerating MILP solving. Due to the strong correlation between critical tight constraints and constraint categories, it is necessary to incorporate the category information into the representation. To this end, we present multi-modal representation that combines the abstract model with an instance-level model. The abstract model can capture MILP's high-level category information, so that the model can capture the structure similarity between constraints in the same category. Thus, this bi-level encoding provides more expressive and generalizable foundation for accurately identifying critical tight constraints.
0.5-
15
Proportion of Constraint Reduction (%)
Figure 1: The results of constraint reduction on computation time the CA_ CA_easy task, where the highest-quality constraints are selected.
The contributions of this paper summarized as follows. First, we propose novel constraint-basee model reduction framework, which predicts critical tight constraints and reduce the size of the solution space. Second, we introduce novel multi-modal representation that incorporates the abstract models into its instance model, which can accurately predict critical tight constraints. Finally, we conduct extensive experiments on large-scale MILP domains to validate the proposed constraint-basee model reduction method. Results show that our method outperforms the state-of-the art benchmarks by over 50% in solution quality (e.g., primal gap) and improves the computation time with an average 17.47%.
2 RELATED WORKS
Learning-based Model Reduction. Model reduction is direct approach reducing MILP size, thereby speeding up | solving. Extensive research has focused on variable reduction, which
predicts and fix a subset of variables to reduce the search space of solutions (Khalil et al. 2022
Paulus & Krause 2023 Zeng et al.) 2024; Chen et al., 2024: Geng et al., 2025). Fixing false- predicted
variables can sometimes lead to the infeasiblity of the original MILP problem (Ding et al. 2020b
Nair et al. [020 Chen et al. 2023). Instead of directly using the predicted solutions, threshold based
learning Yoon et al. (2023). local branching (Han et al. 2023; Huang et al. 2024a [iu et al., 2025).
and large neighborhood search (Sonnerat et al. 2021 Ye et al. 2023 2024) are proposed to guide the search for feasible solutions. In addition to variable reduction, a novel constraint reduction framework is proposed. [Bertsimas & Stellato (2022) and Li et al. (2024) have attempted to learn all tight constraints, from which the optimal solution can be obtained efficiently. However, the total number of tight constraints is very large, it grows exponentially with system size (Misra et al.
2

---

Published as a conference paper at ICLR 2026
2022). Predicting a high-dimensn sigh-dimensional vector of tight constraints is challenging. In contrast, this paper carefully selects a subset of critical tight constraints based on their contribution to reducing the local feasible space. In the specific domain of smart grids, PPorra et al. (2022); Park et al. (2023); Yang et al. (2020); Velloso & Van Hentenryck (2021) identify and remove redundant constraints (e.g.. flow constraints) to speed up the solution of the problem. In contrast, by defining the contribution of each type of constraints to the set of tight constraints, we propose general constraint reduction
approach.
MILP Representation. Effective feature extraction is crucial for learning- based approaches of MILP problems. Bipartite graph is a straightforward way to capturing the structural relationships
between variables and constraints (Khalil
2017; Selsam al., 2018 Gasse et al. 2019).
Chen et al. (022) theoretically shows that bipartite graphs can fully represent linear programming
problems, and with random features (Chen et al. 2023). GNNs can represent MILPs sufficiently. To capture connections among the variables, constraints, and the objective, Ding et al. (2020b) proposes a tripartite graph representation and embedding method. Moreover, EGAT-based methods (Ye et al.) 2024] Deng et al.) leverage edge features, offering more expressive representations. However, existing approaches focus on the representation of the MILP instance-level model, rather than the high-level abstract model that can provide uniform structural information among different instances.
THE PRELIMINARY AND OBJECTIVE
Mixed Integer Linear Program (MILP). The MILP can be formalized as follows:
min X s.t. A b and x x R"-",
(I)
where x = (Z1...., Fn.] is an n--dimnnsional decision variable consisting of integer variables and 9 continuous variables, E E denotes the vector of objective coefficients, A I@=x" denotes the constraint coefficient matrix, and b E R.m is the right-hand side of the constraints. This paper focuses on binary integer variables with E {0. 1 IR-4 which can be extended to general MILPs by encoding integers in binary (Nair et al., 2020). A drawback of this binary encoding is the potential increase in the problem's 's scale and a weaker resulting LP relaxation. For convenience, let I= (c, A, b) denote an MILP instance.
Tight Constraints and Fixing. Given an MILP instance I defined in Eq. ( let xx denote an optimal solution. constraint of the form a. x < by called tight at x² if a x= = b;; all other constraints are redundant and can be discarded (Boyd & Vandenberghe, 2004 In our reduction framework, fixing a constraint means turning a light inequality into an equality, i.e., replacing a, x < b, by a, b, in the reduced model. What's more. for prototypical constraint category C,, we say that this category is fixed when all its tight inequalities are transformed into equalities.
Model Reduction. Model reduction consists of variable and constraint reductions. Variable reduc- tion, which is used to predict subset of integer variables xy {0, 1)9, has been extensively studied (Han et al. 2023). The constraint reduction is to identify a subset of tight constraints and transform them into equality constraints, which can also reduce the search space of feasible solutions.
The Objective. Given a MILP problem, although different MILP instances are not the same, only the key parameters (c.g., c, vary slightly, and the structure remains unchanged. We can exploit the repetitive structure of the MILP instances and solutions and learn to solve unseen MILP instances. Therefore, our objective in this paper to learn the mapping from the parameter (c, A, b) to the reduced model intermediate step for MILP solving.
METHODOLOGY
The proposed model reduction framework comprises two phases: 1) Multi-Modal Representation to provide more expressive foundation for predicting critical tight constraint (i.e., Section 4.1); 2) Constraint- based Model Reduction for labeling Critical Tight Constraints (CTCs) (i.c., Section 4.2) The overview of framework is shown in Figure

---

Published as a conference paper at ICLR 2026
S Multi-Modu Representation
2
Tight Constraints Priority Module for Training Labels
Bescription ("ope" "dese"".d Mapp"" "oup"".. Edge: L.n)
Problems Semantka
c' A AEAKS Usssu. xE2 *
Absiract Medel
Inciantiaaion
mesvace
Caumater Type Gp S1
Coms
Type Paching
Covrrigg
n/(2" (12-=1)
Strongrh
n/(a +
Citiial Fight Constritony (CTC)
Alestificmnn by Printty
Fight
Packing
0C3/4/))
Not- Right
Kaagouck
003/A41)
Hor Sparr M8c.
Mors Space Reg
Sdieet Top within
Fillng GJ
peloitizzed topes
Pre-traind LM
Grach Commmaation
Insomiai
Message -Pasing
Bel//aal 1/2
JUDGE Module
Intraekayer
Priority
CTC
Gata
1o..I.1...........
Constraint Strength
Ranking Types by
CTC Identification
Detailee In
Higher (Absnooteve)
OSN
Training
@ Updaa
Prodlced Comsmnitt
Prodewd Karialer
ei d'r CACMCC and XXXX, x62
Inter-aye Message Possing
Xy,
V,
Zec
Constralor Search
Variable Soarch
Fa
Rodazak-medi walving
1
Solver SCIP
2 Bezeive
① Sood
X Model Reduction and Solving
Figure 2: An overview of our framework, which comprises three components: 1) Multi-modal representation, 2) Identification Critical Tight Constraints, and 3) Model reduction. 1), the textual semanties are first embedded as initial features for the abstract model, after which both the instance and abstract model are transformed into bipartite graph. In 2), a subset of tight-constraints is selected and labeled critical constraints. In 3), multi-modal representation and critical constraints are fed into the learning architecture in Section 4.1 to predict the reduced variables and constraints.
4.1 MULTIIMODAL REPRESENTATION
As shown in Gasse et al. (2019). a MILP instance can be represented as a weighted bipartite graph G = (C U V, E,) called instance model graph. This graph has constraint and variable nodes (C and V), with edges between them when a variable has non-zero coefficient in a constraint, and edge weights equal these coefficients. Please Appendix (Fo more information on the graph features.
For a class of MILP problems M, there exists a unified abstract model, represented as an unweighted bipartite graph 9m (C.. U Vm, Em) (the abstract model graph), as depicted in Figure 2 In this graph, nodes represent variable and constraint types, with an edge indicating that a variable type appears in a constraint type. The abstract model's 's textual descriptions, denoted as Tm. are converted into text embeddings using a pre-trained language model PLM(-). detailed in Appendix CC4]. These embeddings serve the initial features { } (LM(Tm) for the abstract model graph, where V denotes a category node corresponding
class of variables or constraints.
Prior work using Graph Neural Networks (GNNs) has focused on the coefficient matrix and structural properties of instance models G. overlooking high-level abstract model information. The identification of critical tight constraints is highly correlated with constraint categories, making category-level information essential for effective representation. To this end, we regard the abstract model as a modality of MILP, introduce it to capture high-level category information.
Specifically, our model comprises two key components: (1) Intra-Layer Message Passing (MP) and (2) Inter-Layer Message Passing. Intra-layer MP refers to independent message propagation within the abstract model graph (high level) and the instance model graph (low level). In contrast, inter-layer MP facilitates information exchange between the high-level and low-level graphs, enabling effective feature fusion across different levels of representation.
Intra-layer MP. In the intra-layer message passing stage, the high-level GNN operates on the
abstract model graph, incorporating text embeddings, while the low-level GNN follows the GNN framework proposed by Gasse et al. (2019). Let N(v;) Us E V: A * O. For convenience, we focus on a specific category node class Vy and its corresponding instance nodes v;, where ; E Vi denotes that instance node belongs to category node Vy. Hence, have
i V/3 = (()) (1145- (k-)) (()) ((11 (k-1)) 1) N()))))),
(2)
4

---

Published as a conference paper at ICLR 2026
(hh 1 1/ ((h f1 Sa ([h ((h0-1); :u ((i))))
((k
where function f1 is the neighbor aggregation function, while ((*) focuses on integrating neighbor information with the existing hidden features in the A layer. bi, denotes the higher GNN's features while (A) denotes lower GNN's features.
In the inter-layer message passing stage, this process consists of three phases: Sending, Receiving and Updating.
Inter-layer MP.
In the sending phase, for category node Vy in the abstract model, we extract the corresponding set of nodes {w:} from the instance model. Pross-AAtention (Bahdanau et al., 2014) is then applied
to achieve eross-modal fusion, resulting in instance-category features Ny, enhanced with instance model node features, which can be calculated by:
(((()) CrossAttention ( (LP(( MLP((()))) H)), 2 E Vg. V
In the receiving phase, category nodes Vj in the abstract model receive the instance-category features (ey obtained from Eq. 44. After concatenation, these features pass through MLP layer derive
new and more enriched category features R33
(.)K) MLP( (k) || (17))
(S)
In the updating phase, we represent the category features in the instance model with the average instance node features, ( mean (k) }), U2 E Vy. To balance the category features from both the instance and abstract models, we introduce a gating mechanism, which gets a dynamic weight for category features. Here, G-te(-) = MIP(()) Finally, we fuse the resulting category features with the node features the instance model (A()) to obtain a more comprehensive representation. The aforementioned computation can be formulated as follows:
a = Gate(hr (k) ((0)),
)
a [0, 1].
(6)
(k) + (1 - a a)) O h (R) = (ahi)) Rr
(R),
(7)
where @ denotes Hadamard product and || denotes concatenation. We conducted a complexity analysis of the model in the appendix. For details, please refer to the appendix
4.2 MODEL REDUCTION
Observation. We were curious about the absence of existing work on directly predicting and fixing con- straints to reduce model. Therefore, we conducted ex- periments to evaluate the effectiveness of this approach. We first introduce tight constraints, fixing them without affecting the problem's 's optimality. Then randomly fix tight constraints with ground truth values and it leads highly variable solving times across runs. Some cases solve much faster than direct solving, while others are slower. The results for toy datasets in Table showed in worst cases, it even severely deteriorated the solving time, which suggests that fixing different tight constraints has varying impacts solving acceleration. Based on the above experiments and related empirical evidence on ML-based prediction, we attribute the failure of directly predicting and fixing tight constraints to the following two reasons:
Table 1: We conducted motivation experi- ments via fixing different tight constraints on two datasets. Please refer Appendix H.] to see details of this experiment.
Time (s)
CA_easy
WA
Original
>3600
Best Fixing
1.851
50.726
Worst Fixing
465.74
>3600
(I) Critical Tight Constraints (CTCs), which are capable of accelerating the solving process, exhibit varying impacts due differences in the structural forms and functional roles of constraints.
(2) Selective Learning Bias. Neural networks often assign high confidence to simple constraints, which are typically non-critical, resulting in poor fixings and reduced solver efficiency.
Therefore, to leverage constraints for accelerating the solving process, we propose a method to identify and fix critical tight constraints addressing the two aforementioned challenges.
5

---

Published as a conference paper at ICLR 2026
Identification of CTC. In this paragraph, will introduce Tight Constraints Priority (TCP) an information theory-inspired heuristic module for identifying critical tight constraints and setting training labels. First, we select 10 of the 17 basic constraint types from MIPLIB (Gleixner et al.) 2021) as prototypical constraints (covering nearly all MILP constraint types), excluding equation constraints, logical constraints, and other less common ones. These 10 types shown in Table 2
Table 2: The 10 selected prototypical constraints and their estimated strengths. ~ indicates that the strength is hard to uniformly quantify and represent. See Appendix B.2 for the derivation.
Type
Expression
Strength (p)
Singleton
a single variable
Precedence
az ay S b, where x and y have the same type
Variable Bound
ar + by S c, (0, 13, Vi
1}
Set Packing
Σ 6,,
n/(n+ + 1)
Set Covering
,,,1,,46
n/ -1)
Invariant Knapsack
(
N22
O(1/V))
Bin Packing
Σ a,z; + or 50,,2, (0,1), N
O(1/A/n)
Knapsack
Σ 0, bb,, ( Vi,b (0,1), N22
0(1/A/n)
Mixed Binary
Ea, + Pjsj S b,,; E {0, 13, Vi, sj cont. Vj
General Linear
no special structure
Definition 1 (Local Feasible Space Sc,). For a prototypical constraint C₁ (a type of constraint) acting on a set of k variables Xc. == .I we define the Variable Domain Space as D. = I1 dom(x;)) (om(2));223 XC.. where dom(.) denotes the domain of a variable. Thus, we have:
fx ED; Cx(x) is satisfied)-
(8)
Here, "C²(x) satisfied" means that, for a given assignment x E DD to the variables Xc., all constraint conditions belonging the type C, are simultaneously fulfilled under x, i.e., none of the constraints in this category is violated.
Definition (Fixed Constraint Strength p). We use C₂ to denote the set of constraints after fixing the tight constraints in the constraint category Cj. We define the fixed constraint strength as:
|
((C.)
P [0.1]
[Sc,''
|-| denotes the size of a set. Hereinafter, p(C)) is abbreviated as p.
We detine the fixed constraint strength p in Eq. ( We note that this strength is primarily related to the structural form of the constraint. Therefore, we estimate its strength by analyzing the prototypical form of class of constraints. The inherent coupling of constraints in MILPs renders the analysis of their individual impacts intractable. We therefore introduce a local decoupling simplification. This positions theoretical framework principled heuristic guided by fixed constraint strength p. whose validity is ultimately corroborated by robust empirical results.
Proposition 3 (Entropy-Drivenn -rivenn Acceleration). Let P(Xc.TT) represent the probability distribution of the values taken by the variables acted upon by the prototypical constraint C.. Thus, we have assumption:
P(X,, = P(Cc. CC,1) ve P(Xc.C..),
(10)
where U denotes the influence noise of other constraint types in the instance I on the Xc, Therefore, suppose 110 holds We have the local information gain A AHc fixing C₁ as below:
AHc. = -loog
(11)
We interpret the feasible region of a MILP as a space of uncertainty, and fixing constraints can be viewed as process of entropy reduction. We have that a lower p value implies larger reduction in uncertainty, which in turn effectively shrinks the search space during solving and accelerates the process thicessthiissee partly demonstrates the validity of our heuristic method based on
For this Assumption, there is to show that the method admits favorable theoretical properties when the MIIP exhibits certain structural characteristies. Without these characteristics, our proposed method alsp remains effective, please refer Appendix H.7 for more discussion.

---

Published as a conference paper at ICLR 2026
Please refer Appendix[B.1 [B.1 for the proof. Therefore, identify critical tight constraints based on the pre-estimated strength prototypical constraints and the structural form of each constraint. Specifically, we prioritize constraints from categories with lower p. which significantly reduce the local feasible region, yielding high information gain A He; = log p for the problem. Next, we treat the tight constraints in these categories as critical tight constraints and conduct learning them. To maximize sample balance, we perform coarse-grained selection of critical tight constraints in TCP module. See Algorithm for TCP module details.
Model Reduction. Given MILP instance I belonging to problem class M. let & denote the parameters of our proposed network. The model generates predictions pe(c. M) to identify critical components. To handle predicted tight constraints, we introduce a hyperparumeter k2 to select the top-ranked constraints and trust region parameter Ag to allow for flexible adjustments. This trust region mechanism is crucial for mitigating potential infeasibility or suboptimality caused by prediction errors. For integer variable prediction and search, we follow the methodology proposed by Han et al. 2023). which is detailed in Appendix C.5
Specifically, we reduce the original MILP to the following formulation, where I, represents the set of indices for the ke selected constraints, M is sufficiently large constant (Big-M) and 2; {0, 1} are auxiliary indicator variables. In practice, this logic can also be efficiently implemented via the solver's native indicator constraints:
min s.t.
Ax S b,
a. x 2 b, - M2t,
ViE lo
(12)
Σ 2 Der
x E D n B(Xo, X1, A).
The rationale behind this reduction is that fixing (or penalizing the violation of) tight constraints preserves the original optimal solution x², x² inherently satisfies these constraints. By restricting the search space to a region that remains likely to contain x", we maintain the feasibility and optimality of the original problem while significantly reducing the computational burden. Even in the presence of prediction noise, the trust region A, ensures that the reduced feasible region remains a non-empty subset of the original space that is highly likely to retain the optimal guarantee.
Focal Loss. To mitigate the second bssuc-selective learning bias from the imbalance between easy and hard samples- we use Focal Loss (Lin et al. 2017) instead of Cross-Entropy Loss.
L aa ).)" log 0: + (1 o) y:) log(1 (c).
(13)
where Vi is the true label, is the predicted probability, is weighting factor for class balance, and ry is a parameter that adjusts the weighting of hard and easy samples. The following is our loss:
[()) A + (1 - Croe
Focal
(14)
where Coo denotes the Focal Loss for predicting variable assignments and Crom denotes the Focal Loss for identifying critical tight constraints.
EXPERIMENTS
In this section, to demonstrate the advantages of the proposed framework, we conducted com- prehensive computational studies on (i) solving performance, (ii) generalization ability, and (iii) compatibility with real-world scenarios. In addition, to verify the effectiveness of each component within the proposed framework, we conducted extensive ablation studies. Additional numerical results and implementation details can be found in the Appendix H
5.1 EXPERIMENTAL. SETUP
Benchmarks. Our evaluation carried out on four widely adopted benchmark datasets: the maxi- mum independent set (MIS), minimum vertex cover (MVC) (Albert Barabási 2002), combinatorial
7

---

Published as a conference paper at ICLR 2026
auction (CA) [Leyton-Brown et al. 2000), and workload appointment (WA) Gasse et al. 2022 problem. Specifically, the first two datasets (MIS and MVC) represent graph optimization problems, while the latter two (CA and WA) correspond to non- con-graph optimization scenarios. These datasets are widely adopted in (Huang et al. 2024a, Han et al. 2023; Liu et al., 2025; Gasse et al. 2019)
for henchmarking and empirical evaluation. A more detailed description of the datasets and their generation processes can be found in the Appendix(C
Baselines. In experimental setup, we consider the following baselines for comparison: (i) traditional solvers, including SCIP 8.0.1 (Achterberg) (209) and Gurobi 9.5.2 (Gurobi Optimization 2022). (ii) the Predict-and-Searcd (PS) method (Han et al. 2023), as described in Appendix C.5 and (iii) the Contrastive Predict-and-Search (ConPaS) method (Huang et al. 2024a), which is employed strong baseline to demonstrate the performance of our approach. It differs from PS in that it uses contrastive learning and leverages it to improve the quality of predicted solutions. For ConPaS, we set the ratio of positive to negative samples ten, using low-quality solutions as negative samples. By including negative samples in the training process, ConPaS can better distinguish between high-quality and low-quality solutions.
Metrics. We use the following metrics in the experiment: (i) Relative primal gap (Berthold 2006). which shows the difference between the primal objective value 2 and the best known objective value (BKS) z". It can be defined as (..2 e where e is a small positive value to avoid the numerical problem. We follow the setting in Han et al. (2023), running Gurobi single-thread for 3, 600 seconds to get 2". (ii) Absolute primal gap (called gapan.) the difference between the best objective found by the solvers and BKS, defined as gaPats = 12 2% (iii) The primal-duee dual integral (called PDI) (Berthold. 2013) is defined as the integral the primal-dual gap, with lower values indicating better |==2pl
|=-="|
convergence. Let aD be the dual objective bound, and the primal-dual gap is defined as gap = T=| Our method is model reducer: it takes an original MILP as input and outputs "simpler" reduced one. good reduced MIIP should help an off-the-shelf solver perform better, with better quality measured by faster convergence speed (via PDI) and higher solution quality (via gap).
Configurations. We conduct experiments on AMD Ryzen 9 9900X 12-Core Processor. All evalutions are performed under the same configurations We set MIPFocus for Gurobi and enabled the SCIP WWW.AMMETTIINNNGGGEESSSSS
mode for SCIP, both of which run in a single- thread. Following Han et al. (2023), we use 240 trainging, 60 validation, 100 testing instances. And for testing, we set the run time cut off to 800 seconds to solve the reduced MILP of each test instance. For more details, please refer to the Appendix G
5.2 EVALUATION RESULTS
To assess the efficacy of the proposed approach, we contrast the solving performance of our framework with that of the baselines, within time constraint of 800 seconds. Table provides a comprehensive overview of the experimental results from two dimensions. gapabs measures the solution quality, and PDI quantifies the overall convergence behavior of the optimization process. Overall, ConPaS slightly outperforms the PS in terms of solution quality, while the two methods exhibit comparable convergence speeds. Our proposed method surpasses both approaches in both solution quality and convergence speed. Across all methods utilizing Gurobi and SCIP, our proposed method achieves an average improvement of 51.06% in gap.b. and 17.47% in PDI over the berf-performing baseline.
In addition, Figure presents the evolution of the primal gap over time using SCIP, where faster decline in the curves reflects better solving performance. As shown in Figure 3 our method demon- strates more rapid decrease in the primal gap compared to other methods, highlighting its superior efficiency in solving MILP problems within the 800s time limit. Moreover, the primal gap of our method consistently outperforms those of the ConPaS and PS methods. We have also reported the experiments of all baselines based on Gurobi and hyperpapameters analysis in the Appendix H
To assess the generalization capability of our model, we further conduct evaluations on larger versions of the CA and MVC datasets. Detailed dataset scales and statistics are reported in the Appendix C.T The results are shown in Table 4 It can be observed that all machine learning-
Generalization.
8

---

Published as a conference paper at ICLR 2026
Table 3: Comparison of Different Methods Four Datasets (800s time limit). The last column shows our method's s improvement over the traditional solver (1 means lower is better). The best are in bold.
CA
MIS
MVC
WA
Method
guPas
gapas
goPas
guPas
Gurobi
477.51
76.29
2.70
33.09
8.38
68.02
0.20
4.76
PS+Gurobi
210.19
73.78
0.04
0.69
0.28
7.39
0.07
4.97
ConPaS+Gurobi
197.36
73.75
0.02
0.71
0.10
7.64
0.10
4,97
Ours+Gurobi
104.72
73.02
0.00
0.47
0.00
6.26
0.06
4,40
Improvement (%)
77.06%
98.58%
70.00%
4005.99
190.18
103.91
12.42
140.89
2.60
PS+SCIP
3575.18
179.48
0.66
6.49
2.98
21.03
1.27
34.85
ConPaS+SCIP
3545.92
1.20
Ours+SCIP
3401.63
109.41
0.34
4.65
1.48
18.34
0.83
21,52
Improvement (%)
15.08%
42.47%
91.83%
95.52%
88.08%
86.98%
68.08%
41.93%
based methods exhibit good generalization capabilities. Notably, our method continues achieve the best solution quality and convergence speed even in larger-scale generalization experiments.
SCIP
ConPaS+SCIP
10"5
Penar
10-
1012
10
10
405
8:0
420
800
400
420
300
(6)
(b)
(C) MVC
(d) WA
Figure 3: The relative primal gap (the lower the better) function of runtime, averaged over 100 test instances, within 800s time limits.
Real-world Scenarios. One limitation of our approach is its reliance on explicit mathematical models and problem descriptions, preventing direct evaluation standard benchmarks like MIPLIB (which often lacks such details), Instead, we use the real-world Middle-Mile Consolidation Network (MMCN) (Huang al. 2024b) assess its practical performance. As an alternative,
select the Middle-Mile Consolidation Network (MMCN) in Huang et al. (2024b). a set of real-world problem instances assess the practical performance of our approach. Please refer the appendix C.2 for the detailed information of this dataset. The solving results between baselines and our method on this dataset are presented in 5
Table 4: Generalization results on aarger-scale CA and MVC with SCIP within 800s across 100 test instances. I indicates that lower is better. The best are in bold.
Table 5: Results on the real-world dataset MMCN (Huang et al.) 2024b), using SCIP within 800s over 100 test instances.
CA
MVC
MMCN
Method
Method
gap
PDI
gapass
PDI
gapats +
PDI 1
SCIP
7009.58
198.78
22.07
228.21
SCIP
13819.90
427.63
PS
6541.87
169.86
4.07
39.63
PS
8084.36
329,60
ConPaS
6287.22
156.95
2.20
35.39
ConPaS
6064.85
330.05
Ours
5955.86
131.44
0.55
24.54
Ours
3547.08
246.89

---

Published as a conference paper at ICLR 2026
Ablation Study. better understand each compo- nent's contribution, conduct ablation study the CA dataset using SCIP (800s time limit, 100 test instances). First, ables/constraints ("w/o Multi-Modal") to highlight con- straint fixing effectiveness. Second, we use only multi- modal representation ("w/o Constraints") to show its contribution prediction. Figure shows outperform PS but are slightly inferior to our complete approach. Before the time limit, our multimodal repre- sentation consistently shows significant benefits, despite negligible gain at the end. For example, at 400s marked, our full method improves the primal gap by 12% over "wlo Multi-Modal". For more analysis on the "multi-modal representation", refer to Appendix H.5
w/o Constraints
w/o Multi-Modal
GNN to predict and fix vari-
Primal Gap
Ours
10-1
shows both variants
400
800
Figure 4: Ablation study results: the rela- tive primal gap as a function of runtime.
CONCLUSION
This paper proposes a constraint-based model reduction method by reducing both variables and constraints. There are two challenges for constraint reduction: 1) which inequality constraints are critical, and 2) how to predict these critical constraints efficiently. This paper first labels subset of tight constraints according to their contribution reducing the search space. Furthermore, multi-modal representation is proposed to encode both instance-level and abstract-level MILP, which fully capture the category information of constraints. Simulations real-world problems show that the proposed method has significant improvement computation time and solution quality.
7 ACKNOWLEDGEMENTS
This research was supported by National Key Research and Development Program of China (NO. 2024YFB4303805), the Key Research and Development Projects in Jiangsu Province (No. Noo.BE2221011 1001-2), the National Natural Science Foundation of China (Nos. 62476121). The work was collaborative effort jointly conducted by School of Computer Science and Engineering. Southeast University and Huawei Noah's 's Ark Lab. We appreciate the close collaboration, technical discussions, and shared resources from both teams that made this joint research possible.
10

---

Published as a conference paper at ICLR 2026
8 REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our research, we provide all necessary implementation details. The key source code has been uploaded as an attachment this submission. We further commit releasing the entire source code on public GitHub repository upon acceptance of the paper. The datasets used this study are publicly available, with detailed deseriptions, sources, and preprocessing steps provided in Appendix C.1 The specific experimental setup and computational resources are described in Section 5.1
All hyperparameter settings for our models are comprehensively listed in
Appendix and D
REFERENCES
Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computa- tion, 1:1-41, 2009.
Réka Albert and Albert-László Barabási. Statistical mechanies of complex networks. Reviews of modern physics, 74(1):47, 2002.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly 2014.
learning to align and translate. arXiv preprint
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
Timo Berthold. Primal heuristics for mixed integer programs. PhD thesis, Zuse Institute Berlin (ZIB), 2006.
Timo Berthold. Measuring the impact of primal heuristics. Operations Research Letters, 41(6): 611-614, 2013.
Dimitris Bertsimas and Bartolomeo Stellato. Online mixed-integer optimization in milliseconds. INFORMS Journal on Computing, 34(4):2229-2248, 2022.
Stephen P Boyd and Lieven Vandenherghe. Convex optimization. Cambridge university press, 2004.
Xiuli Chao, Stefanus Jasin, and Sentao Miao. Adaptive lagrangian policies for multiwarehouse, multistore inventory system with lost sales. Operations Research, 0(0):1-22, 2024.
Qian Chen, Tianjian Zhang, Linxin Yang, Qingyu Han, Akang Wang, Ruoyu Sun, Xiaodong Luo, and Tsung-Hui Chang. Symilo: A symmetry-aware learning framework for integer linear optimization. arXiv preprint arXiv:2409.19611 2024.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. arXiv preprint arXiv:2209. /2288, 2022.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing mixed-integer ab2/221
linear programs by graph neural networks, 2023. URL
10759
Yufan Deng, Tianle Pu, Li Zeng, Junfeng Kong, and Changjun Fan. Edge matters: A predict-and- search framework for milp based on sinkhorn-nomalized edge attention networks and adaptive regret-greedy search.
Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Accelerat- ing primal solution findings for mixed integer programs based on solution prediction. In AAAI'0., 20, pp. 1452-1459, 2020a.
Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Ac- celerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaai conference artificial intelligence, volume 34, pp. 1452- 1459, 2020b.

---

Published as a conference paper at ICLR 2026
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 competitions and demonstrations track, pp. 220-231. PMLR, 2022.
Zijie Geng, Jie Wang, Xijun Li, Fangzhou Zhu, Jianye Hao, Bin Li, and Feng Wu. Differentiable inte- ger linear programming, In The Thirteenth International Conference on Learning Representations, 2025.
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg. Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data- driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443-490 2021.
Lacy Greening, Mathieu Dahan, and Alan L Erera. Leadd-iim--consrraneed middle-mile con- solidation network design with fixed origins and destinations. Trunsportation Research Part B: Methodological, 174:102782, 2023.
LLC Gurobi Optimization. Gurobi optimizer reference manual, 2023, 2022.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. arXiv preprint wwx.iv:3322006633 2023.
Paseal Van Hentenryck and Kevin Dalmeijer. A14OPT: Al institute for advances in optimization. Al Mag., 45(1):42 -7, 2024.
Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Contrastive poddict-and-searde for mixed integer linear programs. Forty-first International Conference on Machine Learning, 2024a.
Weimin Huang. Taoan Huang, Aaron M Ferber, and Bistra Dilkina. Distributional miplib: multi- domain library for advancing ml-guided milp methods. arXiv preprint arXiv:2406.06954 2024b.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Elias Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10219-10227, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14X2v.1412.6998 2014.
Kevin Sayton-Brown Mark Pearson, and Yoav Shoham. Towards a universal test suite for combina- torial auction algorithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pp. 66-76, 2000.
Xihan Li, Xiongwei Han, Zhishuo Zhou, Mingxuan Yuan, Jia Zeng, and Jun Wang. Grassland: A rapid algebraic modeling system for million-variable variable optimization. In CIKM'2I, pp. 3925-3934, 2021.
Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, and Wanyuan Wang. Fast and interpretable mixed-integer linear program solving by learning model reduction. arXiv preprint arXiv:2501.00:: 000307 2024.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In NeurlPS' 18, pp. 537-546, 2018.
12

---

Published as a conference paper at ICLR 2026
Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pp. 2980-2988, 2017.
Chang Liu, Zhichen Dong, Haobo Ma, Weilin Luo, Xijun Li, Bowen Pang, Jia Zeng, and Junchi Yan. L2p-mip: Learning to presolve for mixed integer programming. In The Twelfth International Conference on Learning Representations, 2024.
Haoyang Liu, Jie Wang, Zijie Geng, Xijun Li, Yuxuan Zong, Fangzhou Zhu, Jianye Hao, and Feng Wu. Apollo-milp: An alternating prediction-correction neural solving framework for mixed-integer linear programming. ICLR 25, 2025.
Sidhant Misra, Line Roald, and Yeesian Ng. Learning for constrained optimization: Identifying optimal active constraint sets. INFORMS J. Comput., (4(1))463-44) 2022.
Germán Morales- Essaiaa, Jesus M. Latorre, and Andres Ramos. Tight and compact milp formulation for the thermal unit commitment problem. IEEE Transactions Power Systems, 28(4):4897-490s 2013.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' Donoghuue Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang. et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012./3349 2020.
Seonho Park, Wenbo Chen, Dahye Han, Mathieu Tanneau, and Pascal Van Hentenryck. Confidence- aware graph neural networks for learning reliability assessment commitments. IEEE Transactions on Power Systems, 39(2):339-38800 2023.
Max Paulus and Andreas Krause. Learning to dive in branch and bound. Advances in Neural Information Processing Systems, 36:34260-34277, 2023.
Yves Pochet and Laurence A Wolsey. Production planning by mixed integer programming, volume 149. Springer, 2006.
Álvaro Porras, Salvador Pineda, Juan Miguel Morales, and Asunción Jiménez-Cordero. Cost-driven screening of network constraints for the unit commitment problem. IEEE Transactions Power Systems, 38(1):42--38) 2022.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1 1-,7 2020.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv: 10084, 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning sat solver from bin supervision. arXiv preprint
2018.
Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201,
2021.
Alexandre Velloso and Pascal Van Hentenryck. Combining deep learning and optimization for preventive security-constraiee constrained de optimal power flow. IEEE Transactions on Power Systems, 36 (4):3618-3628 2021.
Zhihai Wang, Lei Chen, Jie Wang, Yinqi Bai, Xing Li, Xijun Li, Mingxuan Yuan, HAO Jianye, Yongdong Zhang, and Feng Wu. A circuit domain generalization framework for efficient logic synthesis in chip design. In Forty-first International Conference on Machine Learning, 2024.
Yan Yang, Zhifang Yang. Juan Yu, Kaigui Xie, and Liming Jin. Fast economic dispatch in smart grids using deep learning: An active constraint screening approach. IEEE Internet of Things Journal, (1) 1030-11040, 2020.
13

---

Published as a conference paper at ICLR 2026
Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. Gnn&gbdt con&gddt-guided fast optimizing framework for large-scale integer programming. In International conference on PMLR, 2023.
machine learning, pp.
Huigen Ye, Hua Xu, and Hongyan Wang. Light-milpopt: Solving large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset. In The Twelfth International Conference on Learning Representations, 2024.
Taehyun Yoon, Jinwon Choi, Hyokun Yun, and Sungbin Lim. Threshold-aware learning generate feasible solutions for mixed integer programs. arXiv preprint arXiv:2308.0032)) 2023.
Hao Zeng. Jiaqi Wang, Avirup Das, Junying He, Kumpeng Han, Haoyuan Hu, and Mingfei Sun. Effective generation of feasible solutions for integer programming via guided diffusion. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4107-4118, 2024.
Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205 217, 2023.
14

---

Published as a conference paper at ICLR 2026
A
THE USE OF LARGE LANGUAGE MODELS
Large Language Models (LLMs) were utilized to assist in generating the JSON text required for this work and to support writing revisions. Specifically, we leveraged LLM,, providing it with detailed deseriptions of the relevant problems and corresponding mathematical models, along with specified output formats, to generate the JSON content we needed. Additionally, the LLM aided in tasks such as refining language expression, enhancing text readability, and ensuring clarity in various sections of the paper, including sentence rephrasing, grammar checking, and improving the overall textual flow.
It is important to note that the LLM was not involved in the ideation, research methodology, or experimental design. All research concepts, ideas, and analyses were developed and conducted independently by the authors. The contribution of the LLM was solely focused on aspects related to text generation and linguistic polishing, with no involvement the scientific content or data analysis.
The authors take full responsibility for the entire content of the manuscript, including any text generated or polished by the LLM. We have ensured that the text produced with the assistance the LLM complies with ethical guidelines and does not lead to plagiarism or scientific misconduct.
B THEORETICAL PROOFS
B. PROOF OF PROPOSITION
3
According to the Maximum Entropy Principle, we define the distribution P(Xc; (T) as the uniform distribution over all variable assignments permitted by constraint C.. And based on Assumption 10 we have:
1
P(Xa, ~ C()) =
Scc
P(Xc, (T) P(Xc((()==
(15)
|Sc,
where 1' denotes the instance after fixing the tight constraints the constraint category C.. Thus:
AHc. = H(P(Xc (')) - ((((Xc, ())
H(P(Xc; (a)) H(P((x,(.))
(16)
log (1Sa.) + log (1Sc.))
(17)
Therefore:
|Sc,
AHc. = log
log
(18)
|Sc,
B.2
PROOF OF FIXED STRENGTH FOR 10 PROTOTYPICAL CONSTRAINTS IN TABLE 2
B.2.1
SET PACKING
For Set Packing Σ S 1, (0, 1), Vi, we can easily have |Sc. n + 1, 1,18c, = n. Therefore,
Sc. p Sc.
n n2 + 1
B.2.2 SET COVERING
Consider the Set Covering constraint Σx, with x, E (0.1) = n. The number of feasible combinations before fixing is Scc,1 = 2 - 1, excluding the all-zero vector. After fixing the constraint to Σ x; = only n combinations remain, corresponding to vectors with exactly one non-zero entry. Thus, the fixed constraint strength is:
p
2
15

---

Published as a conference paper at ICLR 2026
B.2.3 INVARIANT KNAPSACK
Consider the Invariant Knapsack constraint defined as Dim1 Ty b, where z; E {0, 1} and b N22. The total number of feasible solutions is given by
Sc.
Σ k=0
12
k
which corresponds to all binary vectors of length with Hamming weight most b. Among them, the tight feasible region, where the constraint is exactly satisfied, i.e., Lim 1 24 = b, so we have
Se =
Therefore,
[ Sc,
p =
Σk=o k=0
We analyze the behavior of p under regimes. First, when achieves its maximum. Using Stirling's approximation, we obtain
2. the binomial coefficient (%)
n/2
2
2n
n1/2)
TT\22
2
k
which yields
2
Tn/2
2
= 0
2n-1
VTn/2
Vn
Second, when 6 ~ vn, the summation in the denominator has at most b + 1 terms, each upper bounded by (k). This implies
n k
(b+1)))))
S (bb
=
p2 b+7
= Ω
vn
1
Therefore, in both cases we conclude that
p=
indicating that the relative size of the tight feasible region decays with increasing n. Hence, the fixing strength based on tight solutions for the Invariant Knapsack constraint is asymptotically weak.
B.2.4 KNAPSACK
Consider the classic Knapsack constraint of the form Σx= A&TR < b, where I& E {0, 1} and aş > 0. To ensure the constraint non-trivial and informative, we assume the right-hand side is set near the mean of the total weight, i.e.,
Σ ak
b~ μ
b is too small, the fcasible region may collapse; too large, the constraint becomes inactive. Thus, setting ~ y corresponds to the regime of maximal informativeness.
Assuming that each 24 is an independent Bernoulli random variable with success probability 0.5, the total weighted sum
X
16

---

Published as a conference paper at ICLR 2026
is sum of independent random variables. By the Central Limit Theorem, for sufficiently large n, the distribution X approximates a Gaussian:
1 n
X X~ N
aks 0² =
2
Fixing the constraint (i.e., foreing the inequality to hold at equality or within a small margin) corresponds to conditioning X to lie within a narrow band around for instance:
X E [1 6, 6].
where 5 is small positive constant. The probability mass within this interval under the Gaussian approximation provides estimate of the tightness ratio p. given by:
put6
(r-u) 20
28
dx S
4-8 v V2TO
This yields the upper bound:
p p=
V ai
If the weights ag have average magnitude A (i.e., ag A), then:
nA² = 0= 1
0K
AVn
k=
In the most informative regime where b ~ the tightness ratio p of the Knapsack constraint decays at least as fast as Ol)/vn), and potentially faster depending on the weight magnitudes. Thus, similar to the Invariant Knapsack, the Knapsack constraint also becomes asymptotically weak increases.
B.2.5 BIN PACKING AND MIXED BINARY
Both Bin Packing and Mixed Binary constraints share similar mathematical forms with general Knapsack constraints, typically expressed as Σ ax-T S 6 with binary or partially binary variables. Overall, Bin Packing's p values can be considered of similar magnitude to Knapsack constraints. However, for Mixed Binary, considering that there are some continuous variables, it is difficult to analyze them, and generally do not consider fixing them.
B.2.6 OTHERS
Constraints such as Singleton. Precedence, Variable Bound, and General Linear are challenging to quantify uniformly. In this work, we generally do not take these constraints into account.
C DETAILS ON THE BENCHMARKS
In this section, we will introduce the benchmark problems. For the CA problem, there are two types of constraints that structurally similar; however, the average number of variables in the second type is significantly smaller than in the other. This results in smaller fixed strength p. leading to more effective reduction in the solution space, and thus choose to fix this type of constraint, For the MIS and MVC problems, which involve only one type of constraint, our approach also remains effective and demonstrates superior performance. In the case of the WA problem, since only the first constraints includes binary variable, we opt for this type of constraint.
C. DATASET DETAILS
Table shows the relevant scale information of the benchmark used in our paper. For the CA and MIS datasets, generated them using the method in Gasse et al. 2019). Specifically, used
17

---

Published as a conference paper at ICLR 2026
algorithm in Leyton- Brown et al. (2000) with 2,000 items and 4,000 bids to generate CA instances. For the MVC dataset, we generated the instances according to the Barabasi- Albert random graph moodel[Albert & Barabási (2002), with 4,000 nodes and average degree of 5 subsequently. The WA dataset is token from the NeurIPS 2021 MI.CCO competition Gasse et al. 2022), which also includes an item placement (IP) dataset that is often employed in the field. We, however, chose not IP as it predominantly consists of equality constraints, with a scarcity of tight constraints, thus making it unsuitable for our method.
Table 6: The average numbers of variables and constraints of the benchmarks we used in this paper.
CA
MIS
MVC
WA
MMCN
Binary Variables
4000
6000
4000
1000
7441.34
Continuous Variables
0
0
60000
529.37
Constraints
2675
25549
19975
64306
6385.27
We generated CA and MVC datasets of larger scale verify the generalization ability of method. Specifically, for the CA dataset, we used the same method to generate instances with 3,000 items and 6,000 bids. For the MVC dataset, we generated instances with 6,000 nodes and an average degree of 5.
For the training data collection, We use Gurobi to run for 3600 seconds, saving 50 solutions along with their corresponding tight constraint sets as labels. Notably, the time cost for collecting tight constraint labels consistent with that of collecting solution labels alone, without introducing any additional time overhead. Additionally, during both training and testing, performing constraint prediction and reduction simultaneously incurs no extra time cost.
C.2 REAL-WORLD DATASET
The Middle-Mite Consolidation Network (MMCN) problem is network design challenge that focuses on developing load consolidation plans for transporting shipments from stocking points-such vendors and fulfillment centers-to last-mile delivery destinations. The objec- tive is to determine minimum-cos allocation of transportation capacity across the network ares, while ensuring that all shipment lead-time constraints are satisfied. The detailed mathe- matical model can be found in Greening et al. (202)). Taking into account both the computa- tional difficulty and the model scale, we opted for MMCN Very-hard-BC2, which is available for download on the httes: http:///sttessett http::::://siiee..oglllleeeeeeee com usc edu di st butbuutoon 1-miimmmme p ib/ middle mile wwwsolinoi..ooo..co wwtesooldaaiin dddiiinnnnnnnoo wwwiioonnnetwtoo network des s gn (Huang al. al.) 2024b). We also use 240 trainging, 60 validation, 100 testing instances, keeping other settings unchanged.
C.3 PROBLEM MILP FORMULATIONS
In the CA problem, given n bids (()., i E [n]] for yn items, where B; is a subset of items and Ps is the bidding price for B,, Sy denotes the substitutable bid group for bidder ks where E and we want to allocate items to bids such that the total revenue is maximized:
min
iE(n]
s.t. Σ Iz S 1,
Vj E [m],
BjEB
Σ
< 1,
Vi [4]
KES;
24 (0, 1),
Vi E in].
In the MVC problem, given undirected graph G = EV. with weight w. associated with each node v E V. we want to select a subset of nodes V' C V with the minimum sum of weights such that at least one end point of the edge is selected in / for any edge in F:
18

---

Published as a conference paper at ICLR 2026
min
WoZv
vEV
S.t. + Ty 2 1, v(u, E,
Ie {0,1}, V
In the MIS problem, given an undirected graph = (V, E), we want to select the largest subset of nodes V V such that no nodes in the subsets connected edge in G:
min Σ Te
VEV
s.t. Tu + To I 1, v(u,v) E E,
Te {0,1), V
In the WA problem, let T denote the set of workers, indexed by i E and J denote the set of workloads, indexed by j E J. For each workload j E let Aj C represent the subset of workers that are eligible process workload j.
Each worker i E is associated with an activation cost C; E R and a processing capacity C. E Rt. Each workload j E J requires processing demand of dj R... The cost incurred for reserving unit of capacity on worker for workload, j is denoted by Mi E R4 U (+o), where %ij = too if i Aj, indicating that such an allocation is infeasible.
The decision variables are defined as follows: 2; E {0, 1}3 indicates whether worker is activated (z; 1) not (x; = 0), and Vij E RR represents the amount of capacity reserved on worker for workload j. The objective is to minimize the total cost of worker activation and capacity reservation, subject capacity constraints, assignment feasibility, and robustness against single-worker worker failures. The resulting mathematical model is formulated follows:
EGN ΣΣ
min
Tiglig
iET JEJ
s.t.
Vij S Cari
WEI, VjEJ
Σ Vij S Ci
WET
JEJ
Σ ykj 2 dj.
Nj VIEI
(ET(()
Viÿ 0,
J, Vi
E {0.1].
WEE
Vi 0,
C.4 PROBLEM TEXT DESCRIPTIONS
Due space limitations, we only present the JSON-formated representations of the textual descrip- tions of problems. For the specific textual content of some problems, we employed large language models (LLMs) for generation. Concretely, we supplied the LLM with detailed descriptions of this category of problems as well as the relevant mathematical models, and defined the output format to generate the content we required. The complete content can be found below:
Listing 1: Example JSON Description for the CA Problem
braask_descriptiie "variable_type"
"The Combinatorial Auction (CA) task is a ...",
"x":
"type": "binary",
19

---

Published as a conference paper at ICLR 2026
"Gescription": "The variable indicates whether bid ...", "index"; "x_i",
"range": "[0, 11", "constraints"; "For cach bid i, x_i is binary
"constraint_type".. {
13
"Item Allocation Constraint";
"type": "Linear, inequality, leq, SetPacking",
"esccription: "Constraint c_j ensuring that each item ...",
index"; "c_j (j n_items )",
17
expression"; "sum(x] for in bids) 1 ...., "constriint"; "For each item ), the sum of x_1
,,
"Susstitutable Bids C
21
22
23 },
"edges":
("source": "0", "target": "0"),
26
"source"; "0", "target": "1",,
er
"source"; "O", "target": "2"]
In addition, for the pre-trained language model, we selected T5-base. Considering efficiency, we also experimented with some other lightweight language models, such Sentence-BERT Reimers & Gurevych (2019). However, we did not find any significant differences. The more influential factor turned be the training process. Therefore, did not conduct further attempts in this regard.
C.5 BASELINES INTRODUCTION
Predict-and-Search Predict-and-Search (PS) is ML-based framework, which consists of two parts, predict and search. During the prediction phase, PS learns the Bernoulli distribution of the solution values through a GNN network, and get the probability pe(x; []) for each binary variable, where I the MILP instance. Subsequently, based on the marginal probabilities, PS greedily selects kn binary variables Xr and fixes them to O, and selects k binary variables X; and fixes them to 1. In the searching phase, through the hyperparameter search, PS employs traditional solver, such as SCIP or Gurobi, to search in the neighborhood ( X1, A) = {x Ex.ex, I; >E; (1 - x;) < A}. where B(X, X,, A) is called the trust-region. The above neiborhood search process can be formulated the following MILP problem:
which determines the range of the neighborhood
min T s.t. Ax b, I. E D B(X,, Xi, A);
(19)
where D denotes the original feasible region of the MILP. Note that, when A = 0, PS degenerates into Neural Diving Nair et (2020) (Nth(without selectiveNet).
D ALGORITHM
In this section, present the pseudo-code of the TCP module, which is identify and select critical tight constraints for a class of MILP, in the algorithm [ In addition to selecting based on fixed strength p. maintain stability and effectiveness during training, strive to keep critical tight constraints at relatively balanced proportion. Specifically, we uniformly set Amin 5 and [81, Bz] [0.1. 0.8). It should be noted, however, that this does not require strict configuration.
E COMPLEXITY ANALYSIS
GCNN For the GCNN proposed by Gasse et al. (2019), the neural network comprises single graph convolution layer followed by an output layer. The graph convolution consists of two half- convolutions (variable-to-coonstrait and constraint-to-variabee where each edge is processed by
20

---

Published as a conference paper at ICLR 2026
Algorithm TCP Module: identify and select critical tight constraints
Input: Set of constraint categories C, Fixed constraint strength o JUDGE(.) in Algorithm 2 Output: Selected constraint categories C".
1: Sort C. using {pt)
(=0= Csorted = Sorl(c)
2: Initialize: C = (}. tight_count couht_ = O, total count =
3: for C. in Ceorted do
4: = C
5: if JUDGE(C) then
6: CC
7: else
8:
return C
9: end if
10: end for
11: return () (No subset found that meets the criteria)
Algorithm 2 JUDGE
Input: Constraint set C, Minimum number Ammins Acceptable proportion [31,02] 1: Initialize: tight_count count = 0, total _ooutt
2: for C in C do
3: tight fociittccuuttt = tight_cou Sight_count- + TightComs umm
4: total count total_ coultt Constraint. Numttrainttuum(CCC
5: if tight feritt_ouuntt_e 2 Mmin and 3 S (tight_count coount/tottllcoee total count) S 3g then
6: return TRUE
7: else
8: return FALSE
9: end if
end for
two-layer perceptrons, incurring a complexity O( d²). Updates to constraint and variable nodes contribute O(JCI - d²
|V]- dd), but since | >> [C), this is dominated by O(E) df). The output layer applies a two-layer perceptron to variable nodes, with complexity O[V] - which subsumed by the graph convolution as [V| < E.. Thus, the total computational complexity is O(EE) . dd).
Our model Compared previous GNN models, the time complexity of model primarily increases due to the addition of higher GNN and Inter-Layer MP. We assume that the abstract graph contains N category nodes, while the instance graph consists of instance nodes, On average, each category node corresponds to de instance nodes, and the feature dimension is d. Since the number of abstract graph nodes N < n, higer GNN's computational cost negligible. For Inter-Layer MP, according to Eq. (4) the computation complexity is O(n dl + N d² + n d N dd). Because of d D des the complexity is approximately O(n d²) and the bottleneck of this process the operation. Therefore, after considering the underlying GCNN, the total complexity O(n d' + |E (d).
F DETAILS ON BIPARTITE GRAPH REPRESENTATION
In this paper, basically the same features those in PS Han al. (2023) to characterize the instance bipartite graph. Specifically, we also add position embedding to the constraints. The specific features shown in the Table 7
21

---

Published as a conference paper at ICLR 2026
Table
Features embedded bipartite representations.
features.
name
description
normalized coefficient of variables in the objective func- obj
tion
v_coeff
average coefficient of the variable in all constraints degree of variable node in the bipartite representation maximum value among all coefficients of the variable minimum value among all coefficients of the variable
Nv_coeff
Variable
max_ max_coefi coeff
min_ min_coeff
int
binary representation to show if the variable is an integer variable
12
pos_ jos_emb
binary encoding of the order of appearance for each vari- able among all variables.
c_coeff
average all coefficients the constraint
Ne_coeff rhs
degree of constraint nodes in the bipartite representation
Constraint
right-ham hind-side value of the constraint
sense
the sense of the constraint
Edge
coeff
coefficient of variables in constraints
G HYPERPARAMETERS
G.1 TRAINING PARAMETER
All evalutions are performed under the same configurations. For the training of the model, uniformly set the learning rate as 10-3 with Adam optimizer (Kingma & Ba 2014). the batch size as and the max epoch as 150, although models typically achieve convergence within 50 to 100 epochs. Regarding the parameters of the Focal Loss, we keep them consistent with the conclusions in Lin for MIS and MVC. And we set the balancing weight of the final loss À = 0.4 in Eq. (14) for all benchmarks. For the pre-trained language model used in text embedding, considering efficiency, we choose T5-base (Raffel al. 2020))
al. (2017) and set 0.75, 7
G.2 NEIGHBORHOOD PARAMETERS
We report the neighborhood Parameters for all baselines with Gurobi in Table
Table 8: Hyperparameters (ko, ki, A) for PS and ConPaS; (ka, K1, A,kic Ad) for ours.
Benchmark
CA
MIS
MVC
WA
PS
(1200, 0, 20)
(1200, 600, 20)
(600, 100, 10)
(0, 550, 10)
ConPas
(1200, 0, 20)
(1200, 600, 20)
(600, 200, 20)
(0, 500,
Ours
(1000, 0, 10, 80, 15)
(600, 600, 5, 800, 1)
(000,200,20,1000, 1)
(0, 550, 10, 10000, 1)
H ADDITIONAL EXPERIMENTAL RESULTS
H.1 MOTIVATION EXPERIMENTS
We conducted motivational experiments on toy datasets, CA and WA. Specifically, we only fix the constraints without performing any other operations. Because full enumeration of all possible combinations would be computationally infeasible, we chose to test 20 combinations selected based empirical observations. To illustrate, in the case of the CA problem, noticed that fixing constraints with fewer variables generally results a faster solution. Consequently, to construct test sets, began by sampling constraints that involved the fewest and the most variables and
22

---

Published as a conference paper at ICLR 2026
then randomly created combinations to be fixed during the solve. We show the results of 8 of these combinations in the table
Table 9: the results of 10 of these combinations of CA.
C1
C2
C3
C4
C5
C7
C8
Cg
Time
1.85
332.72
465.74
15.49
98.44
370.51
51.57
84.01
Avg var num
3.0
21.2
34.2
9.2
14.8
24.1
12.1
14.8
The Table T shows the average solving time across 30 instances under different operations. Here, "Original" denotes the initial solving time. Based on our experience and findings, we evaluate different combinations of n distinct constraints, identifying the fastest solution as the "Best Fixing" and the slowest as the "Worst Fixing". For CA_easy, 10, and for WA, 3000. And for the CA easy dataset used here, there are on average 600 constraints and 1,500 variables.
H.2 COMPARSION WITH GUROBI
In this section, we supplement the experimental results of baseline with Gurobi.
Main Evalution In Figure 5 we have shown the relative primal gap as a function of runtime for CA. MIS, and MVC. As can be seen from the Figure among the ML-based methods using Gurobi across multiple benchmarks, our method still able to achieve the best solution quality and convergence speed. For the datasets, MIS and MVC, since the solutions obtained by method are better than those obtained by Gurobi after 3600 seconds of solving, the solutions obtained by our method are taken as the Best Known Solutions (BKS). In this regard, for the primal gap, we have truncated it to minimum of 1 x 10 in the figure. Since the WA instances solved by Gurobi can rapidly reach objective values comparable to the BKS (Best Known Solution), the figure in Figure [ fails to effectively illustrate performance disparities. Therefore, we deliberately omit the presentation of Gurobi-basee WA results in this context.
Gurobi
Purobii
ConPaS+Guroon
Ours Ours+Gurobi Gurobi
10-1
10
10-2
-0
10
Primat
10-2
10
10
10-4
10
10-1
10-a
10
101
800
400
(a) CA
(b) MIS
(c) MVC
Figure 5: The relative primal gap (the lower the better) based Gurobi function of runtime, averaged over 100 test instances, within 800s time limits.
Real-world Datasets Here, we report the Gurobi results for the real-world dataset MMCN in the Figure As shown as figure, our method also outperforms all the baselines on the real-world dataset, which demonstrates that our method exhibits excellent performance when using different solvers.
H.3 HYPERPAPAMETERS ANALYSIS
In this section, we explore the effect of the neighborhood parameter hyperparameters on CA dataset based Gurobi. (Kn, Ki, A) have been studied numerous times in previous works. Here, we focus on studying (ktg, Ae) which is a crucial hyperparameter that has significant impact in our work. The results shown Table IO We observe that as the value of k. increases, the error rate of neural network predictions also increases, leading to a degradation in solution quality. However, the convergence speed shows certain degree of improvement.
23

---

Published as a conference paper at ICLR 2026
10
Gurebi
10
PS
175
Prima Gap
10
Ours
Conpas
Primal Integral
150
125
10
10
75
50
10
10
Gurabi
Ps
Conpas
Ours
400
800
Run time in Seconds
Figure 6: The left: the relative primal gap (the lower the better) based Gurobi as a function of runtime, averaged over 100 instances, within 800s time limits on the real-world datasets. The right: the primal-dual integral (PDI) at 800s runtime cutoff based Gurobi. The error bars represent the standard deviation.
Table 10: Performance of different fixed constraints.
Gurobi
SCIP
(kies A.)
gapabs
PDI
gapabx
+
PDI L
(10, 0)
492.78
74.88
3945.76
111.03
(20,
109.57
73.07
3401.63
109.41
(40, 5)
375.73
73.56
4270.87
114.64
(50, 5)
228.69
73.52
4054.70
108.69
(80, 15)
104.72
73.02
3485.82
108.23
(100, 20)
161.81
73.41
3673.37
109.11
(120, 25)
217.94
73.98
4535.83
110.73
Additionally, taking the CA instances as example, Table demonstrates how solver performance degrades with different fractions of incorrectly fixed constraints. "N/A" denotes problem infeasibility and we randomly choose three CA instances.
Table 11: the results of solver performance degrades with different fractions of incorrectly fixed constraints
CA12
CA20
CA25
Incorrectly Fixed
Time(s)
Objective
Time(s)
Objective
Time(s)
Objective
0%
154.47
24543.48
163.58
25055.95
79.31
24181.19
2%
137.58
24325.03
199.99
24810.55
107.05
23564.07
5%
37.80
23358.41
11.14
23891.44
108. 18
23445.82
10%
4.96
22160.16
23.93
23516.66
N/A
N/A
20%
N/A
N/A
N/A
N/A
N/A
N/A
30%
N/A
N/A
N/A
N/A
N/A
N/A
In this experiment, we begin with fixed set of correctly identified tight constraints (5% of tight constraints). We then introduce varying proportions of non-tight (i.e., incorrectly fixed) constraints this set. The resulting degradation in solver performance is then measured by the solution time and the final objective value.
H.4 PRESOLVE ABLATION STUDY
To quantify the interaction between the learned model reduction and the solver's presolve, conduct a presolve ablation study on the MVC and CA datasets using Gurobi. Unless otherwise stated, Gurobi run with presolve disabled; we then explicitly enable presolve top of each reduction variant.
24

---

Published as a conference paper at ICLR 2026
Table 12: Presolve ablation on MVC and CA. Lower gap and PDI indicate better performance.
Method
MVC gapabs
MVC PDI
CA gaPabs
CA PDI
Gurobi
8.38
68.02
565.61
76.78
presolve
7.44
72.31
477.51
76.29
PS
0.28
7.39
420.47
78.20
presolve
0.20
8.28
210.19
73.78
Ours
0.00
6.26
410.58
77.29
presolve
0.00
4.56
104.72
73.02
Table 12 reports the average absolute optimality gap (gapat.) and PDI on both datasets for: vanilla Gurobi, Gurobi with presolve, the classical reduction baseline (PS), and our learned reduction, each with and without presolve.
From Table 12. we make three observations:
1. Combining our learned reduction with presolve yields the best overall performance on both datasets, indicating that the two mechanisms are complementary rather than conflicting.
2. Under the same solver configuration. the learned reduction consistently achieves better solution quality than the presolve method.
3. For vanilla Gurobi as well as for both reduction methods, enabling presolve consistently improves performance, confirming that presolve remains beneficial even in the presence of strong model reductions.
These results highlight the actual contribution of the learned reduction and show that it can be effectively combined with standard presolve techniques to further improve solver performance.
H.S ANALYSIS OF MULTIMODAL REPRESENTATION
In Figure 4 there is little discernible gain precisely at the Time Limit. However, before reaching the time limit, our multimodal representation consistently demonstrates significant benefits. For example. at the 400-second mark, method achieves 12.0% improvement in the primal gap. In Table 13 we show the loss and the prediction accuracy constraints for our multimodal model.
Table 13: the training metrics of our multimodal model. ACC K means the accuracy of constraints when K% of tight constraints need to be fixed.
loss
AC'var
ACC@10
ACC020
ACC&50
ACC@100
ours
1246.3
99.31% %
93.13% 90.37%
84.84% 80.62%
66.41 %
64.30%
GNN
1263.8
98.80%
66.37%
64.31%
Moreover, in the main experiments, we use the T5-base model as the text encoder. To assess the sensitivity of approach to the choice of pretrained language model (PLM), further replace T5-base with the stronger OpenAl text-ennee cexxt-embeddiio Seobbeddinn---- -oeddinnn---ll- 3-large model (called OpenAl Embed)
The comparison is summarized in Table 14
As shown in Table 14 switching from T5-base to OpenAl text- -ewpxxt-emedding------- -rragge leads to only marginal improvements loss, absolute gap, and PDI. This suggests that the overall performance is not particularly sensitive to the specific PLM. A key reason is that, compared with the relatively coarse sentence-level embeddings produced by PLMs, the MLP used to align PLM embeddings with the GNN representations plays a more critical role, effectively mitigating the influence of the PLM choice itself.
"W keep the intermediate feature dimension unchanged and leave all other settings identical to those in the original Gurobi-based experiments.
25

---

Published as a conference paper at ICLR 2026
Table 14: Effect of the pretrained language model the Gurobi-basee experiments in CA dataset.
PLM
Loss
gaPaba
PDI
b5-base
1246.3 1232.1
104.72
73.02
OpenAI Embed
103.33
72.96
H.6 TRAINING TIME CONSUMPTION
In this section, since we have employed more complex model, we report the training duration per epoch of our model compared that of the naive Graph Neural Network (GNN) multiple datasets.
Table 15: Per-epoch training time (in seconds) for PS (naive GNN) and our model on different datasets.
Dataset
PS (GNN)
Ours
CA
9.7
23.1
MIS
66.5
148.4
MVC
60.2
122.6
WA
242.4
358.9
H.7 DISCUSSION ABOUT ASSUMPTION
10
To assess the practical validity the local decoupling assumption, we conduct an additional empirical study the same MILP benchmarks used in the main paper, including CA, WA, and the real-world dataset MMCN.
Empirical evidence on realistic datasets. For each instance,
1. group constraints into prototypical types (Set Packing, Set Partitioning, Knapsack, General Linear);
2. for every constraint, compare (i) the distribution of its activities and (ii) the marginal distributions of incident variables under solutions of the full model, and solutions of type-only local model that retains only constraints of that type, implied by the local decoupling assumption.
We use the Wasserstein distance (WD) constraint activities and the mean absolute enror variable marginals (VarErr) to measure the distributional discrepancy between the two solutions. A constraint is counted satisfying the local decoupling assumption under given metric if WD 0.25 (for activities) or VarErr < 0.15 (for marginals).
The averaged statistics over 40 instances summarized in Table 16
Key observations. We highlight several observations from Table 16
On CA, substantial fraction of Set Packing constraints (40.1% 11 by WD and 58.3% by VarEmr well approximated by the corresponding type-only local model, even under this deliberately strict setting.
. On MMCN2, the highly structured types that our theory focuses on behave particularly well:
all Set Packing constraints are perfectly matched in variable marginals (100.0% satisfy- ing VarErr with very small average error);
most General Linear constraints exhibit solution distributions that closely approximate those the global model.
These results indicate that, in realistic instances, large and structured subset of constraints precisely the prototypical types emphasized by our thcoretical analysis analysis-satisfeee satisfies the local decoupling assumption to meaningful extent.
26

---

Published as a conference paper at ICLR 2026
Table 16: Empirical validation of the local decoupling assumption on realistic MILP benchmarks. "Satisfied (WD)" and "Satisfied (Var)" denote the fraction of constraints whose activity distributions and variable marginals, respectively, are well approximated by the corresponding type-only local models.
Dataset
Constraint Type
Satisfied (WD)
Satisfied (Var)
Avg WD
Avg VarEmr
CA
Set Packing
40.1% %
58.3%
0.334
0.148
MMCN
General Linear
25.7%
87.3%
91.096
13.330
MMCN
Set Packing
18.5%
100.0%
0.758
0.063
WA
General Linear
49.9%
11.2%
0.379
0.360
WA
Mixed Binary
8.2%
7.4%
0.685
0.328
Moreover, in practice we observe that the constraints selected to be fixed by our reduction procedure are exactly those exhibiting smaller gap between (i) the distributions implied by the local decoupling assumption and (ii) the empirical distributions estimated from data. This is consistent with our analysis that constraints better satisfying the assumption are more suitable to fixed. For datasets such as WA, where these gaps generally larger and constraints appear more strongly coupled, the performance gains brought by our method are indeed smaller than on other datasets, further reinforcing the alignment between theory and empirical behavior.
Role of the assumption. The local decoupling assumption used as a local analytic device derive the entropy-based ranking over constraint types. not required for the feasibility or correctness of the reduction procedure itself, but rather serves to motivate why certain prototypical types (e.g., Set Packing / Set Partitioning) are expected be more informative. The overall method remains heuristic in nature, and its effectiveness is ultimately validated by empirical evidence such as that presented above.
I LIMITATION AND FUTURE WORK
This paper proposes a constraint-based model reduction method by reducing both variables and constraints. There are two challenges for constraint reduction: 1) which inequality constraints are critical, and how to predict these critical constraints efficiently. Specifically, we introduce the concept of critical tight constraints and develop heuristic algorithm to identify them. To address the challenges of representing variables and constraints, we leverage an abstract model of the MILP problem to enable multi-modal representations. However, limitation of our approach is its reliance on prior knowledge of the specific MILP formulation. Furthermore, the heuristic search for critical tight constraints may not always be sufficient. In future work, aim develop more general and principled method for identifying instance-level critical tight constraints.
27


Reviews:
[{"review_id": "W720uBnvgs", "reviewer": "Reviewer_ajfo", "summary": "This paper proposes predicting tight constraints to perform constraint reduction in MILP problems, effectively accelerating MILP solving. To better predict tight constraints, in addition to the existing bipartite graph representation, the paper introduces an abstract-level representation of MILP and a TCP module.", "questions": "1. When the lower or upper bounds of constraints in MILP problems are no longer 0 or 1, how does the proposed constraint reduction method handle such cases, and how does this affect performance in practice?\n2. Could the paper provide experimental results on more complex real-world problems (such as those from MIPLIB)? For a real-world problem of an unknown type, how is its text description obtained?\n3. How significant is the performance impact when using different pretrained language models?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Every component proposed or used in the paper is well-motivated.\n2. The definition and use of the fixed constraint strength $\\rho$ are quite interesting.", "weaknesses": "1. Introducing a pretrained language model and the abstract-level GNN will bring additional computational overhead.\n2. I have doubts about Theorem 4. If an error occurs during the process of fixing constraints, would the resulting problem become infeasible, or would its optimal value differ from that of the original problem?\n3. In Table 8, I noticed that the hyperparameters used for different problem types vary significantly. This implies that for a new type of problem, the proposed method would require manual hyperparameter tuning. I would like to know how sensitive the method’s performance is to these hyperparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B38tPahMmt", "reviewer": "Reviewer_Ni7m", "summary": "This paper presents a novel framework for accelerating Mixed Integer Linear Programming (MILP) solving by introducing the concept of Critical Tight Constraints (CTCs) — a subset of constraints that are most influential in determining the final optimal solution. The key idea is that by identifying and reducing redundant or weakly active constraints, one can substantially decrease solver time without compromising solution accuracy.\n\nTo efficiently identify CTCs, the authors design a novel framework that combines multi-dimensional MILP representation learning and constraint-level embeddings with pretrained language model (PLM) augmentation. This hybrid modeling enables the system to capture both structural and semantic relationships among constraints. Once CTCs are identified, the solver performs targeted reduction to simplify the MILP instance before solving. Extensive experiments conducted on large-scale MILP benchmarks, using Gurobi as the backend solver, demonstrate significant runtime reductions while maintaining high solution fidelity.", "questions": "1. It would be helpful to include a sensitivity analysis of the hyperparameter Δc, which controls the constraint search or reduction threshold. This experiment could clarify how robust the proposed method is across different datasets and problem scales, and whether performance degrades significantly under suboptimal Δc values.\n\n2. The current experiments are convincing, but primarily conducted on moderate-scale benchmarks. Could the authors provide additional results or analysis on large-scale MILP instances with more complex and heterogeneous constraints? Such evaluation would strengthen the claim that the proposed reduction framework generalizes well beyond the tested benchmarks.\n\n3. The proposed method identifies Critical Tight Constraints through a neural model. It would be interesting to see an analysis of what kinds of constraints are typically recognized as critical—e.g., are they associated with certain structural or semantic patterns? Such insights could improve the interpretability and trustworthiness of the model’s predictions.\n\n4. Since modern MILP solvers (like Gurobi) already include powerful presolve and constraint simplification modules, could the authors clarify how their learned reduction interacts with, or complements, the built-in presolver? A discussion or ablation comparing the two would help isolate the true contribution of the learned component.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The notion of Critical Tight Constraints (CTCs) represents a fresh and impactful contribution to the MILP optimization literature. Unlike prior works focusing on branching, cut selection, or presolving heuristics, this paper introduces a new perspective centered on constraint-level importance.\n\n2. Constraint reduction directly improves solver efficiency, making the method immediately relevant to industrial-scale applications such as logistics, scheduling, and network design.\n\n3. The proposed neural framework integrates multiple components — structural MILP encoding, PLM-guided feature enhancement, and supervised CTC prediction — in a cohesive and well-justified pipeline. \n\n4. The experiments are comprehensive and clearly demonstrate performance improvements over baseline solvers. The consistent gains on Gurobi are particularly convincing, showing both scalability and generalization.\n\n5. The paper is well-written and logically organized. The motivation for focusing on constraint reduction is clearly articulated and supported by both intuition and empirical evidence.", "weaknesses": "1. While the intuition behind identifying CTCs is compelling, the paper would benefit from a theoretical discussion or empirical analysis showing why certain constraints consistently dominate others. Some sensitivity or ablation studies on the constraint structure could strengthen the justification.\n\n2. The integration of PLM embeddings is an interesting choice, but it would help to quantify their actual contribution via ablation — e.g., selection of different PLM. It would be helpful to provide additional implementation details on how CTC reduction interacts with Gurobi and whether the approach is solver-agnostic.\n\n3. The paper is quite dense, covering multiple modeling, training, and experimental components. While this reflects solid effort, the narrative could benefit from streamlining or reorganization to emphasize the core technical contributions better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cVhwApA0bu", "reviewer": "Reviewer_HaxL", "summary": "This paper proposes a novel constraint-based model reduction framework for Mixed-Integer Linear Programs (MILPs). The core idea is to identify and fix a subset of \"critical\" tight constraints to reduce the problem's complexity, complementing the more common variable-fixing approaches. Experiments on standard benchmarks and a real-world dataset show improvements in solution quality and solving time.", "questions": "1. What is the setting used in the experiments for the MILP Solver?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper's focus on constraint reduction is a valuable direction. The idea that not all tight constraints are equally valuable for acceleration is intuitive, and providing a data-driven method to identify them is a meaningful contribution to the ML-for-optimization community.\n2. The proposed GNN architecture that incorporates both the instance-specific bipartite graph and an abstract graph with textual embeddings is a sophisticated and well-motivated approach. Fusing information from the problem category level is a sensible way to improve generalization and prediction accuracy for constraints.", "weaknesses": "1. While the information-theoretic motivation for the TCP heuristic is appealing, its practical implementation relies heavily on the \"Local Decoupling Assumption\" (Assumption 1). This assumption is a significant simplification, as constraints in MILPs are inherently coupled. The paper acknowledges that this is a heuristic, but the leap from the theoretical to its application for selecting constraints within a specific instance requires further justification. How does the pre-computed ρ for a constraint type reliably indicate the criticality of a particular constraint instance whose variables interact with many other constraints? A more detailed discussion or empirical validation of this link's robustness would strengthen the method's foundation.\n2. ​Baseline comparison is lacking in details, since Gurobi already has a lot of presolving techniques used to reduce variables and constraints. A fairer comparison needs to turn these presolving methods off.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NDbZiLWBG9", "reviewer": "Reviewer_3DQK", "summary": "This manuscript proposes a method that learns to predict tight constraints for Mixed-Integer Linear Programs, which are then used to construct a reduced sub-problem. The goal is to enable faster solution search compared to the original MILP. The paper provides both theoretical and empirical evidence supporting the proposed method. However, the theoretical results are somewhat trivial and rely on a strong assumption, while the baselines considered for comparison are insufficient.", "questions": "1. The tight constraints are defined based on the optimal solution. What happens if there are multiple optimal solutions? How does the proposed approach handle such cases? Also, what if obtaining the optimal solution is computationally expensive?\n2. An IP dataset is used in both of the considered learning baselines but is excluded from the experiments in this work. Could the authors clarify the reasoning behind this exclusion?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The manuscript is well-written with a clear and logical flow.\n2. The idea of constraint reduction is well-motivated, and it holds potential for practical impact.\n3. Empirical results demonstrate the advantages of the proposed method over the considered baselines.", "weaknesses": "1. **Confusing definitions**:  \n    - In Definition 1, $C_i$ is defined as a constraint type with unspecified parameters a,b and c. However, the phrase \"C_i(x) is satisfied\" is unclear. How should the satisfaction of a constraint type be interpreted? Clarifying this would improve understanding.\n    - In Definition 2, the term \"fixing\" appears early in the description of properties of the problem. Isn’t \"fixing\" typically an action performed during the reduction step? Could this be clarified?\n2. **Strong assumption**: The local decoupling assumption is quite strong and its applicability in practice remains unclear. It would be useful to provide statistics or empirical evidence demonstrating the proportion of constraints that satisfy this assumption in realistic scenarios. This would help assess the gap between theory and practice.\n3. **The main Theorem 4 is trivial and meaningless**: The main result in Theorem 4, which suggests that fixing tight constraints leads to a sub-problem containing the optimal solution, is trivial and lacks meaningful insight for the learning task, considering there is no guarantee that the model will accurately predict all tight constraints.\n4. **Inadequate baselines**: The authors mention prior works that also learn tight constraints for model reduction, yet fail to compare their method against these methods. I recommend incorporating at least one of these works as a baseline to enhance the comparison and demonstrate the advantages of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)