Light-MILPopt: Solving Large-scale Mixed Integer Linear Programs with Lightweight Optimizer and Small-scale Training Dataset
Authors: Huigen Ye
Hua Xu
Hongyan Wang
Venue: ICLR 2024 poster (2024)
Keywords: Large-scale MILP
Learning for Optimization
Lightweight Optimization Framework
Primary area: optimization
TL;DR: This paper proposes Light-MILPopt that only uses a lightweight optimizer and small-scale training dataset to solve large-scale MILPs.

Abstract: Machine Learning (ML)-based optimization approaches emerge as a promising technique for solving large-scale Mixed Integer Linear Programs (MILPs). However, existing ML-based frameworks suffer from high model computation complexity, weak problem reduction, and reliance on large-scale optimizers and large training datasets, resulting in performance bottlenecks for large-scale MILPs. This paper proposes Light-MILPopt, a lightweight large-scale optimization framework that only uses a lightweight optimizer and small training dataset to solve large-scale MILPs. Specifically, Light-MILPopt can be divided into four stages: Problem Formulation for problem division to reduce model computational costs, Model-based Initial Solution Prediction for predicting and constructing the initial solution using a small-scale training dataset, Problem Reduction for both variable and constraint reduction, and Data-driven Optimization for current solution improvement employing a lightweight optimizer. Experimental evaluations on four large-scale benchmark MILPs and a real-world case study demonstrate that Light-MILPopt, leveraging a lightweight optimizer and small training dataset, outperforms the state-of-the-art ML-based optimization framework and advanced large-scale solvers (e.g. Gurobi, SCIP). The results and further analyses substantiate the ML-based framework's feasibility and effectiveness in solving large-scale MILPs.

Published as a conference paper at ICLR 2024
LIGHT-MILPOPT: SOLVING LARGE-SCALE MIXED INTEGER LINEAR PROGRAMS WITH LIGHTWEIGHT OPTIMIZER AND SMALL-SCALE TRAINING DATASET
Huigen Ye, Hua ;u;; Hongyan Wang
State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Beijing National Research Center for Information Science and Technology(BNKis)) Beijing 100084, China {yhg23, why17) @ma ils. tsinghua edu. en, xuhua@tsinghua..em edu, cn
ABSTRACT
Machine Learning (MI.)-based optimization approaches emerge as a promising technique for solving large-scale Mixed Integer Linear Programs (MILPs). How- ever, existing ML-based frameworks suffer from high model computation com- plexity, weak problem reduction, and reliance large-scale optimizers and large training datasets, resulting in performance bottlenecks for large-scale MILPs. This paper proposes Light-MIL work that only uses a lightweight optimizer and small training dataset to solve large-scale MILPs. Specifically, Light-MILPopt can be divided into four stages: Problem Formulation for problem division to reduce model computational costs, Model-based Initial Solution Prediction for predicting and constructing the initial solution using small-scale training dataset, Problem Reduction for both variable and constraint reduction, and Data-driven Optimization for current solution im- provement employing a lightweight optimizer. Experimental evaluations on four large-scale benchmark MILPs and real-world case study demonstrate that Light- MILPopt, leveraging a lightweight optimizer and small training dataset, outper- forms the state-of-the-ans
lightweight large-scale optimization frame-
als-d optimization framework and advanced large- scale solvers (e.g. Gurobi, SCIP). The results and further analyses substantiate the MI.-based framework's 's feasibility and effectiveness in solving large-scale MIL.ss.
INTRODUCTION
Mixed Integer Linear Programs (MILPs) are linear optimization problems in which some or all de- cision variables are subject to integer constraints [Wolsey] 2020). They widely utilized for mod- eling combinatorial optimization problems such as routing (Li et al. 2018). bin packing (Paquay) al. 2016) and resource allocation (Koth al. 2016). In many scenarios, large number of ho- mogeneous MILPs with similar combinatorial structures need to be solved simultaneously. In such cases. Machine Learning based optimization frameworks can explore correlations between the structure and solution values to enhance solving performance, making ML-based frameworks a promising direction (Han et al., 2023 Deb et al. 2023).
As the pioneering work using ML-based frameworks to solve MILPs, Gasse et al. (2019) proposed a lossless graph representation of MILPs using bipartite graphs, and further accelerated MILP solv- ing by using Graph Neural Network (GNN) model to learn variable selection policies within the branch-and-bound method. With the increase in the dimensionality of decision variables MILPs, the search space for the branch-and-boum algorithm expands exponentially. This results in pro- hibitively high computational costs, especially in the case of large-scale MILPs. To mitigate this challenge, Nair et al. (2020) proposed the Neural Diving approach, which fixes most decision vari- ables based on the initial solution prediction results obtained through a GNN. Consequently, large- scale MILP is transformed into smaller-scale MILP consisting of the remaining subset of decision
"Corresponding Author: Hua Xu (cuhua@tsinghua.cduuoo

---

Published as a conference paper at ICLR 2024
variables, effectively reducing the dimensionality of decision variables in the MILP. Sonnerat et al. (02I)) further introduced NeuralLNS, which trains a Neural Selection policy to select the search neighborhood in Large Neighborhood Search (LNS) algorithm (Song et al. 2020 Ye et al. 2023a) to improve the initial solution obtained from Neural Diving. However, Neural Diving cannot fully exploit the embedding spatial information, and NeuraILNS heavily relies large-scale solvers, leading to performance bottlenecks and limitations in solving capabilities constrained by the current solvers. In light of these limitations, Ye et al. (2023b) proposed a GNN&GBDT-guidee optimizing framework that respectively employs the Multitask GNN to generate the embedding space, the Gra- dient Boosting Decision Tree (GBDT) to effectively use the embedding spatial information, and the Neighborhood Optimization to improve the current solution by means of small-scale optimizer.
While the GNNGGgDT-gudided framework has shown promising performance in practical applica- tions, it still exhibits several noteworthy limitations. Firstly, representing MILPs as an entire graph poses challenges regarding model training and computational resources, particularly when tackling large-scale MILPs. Secondly, the GNN requires large-scale MILP instances of similar size as training data, leading to significant computational and storage resource demands during the training phase. Thirdly, the application of problem reduction solely focuses on the decision variable level, overlooking potential synergies with constraint reduction, resulting in limited effectiveness in prob- lem reduction. Generally, the performance of this method severely decreases when dealing with large-scale MILPs with complex constraints.
To address the challenges above, we propose Light-MILPPpt, lightweight optimization framework explicitly designed for large-scale MILPs, which consists of four stages: 1) Problem Formulation. Initially, we represent the MILP as bipartite graph and then employ the FENNEL graph partition algorithm to divide the problem to reduce computational costs. 2) Model-based Initial Solution Pre- diction. We leverage the Edge Aggregated Graph Attention Network with calf-convolutions, trained by a small-scale dataset with homogeneous structures, to predict and construct the initial solution for each divided subproblem. 3) Problem Reduction. We selectively reduce decision variables based on the generalized confidence threshold while simultaneoouly reducing constraints using the K-Nearest Neighbor (KNN) strategy. 4) Data-driven Optimization. Building upon problem division and reduc- tion, we employ subgraph clustering and active constraint updating to guide neighborhood search and individual crossover, iteratively enhancing the current solution with a lightweight optimizer.
To validate the effectiveness and efficiency of Light-MILPopt which only uses lightweight op- timizer and a small-scale training dataset, we conduct extensive experiments on four large-scale benchmark MILPs and real-world case study. The results indicate that, compared with the state- of-the-art optimization frameworks and large-scale solvers (e.g.. Gurobi, SCIP), the proposed frame- work exhibits significant advantages when solving large-scale MILP. Further analyses show that the proposed framework can effectively reduce the model's 's computational complexity and achieve sub- stantial problem reduction, which verifies its effectiveness and efficiency.
Our contributions can be summarized as follows.
We propose the first lightweight framework that solves large-scale MILPs with only small-scale training datasets and lightweight optimizers, introducing Problem Formulation, Model-based Initial Solution Prediction, Problem Reduction, and Data-driven Optimization to reduce the computational complexity and improve the problem reduction capability.
We demonstrate the effectiveness of the proposed framework in solving large-scale MILPs with lightweight optimizers and small-scale training datasets through a comparative anal- ysis with state-of-the-ar optimization frameworks and advanced solvers, providing initial insights into efficiently solving large-scale MILPs with limited computational resources.
2 PRELIMINARIES
2.1 MIXED INTEGER LINEAR PROGRAMS
Mixed Integer Linear Programs (MILPs) are type of problem in which the objective function is linear under several linear constraints. In these problems, some or all decision variables are restricted to take integer values. Formally, an MILP has the form as the following (Achterberg. 2007).
min cT x, subject to Ar S b, S I S u. x4 E Z,i El
(1)
2
2

---

Published as a conference paper at ICLR 2024
Erdnsling
Demoilttie
min F1
dus
CLU
Enbeccling
Canssitinn
(a) Bipartite Graph Representation
(b) GCN with Half Convolutions
MILP instance to bipartite graph. The set of constraint nodes f 5m and the set of n decision variables nodes {z1..... Zn form the left-side constraint nodes set and the right-side variable nodes set of the bipartite graph representation. (b) The archi- tecture of GCN with half-convolutions only has one layer. The layers in GCN can be broken down into two successive passes, one from variables to constraints and one from constraints to variables.
Figure 1: (a) Transforming
where x denotes the decision variables whose number is denoted by E 2, with I, u, I being their lower bound, upper bound and coefficient, respectively.
E R*** and b E R denote the linear constraints. I S {1, 2, ................................ .n) is the index set of integer variables. A solution is feasible for the MIIP if decision variables x E R2 satisfy all the constraints in Equation (1. A feasible solution is optimal if it attains the minimum objective function value of the minimized MILP (Schrijver) 1998).
constraint is an active constraint if the optimal solution of the MILP changes when removing this
constraint, and vice versa for redundancy constraint Bailey & Gillett 1980 Murty & Yu 1988).
2.2 BIPARTITE GRAPH REPRESENTATION
The bipartite graph representation for MILPs proposed by Gasse et al. (0199) achieves a lossless graphical representation of an MILP as the input of the neural embedding network (Nair et al. 2020), described in the left side of Figure I The n decision variables in the MILP can be represented as the right-side variable nodes set the bipartite graph, while the linear constraints can be represented as the left-side constraint nodes set. The edge connecting variable node and constraint node represents the corresponding variable that appears in that constraint. The details of the feature selection policy are shown in Appendix A.1
2.3 GRAPH CONVOLUTIONAL NETWORK
In MILPs, based on the bipartite graph representation, the Graph Convolutional Network (GCN) Kiipf & Welling 2016) is used for learning neural embedding and model-based initial solution prediction. Formally, let represent the edges in a bipartite graph, and a k-layer GCN is as follows.
ト = fz ((h f ((h (u,v) E E}))),
(2)
where 1 represents the hidden state of node o in the k-th layer. The function S combines the hidden values of the neighbors from the previous (A 11-t layer to obtain aggregation information, while the function f combines the hidden value of the current node e with the aggregation infor- mation from its neighbors. For the bipartite graph representation, the GCN with two interleaved half-convolution layers can achieve better performance (Gasse et al.) 2019 Yoon (022). Formally, let V., denote the set of n variable nodes and V/ denote the set of m constraint nodes, and le layer half-convolutions GCN could be written the following.
h5 13 (1h), (K-2)
Σ (Kc.6yiCE
ge (E((((-))
11,, (14=)))))) Va.
(3)
h = (Ch (k-1)
Σ (EA,8))E
(k-1 , 1))), Va. (
where hi. h/j o and of are aggregation functions. The right side of Figure provides an overview of the 1-layer GCN with half-convolutions layers.
2.4 EDGE AGGREGATED GRAPH ATTENTION NETWORK
The current GCN model mentioned in Sec. 2.3 faces two significant problems. Firstly, only uses fixed policy to aggregate node information. Secondly, it can not fully incorporate the edge
3

---

Published as a conference paper at ICLR 2024
Dataset
Problem Fomuuatiin
Reduction
Data-driven Optimization
pariia Grazh
Bulgg with Chaskengg
Meepptoottne Partice
Nest Raate
Model Bassd Initial Salution Pradiction
Inv Tussy Bateet Optvier X=I (.3
Prediem Dieace
EGAT with Hal
Prediciio
Busa Solation Searhh
wil
Seurt
of
Selaten
Bood 1
optimited variable
wornbnder.oo mode werliblo B cumrent sdlution
High confidees
optiical vaciab
Figure 2: An overview of Light-MILPopt. where the blue line indicates that the component only used during training. Firstly, the MILP is represented as a bipartite graph, and the FENNEL graph partitioning algorithm is employed for problem division to reduce model computational costs. Sec- ondly, given the divided graph representations, the EGAT, trained by small-scale training dataset, used for predicting and constructing the initial solution of the original large-scale MILP. Thirdly, leveraging the predicted solution, the decision variable's confidence threshold and constraint's KNN strategy are introduced for problem reduction. Finally, based on problem division and reduction, the subgraph clustering and active constraint updating guide neighborhood search and individual crossover, iteratively improving the current solution by means of a lightweight optimizer.
features, ultimately resulting in poor performance in graphs with edge weights. To tackle these problems, troblems,,Gong.. & Cheng 2019) proposed the Edge Aggregated Graph Attention Network (EGAT), which introduces an attention mechanism on graph neighborhoods and adequately exploits edge information, benefiting the learning neural embedding and model-basee initial solution prediction. Formally, let & represent the edges in the bipartite graph. A k-layer EGAT could be written as below.
h = =ffa ( (u, v) g),
(4)
where h is the hidden state of node in the k-th layer; E.; denotes the hidden state of the edge connecting u and e in the k-th layer; is non-linear activation; 9 is transformation that maps the node features from the input space to the output space. The g defined as: g (h:-1) = W k-1 where W is transformation parameter matrix. Additionally, a is the attention coefficient that is a function of k-1 h--1 and Ek-1, and is defined as follows.
ow = DS(erp(T[(a (WW
[WI+-"D)]&
(5)
where DS is the doubly stochastic normalization operator defined in Appendix A.3 L is the Lea activation function (Xu al.) 2020); W is transformation parameter matrix; and is the concatenation operation. Finally, the attention coefficients are used as new edge features for the next layer, defined as: E ai
THE PROPOSED LIGHT-MILPOPT
This section describes Light-MiLPopt, the proposed lightweight optimization framework that solves large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset. Light-MILPopt can be divided into four stages: Problem Formulation (Sec. 3.1. Model- based Initial Solution Prediction (Sec. 3.2,, Problem Reduction (Sec. 3.3), and Data-driven Opti- mization (Sec. 3.4
We present the overall architecture of the proposed framework in Figure 2
3.1 PROBLEM FORMULATION
In Light-MILPopt, the large-scale MILP is represented in the form of a Bipartite Graph at first. Then, the FENNEL Graph Partition algorithm (Tsorrkkakis et al.) 2014) is applied to divide the graph into several blocks. Based on the above steps, all the subgraphs obtained from the graph partition form the inputs for feature-embedding neural networks.
4

---

Published as a conference paper at ICLR 2024
Bipartite Graph Representation. Based on the classic bipartite graph representation introduced in Sec. 2.2 the feature selection policy is further improved to enhance embedding ability. For one thing, the random feat strategy (Chen et al. 2023) is introduced to get better representation and emhedding capabilities when facing some particular MILPs called "foldable" (Chen et al. 2023). Specifically, by adding random features, the predicting of MILP feasibility, optimal objective values, and optimal solutions becomes more reliable. For another thing, the classic feature selection policy for categorical features, which only uses single integer is not sensitive to categorical information, resulting in weak feature neural embedding in feature- eeaturr-embeddinng neural networks. Therefore, the one-hot strategy (Shen et al. 2022) is utilized to represent the categorical features, further enhancing the impact of categorical information on the neural encoding results. More details of the introduced new policy are shown the Appendix A.2
Graph Partition-based Problem Division. For an MILP, the size of the bipartite graph representa- tion is linearly correlated with the problem scale (Gasse et al. 2019). Therefore, when dealing with large-scale MILPs with millions of variables, directly using the entire bipartite graph representation as the input for feature-embedding neural networks for training or predicting would lead to signif- icant demands computational and storage resources. Inspired by the Graph-Bert (Zhang al., 2020) subgraph partitioning concept, we use the FENNEL graph partitioning algorithm, described in Appendix A.4, to divide the original entire bipartite graph into several low-correlation subgraphs, with each subgraph representing a divided subproblem. The partitioned subgraphs are then sequen- tially fed into the feature-embedder neural network, thus transforming the solution of a large-scale optimization problem into the parallel solution of multiple small-scale problems.
3.2 MODEL-BASED INITIAL SOLUTION PREDICTION
Given the graph representation with multiple small-scale subgraphs for the large-scale MILP, EGAT with Half-convolations learns the neural embedding for the decision variables. Then the Neural Prediction network with Multi-Layer Perceptron (MIP) structure predicts the initial value of the corresponding decision variable in the MILP through the neural embedding. Finally, the predicted initial solution will guide the subsequent problem reduction in the next stage.
EGAT with Half-convolutions. Based on the GNN with half-convolutions (Yoon 2022) (Sec. 2.3 and EGAT (Gong & Cheng 2019) (Sec. 2.4). we propose an EGAT with multi-layer half- convolutions structure which combines the advantages of the above two methods, intended to further improve the neural embedding learning of the decision variables for every divided subgraph. For- mally, based on Equation (3) and (4. letting & represent the edges in the bipartite graph, k-layer EGAT with multi-layer half-convolutions structure can be represented as follows.
a DS(ezp(L(a [WA "Ila" [h, (1)2))))) h olla2io (h ( (m, 5,) E Et, (nk h alat, (Mi (47)) (mi, E E) ( (nd, Eh,,, a
(6)
where htt and hy, represent the hidden state of constraint node dy and variable node z; in the k-th layer, respectively; E and a denotes the hidden state and attention coefficient of the edge connecting variable node x; and constraint node ōy in the k-th layer, respectively; a is non-linear activation; g² is transformation that maps the node features from the input space to the output space. The information transition flow of EGAT with half-convolutions is shown in Figure 3
Neural Prediction. Based on the neural embedding of the decision variables obtained by the EGAT, a p-layer MLP is used to predict the initial value of the corresponding decision variable for every divided small-scale MILPs. For binary variables T;, the neural embedding of the decision variable only undergoes a single Multi-Layer Perceptron (MLP) transformation, followed by the application of the Sigmoid activation function to the MLP's output. This process allows the output to convey the probability that the respective decision variable equals 1, denoted as p(z; 1|M). For general integer variables or even real variables, according to the required accuracy, the neural embedding of a decision variable needs pass through multiple independent MLPs with Sigmoid activation function in parallel. For the i-th decision variable, the output of the j-th MLP can represent the probability that the j-th binary bit is 1, represented as p(m: = 1JM), and the value of the bit is taken
5

---

Published as a conference paper at ICLR 2024
Constraint
Edge
Variable
Constraint
Edge
Variable
Constraint
Edge
Vartable
Step1
Stop
Stop
Figure 3: Information transition flow in the EGAT with half-convolutions. The information tran- sitions run consecutively as follows: Step 1, transforming variable nodes and constraint nodes in- formation the edge; Step transforming the variable nodes and edge information constraint nodes; Step 3, transforming constraint nodes and edge information to the variable node.
Lp(ay M + 0.5J, where Focal Loss (Lin al. 2017) is used for training. Due the weak correlation among the small-scale MILPs obtained by problem division, all the split small-scale MILP have obtained initial predicted solutions, the initial predicted solutions of the split small-scale MILP can be concatenated to obtain the initial predicted solutions of the original large-scale MILP.
3.3 PROBLEM REDUCTION
Given the predicted initial solution of the MILP, the generalized confidence threshold method adap- tively fixes the high-confidence decision variable to achieve Variables Reduction. Then, KNN strat- egy is used for Constraint Reduction to identify active constraints. The unfixed decision variables and KNN constraints can jointly guide the initial solution search and iterative optimization.
Variables Reduction. Classic approaches employ SelectiveNet (Geifman & EI- Yaniv 2019) to pre- dict the initial solution of MILP while simultancously predicting the variable reduction based on the target reduction ratio. However, this method requires multiple training runs for different target re- duction ratios, leading to additional training overhead. Therefore, Light-MILPopt proposes gener- alized confidence threshold method based on the confidence threshold method specifically designed for binary variables (Yoon) 2022), aiming to reduce efficient variable dimensionality. Specifically, based on the MILP's initial solution obtained from the model predictions, the confidence value f. of the decision variable x; which contains binary bits can be represented follows.
max(p(ag 1JM), 1 p(r. 1[M)]
Next, the confidence values of the decision variables are sorted in descending order. Based on the desired reduction ratio of k%, the top A% of the decision variables are fixed to their predicted values. The remaining decision variables form new small-scale optimization problem that is fed into the initial solution search of the next stage, achieving variables reduction for the large-scale MILP
Constraint Reduction. The constraints in MILP be classified into redundant constraints and active constraints as mentioned Sec. 2.I Effective removal of redundant constraints simplifies the solution space and speeds up the process of solving large-scale MILPss termed as constraints reduction. When without considering the integer constraints, the feasible domain formed by linear constraints in MILP possesses the property of convexity. If the optimal solution of the MILP is known, active constraints are often those that are close to the optimal solution (Runarsson & Yao, 2005). Since the predicted initial solution is the result of fitting a model to the optimal solution, the predicted initial solution can be treated as an estimation of the optimal solution, utilized for computing the distance from each constraint hyperplane. Finally, according sults, the KNN constraints of the predicted initial solution are selected as the prediction of the active constraints, and the remaining redundant constraints are deleted realize constraint reduction.
the calculation re-
3.4 DATA-DRIVEN OPTIMIZATION
Based the predicted initial solution and the problem reduction, we first solve the reduced subprob- lem to obtain the Initial Solution for the complete MILP. Then, under the guidance of Neighborhood Set Updating and the active Constraint Set Updating, neighborhood search and individual crossover

---

Published as a conference paper at ICLR 2024
Clustaring
Neighborhood Partiton
Individual
Figure 4: (a) Apply random-cluster algorithm to the divided subgraphs to group subgraphs into several clusters. (b) Decision variables in a cluster form neighborhood block. (c) Employ the hierarchical crossover strategy for neighborhood merging and corresponding individual crossover.
iteratively improve the current solution. Finally, when a predetermined wall-clock time or condition reached, the current solution is output the final optimization result.
Initial Solution Search. For the large-scale MILP with n decision variables, we first define a coef- ficient 10 denote that the lightweight optimizer
solve small-scale MILP containing most on decision variables. Following this, an initial solution search method described in Appendix A.6 is employed for the reduced small-scale MILP obtained from the stage of dimensionality duction. Finally, the optimal solution obtained by the lightweight optimizer is recombined with the reduced decision variables form an initial feasible solution.
Neighborhood Set Update. In each iteration of optimization, both the neighborhood search and individual crossover require a new neighborhood prevent getting stuck local optima. Based on the subgraph partitioning obtained from the FENNEL graph partitioning algorithm, we use random- cluster algorithm (Grimmett, (006) to further group the subgraphs into several clusters that are suitable for the small-scale solver, shown in Figure a) and Appendix A.7 Each cluster contains decision variables from multiple subgraphs, forming a neighborhood block. The graph cluster cor- responding to neighborhood set is shown schematically in Figure [b).
Constraint Set Update. Due to the potential distance between the initial predicted solution and optimal solution, the initial prediction of active constraints is biased. Therefore, after each optimiza- tion iteration, the current solution gradually approaches the optimal solution, and Light-MIL set of KNN constraints to obtain more accurate estimates of active constraints using the new current solution as the reference point. Furthermore, since the prediction active adopt a progressive
calculates
constraints becomes more and more reliable the optimization proceeds, strategy by choosing larger value of K in KNN at the beginning and gradually narrowing down the of active constraints. Specifically, after each iteration, K is updated K 7) until the predefined minimum reduction threshold is reached, where E (0, 1) is the preset descent rate, contributing the progressive reduction of constraints. Finally, as the active constraint set changes, the feasible solution region is also altered. So we employ the REPAIR algorithm described in Appendix A.8 to "repair" current solution, which ensures the current solution falls within the new feasible solution range changes by the new active constraint set.
Iterative Optimization. In each iteration, based on the updated neighborhood set and updated active constraint set, the neighborhood search is parallelly executed in each neighborhood, utilizing a lightweight optimizer. Then the results the neighborhood search are used as individuals for hierarchical crossover shown in Figure 4 (c), allowing the integration and inheritance of strengths from different neighborhoods, leading to improved solutions efficiently. When the current iteration ends, the results of the individual crossover update the current solution and simultaneously update the neighborhood set and the active constraint set. Finally, when meeting the predetermined time or conditions, the current solution is output the final optimization result.
4 EXPERIMENTS
To validate the effectiveness and efficiency of the proposed Light-MILPopt for large-scale MILPs, we compare it with two types of basclines on four widely used large-scale NP-hard standard bench- mark MILP datasets: Set Covering (SC, Minimize) (Caprara al. 2000), Minimum Vertex Cover

---

Published as a conference paper at ICLR 2024
Table I: Comparison of objective value results with baselines under the same running time on differ- ent large-scale MILPs. Ours-30%S means the proposed framework with the scale-limited versions of SCIP which limit the variable proportion to 30%. GBDT-50%G means the GNN&GBDT framework with the scale-limited versions of Gurobi which limit the variable proportion a to 50%. means the result is better than the baseline. means that no feasible solution is found.
SC₁
SC₂
MVC;
MVC2
MIS
MIS,
MIKS,
MIKS
Case Study 944086.41 979797.81
Ours-3D9s
17121.51
166756.0
27337.81 81
273014.6T
22621.71
227074.51
35067.81 35533.41
355887.61 357439.51
Ours-30%G
17047.31
163975.91
27223.31
272579.51
22658.01
227305.41
GBDT
17222.2
261174.0
27515.4
276306.9
22389.3
223349.8
GBDT30%
18487.6
281021.2
27700.8
281234.5
22115.9
210019.2
Ours 50&S
16147.27
166966.9T
26956.87
269771.37
22963.61
230278.11 1T
36125,51
357483.87
944166.1 IT
Ours-50%G
16108.17
160015.51
36950.71
269571.51
22966.51
230432.91
36108.21
16226..1
980688.07
GBDT50%S
16728.8
268294.9 9
27107.9
271777.2
22795.7
227006.4
GBDT50%
17503.4
252797.2
27329.9
274600.8
22530.1
215393.6
SCIP
25191.2
385708.4
31275.4
491042.9
1864996
9104.3
29974.7
168289,9
924954.5
Gurbhi
17934.5
320240.4
28151.3
283555.8
21789.0
216591.3
32960.0
329642.4
Time
12000s
2000s
8000s
2000s
2000s
6000s
1000s
(MVC, Minimize) (Diuur & Safra 2005), Maximum Independent Set (MIS, Maximize) Tarjan &
Trojanowski 1977). Mixed Integer Knapsack Set (MIKS, Maximize) (Atamtürk) 2003) and one real-world large-scale MILP in the internet domain (Case Study, Maximize), One type of the base- lines is the state-of-the-art MILP solvers, including SCIP (Achterberg 2009) and Gurobi (Achter- berg 2019). The other one is the latest state-of ofte-offthhearr the-thtrttttt ML-baaed optimization framework based on we present more details of the datasets, compre-
GNN YY et al., (023b). In Appendix B
hensive experimental setup, and the baselines.
To make fair comparisons, we use multiple evaluation metrics to study the performances of all the related methods in this paper, including comparisons of solving effectiveness under the same running time (Sec. 4.1). comparisons of solving efficiency under the same solving results (Sec. [42). and
analysis of convergence (Sec. 4.3 Additional experimental results are detailed in Appendix C Code for reproducing all the experiments can be found at
4.1 COMPARISONS OF SOLVING EIFECTIVENESS
To verify the effectiveness of the proposed Light-MILPopt. we compare the solving results of the proposed framework with the large-scale solvers SCIP, Gurobi, and the GNN&GBDT frameworks, at the same runtime. Light-MILPopt only uses lightweight optimizer which limits the variable proportion a to 30% and 50%, and using only 1% of the size of large-scale benchmark MILPs for training data. We present the experimental results in Table I On the one hand, compared to the large-scale baseline solvers SCIP and Gurobi, Light-MII obviously outperforms them only using limited version solver with variable proportion a 30%. On the other hand, the proposed framework achieves better results than the GNN&GBIT frameworks in integer programs with the same scale of variable reduction, efficiently solving large-scale MILPs, which cannot be solved by the GNN&GBDT framework.
worth noting that in the SC scenario, Light-MILPopt outperforms all baselines significantly. Upon in-depth analysis. it becomes apparent that the small-scale subgraphs obtained through prob- lem division contribute to the improved performance and efficiency of initial solution prediction. Additionally, SC is problem characterized by intricate constraints, and constraint reduction de- creases the time required for each iteration of optimization to 1/5 of the original time. This factor greatly contributes the remarkable solving ability of Light-MiI for this particular problem.
4.2 COMPARISONS OF SOLVING EFFICIENCY
To further validate the efficiency of the Light-MILPopt, we compare the running time of the pro- posed framework with the baseline algorithms with fixed-solving results. We represent the experi- mental results in Table 2 It's evident that Light-MILPopt significantly reduces the time required to obtain the same optimization results compared to all the baseline approaches on all MILPs. Specif- ically, compared to the large-scale baseline solvers, the proposed framework can achieve the same results in only 0.5% of the time for the benchmark MILPs, including MVC, MIS, and MIKS, Even compared to the state-of tfeee----thhttttttt based frameworks. our Light-MILPopt can save more than 90% of the solution time on most MILPs to achieve the same results. It is interesting to note that for MVC, and MIS, while there is little difference among all methods in terms of achieving the same
8

---

Published as a conference paper at ICLR 2024
Table 2: Comparison of running time with SCIP, Gurobi and GNN&GBDT framework under the same target value on different large-scale MILPs. Ours-30%S means the proposed framework with the scale-limited versions of SCIP which limit the variable proportion a 30%. GBDT-50%G means the GNN&GBDT framework with the scale-limited versions of Gurobi which limit the vari- able proportion a to 50%. t means the result better than the baseline. > means indicates the inability to achieve the target value in some instances within the maximum running time.
SC1
SCa
MVC1
MVC₂
MIS;
MIS₂
MIKS
MIKS
Case Study 996.4s1 511.5st
Ours-3096
1998.lsf
11823.0T
1951,6sT
7967.2x1
1951.fst fixt
7967.2st
1982.0sT 593.9s
4x980.4s 79419st
Ours-30%G
1166.86
5648.0sT
1475,36t
6453.36
1487.361
7250.5et
GBDT-30%S
>48369.2
>60000s
-60000s
>60000s
560000s
>60000s
GBDT30RG
30347..8 8s
>60000
>6000
>60000s
600000
>60000s
Ours O
352.2st
11441.341
203.1st
1815.36
225.961
1948.7x1
194.9t
9576.1st
776.241
O0rs
177.8st
1795.4ct
193.8T
1503.31
223.56T
2062.7s1
160.5st
2137.8cT
506.967
GBDTS0%S
587.6s
>-0000ss
297.66
7570.5s
348.6s
5920.7s
GBDTS0%
>60000s
58
21397.36
27952.9s
SCIP
G0000S
600000s
000000
600000
600000
600000
60000
> 60000s
5097.0s
Gambi
60000s
560000s
560000s
5-0000s
60000s
560000s
45599.44
> 60000s
2584.7s
Turget
17121.5
166756.0
27357.8
273014.6
227074.5
35067.8
355887.6
31000
2:800
34400
DunSRNG
GANLCIDT52NGG
Belective
21060
20000
213800
GBH5C20132NG Gerool
Guccil
35809
Time
Time
(a)
(c)
Figure 5: Tije-objective figure for three of the benchmark MLIPs. (a) The minimized SC problem.
(b) The minimized MVC problem. (c) The maximized MIS problem.
optimization results within certain time frame, there is significant difference in running time. Our analyses demonstrate that the proposed framework can significantly reduce the time required to achieve the same results the baseline methods.
4.3 ANALYSIS OF CONVERGENCE
Convergence is an essential metric for evaluating the performance of optimization frameworks. To analyze the convergence of Light-MILPPptt, record the trend of the objective value with the iter- ation time of the proposed framework and baseline algorithm on three MILPs that the GNN&GBDT framework can solve, including SC, MVC and MIS. We visualize the time-objective variation in Figure
5 We can see that the proposed framework can obtain high-quality solutions for large-scale MILPs with only small-scal training data and lightweight optimizer. Figure also demonstrates that the convergence performance of Light-MILPopt is not weaker than that of the state-of-the-r solver Gurobi as well as the state-of-the- ML--baeed optimization framework.
5 CONCLUSION
This paper proposes Light-MILPopt, a lightweight optimization framework for large-scale MILPs. Light-MILPopt uses graph partition-based problem division and EGAT with half-convolutions to efficiently predict initial MILP solutions with only lightweight training dataset. Through variables and constraints reduction, Light-MILPog rapidly updates the current solution with a lightweight optimizer. Experimental evaluations conducted on four standard large-scale MILPs and a real-world case study demonstrate that our framework outperforms SCIP, Gurobi, and the GNN& bassdb optimization framework. In the future, we will further improve the proposed framework and explore its applicability in ultra-large-scale, multi-objective, and nonlinear constraint scenarios.

---

Published as a conference paper at ICLR 2024
REFERENCES
Tobias Achterberg. Constraint integer programming. 2007.
Tobias Achterberg. Scip: Solving constraint integer programs. Mathematical Programming Com- putation, 1:1 41, 2009.
Tobias Achterberg. What's in gurobi 9.0. Webinar Talk url: https://www. gurobi. com/wp- conten//ploadd220191222uuuv -i-eoubi-----vvvviiwe--ee- Siiiiee--Wbbinr-SSidee pdf, 2019.
Alper Atamtürk. On the facets of the mixed-integer knapsack polyhedron. Mathematical Program- ming, 9811-3):145-1755 2003.
Mason Gene Bailey and Billy E Gillett. Parametric integer programming analysis: A contraction approach. Journal of the Operational Research Society, 31:257-262. 1980.
R. Byrd, Goldman, and Miriam Heller. Technical note-recogmizing unbounded integer programs. Operations Research, 35:140-142, 02 1987. doi: 10. 10.1287/opre.3..1
Alberto Caprara, Paolo Toth, and Matteo Fischetti. Algorithms for the set covering problem. Annals of Operations Research, 98:353-371, 2000.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Kalyanmoy Deb, Peter Fleming, Yaochu Jin, Kaisa Miettinen, and Patrick Reed. Key issues in real-world applications of many-objective optimisation and decision analysis. In Many-Criter Optimization and Decision Analysis: State-of-the-Arr, Present Challenges, and Future Perspec- tives, pp. 29-57. Springer, 2023.
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, 2020.
Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of mathematics, pp. 439-485, 2005.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32, 2019.
Yonatan Geifman and Ran Yania..v. Selectivenet: A deep neural network with an integrated reject option. In International conference machine learning, pp. 2151-2159, PMLR, 2019.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 9211-9219, 2019.
Geoffrey Grimmett. The Random-cluster Model, volume 333. Springer, 2006.
Olivier Guieu and John W Chinneck. Analyzing infeasible mixed sitteer and integer linear pro- grams. INFORMS Journal on Computing, 1(1):63-77, 1999.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xi- aodong Luo. A gon-guided predict-and-search framework for mixed-integer linear programming. arXiv preprint arXiv:2302.056:: 2023.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: ww..6660900000 2016.
Amir O Kotb, Yao-Chun Shen, Xu Zhu, and Yi Huang. iparker-a new smart car-parking system based on dynamic resource allocation and pricing. IEEE transactions on intelligent transportation systems, 77:667-22647, 2016.
Chunlin Li, Jingpan Bai, Jinguang Gu, Xin Yan, and Youlong Luo. Clustering routing based on mixed integer programming for heterogeneous wireless sensor networks. Ad Hoc Networks, 72: 81-90, 2018.
10

---

Published as a conference paper at ICLR 2024
Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. Proceedings of the IEEE international conference on computer vision, pp- 2980-2988, 2017.
Katta Murty and Feng-Tien Yu. Linear Complementarity, Linear and Nonlinear Programming, volume 3. Citeseer, 1988.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan D'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 13344, 2020.
Célia Paquay, Michael Schyns, and Sabine Limbourg. A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application. International Transactions in Operational Research, 23:187-213. 2016.
Thomas Philip Runarsson and Xin Yao. Search biases in constrained evolutionary optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 35: 233-243. 2005.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1998.
Cencheng Shen, Qizhe Wang, and Carey E Priebe. One-hot graph encoder embedding. JEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Jialin Song, Yisong Yue, Bistra Dilkina, al. general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, 33: 20012-20023, 2020.
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.
Robert Endre Tarjan and Anthony E Trojanowski. Finding a maximum independent set. SIAM Journal on Computing, 6(3):537-546, 1977.
Charalampos Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In Proceedings of the 7th ACM interna- tional conference on Web search and data mining, pp. 333-342, 2014.
Laurence Wolsey. Integer Progrumming. John Wiley & Sons, 2020.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 30075- 30087. Curran Associates, Inc., 2021.
Jin Xu, Zishan Li, Bowen Du, Miaomiao Zhang, and Jing Liu. Reluplex made more practical: Leaky relu. In 2020 IEEE Symposium on Computers and communications (ISCC), pp. 1-7. IEEE, 2020.
Huigen Ye, Hongyan Wang, Hua Xu, Chengming Wang, and Yu Jiang. Adaptive constraint partition based optimization framework for large-scale integer linear programming (student abstract). In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 16376-16377, 2023a.
Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. GNN&GBDT-guides fast optimizing framework for large-scale integer programming. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202, pp. 39864 39878. PMLR, 2023b.
Taehyun Yoon. Confidence threshold neural diving. arXiv preprint arXiv: arXiv:2202.07506 2022.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.

---

Published as a conference paper at ICLR 2024
APPENDIX
This Appendix contains three sections. Appendix A introduces the details of some algorithms men- tioned in the main text, elaborating their implementation details through formulas pscudo-code. (opendix(BBdeserre
the experimental setup, including the standard mathematical form of the stan- dard benchmark MILP, parameter settings in data generation, and other relevant setup information. Appendix [ shows supplementary experimental results to verify the effectiveness and efficiency of Light-MILPopt further. Appendix D shows more additional information on mixed-integer linear programms.
A ADDITIONAL ALGORITHM DETAILS
A.1 FEATURE SELECTION POLICY
In the classical feature selection policy (Gasse et al. 2019 Nair et al. 2020), the feature selection of nodes and edges usually depends on the coefficients in the formulation of MILP. Formally, let he, Ny. (((k)) denote the feature selection of the i-th variable node, j-th constraint node and edge (i,j), the classical feature selection policy can be written as the following.
h- (ci, lis uis li, d;),
hg 0z),
(8)
h(a,)) = (a:y),
where Ci, kis ui, l denotes the coefficient, lower bound and upper bound of the i-th decision variable respectively; di E (0, }} represents whether the i-th decision variable restricted to take integer value or not; by. o, refers the value and symbol of the j-th constraint; as denotes the weight of edge (i,
A.2 PROPOSED FEATURE SELECTION POLICY
Based on the classic bipartite graph representation introduced in Appendix A..1 the feature selection policy is further improved to enhance embedding ability.
On one hand, the random feat strategy (Chen et al. 2023) is introduced to achieve better representa- tion and embedding capabilities when facing some particular MILPs called "foldable" (Chen al., 2023 that can rewrite Equation (8) as the following.
hig (Gi, li, ui, di, 4, E),
hg = (b),
h(a) (aiy),
where & U0, 1) is the random feat between 0 and I.Specifically, by adding random features, the predicting of MILP feasibility, optimal objective values, and optimal solutions becomes more reliable. On the other hand, in the classical bipartite graph representation, for categorical features such the type of decision variables and the type of constraints, single integer is used represent the categorical feature's 's type. For example, for the representation of the type of constraints in j-th constraint node, the feature selection policy is (2- 0, <- 1, = 2). However, this feature selec- tion policy is not sensitive to categorical information, resulting in weak feature neural embedding in eeature-mmbedding neural networks. Therefore, the one-hot strategy that is widely used in the field of text feature representation is used for representing the categorical features, further enhancing the impact categorical information on the neural encoding results. In this feature selection policy, for the representation of the type of constraints in j-th constraint node, the feature selection policy is changed to {2- [1, O, 0). <- [0, 1, 0), = + [0, O, 1]3. So we can rewrite Equation (9 to obtain the final feature selection policy.
h (ci, li, ui, di, E),
hg (b,, 5).
(10)
h(g (ary),
where o', is the one-ho hot representation of the type of constraints in j-th constraint node, and we have og : (2- [1,0, 0), < [0, 1, 1], = [0, 1]].
12

---

Published as a conference paper at ICLR 2024
A.3 DOUBLY STOCHASTIC NORMALIZATION OPERATOR
In graph convolution operations, we utilize edge feature matrices as filters to perform element-wise multiplication with the node feature matrix. To prevent an undesired increase in the magnitude of the output features due to this multiplication, it is essential to normalize the edge features. Let's denote the raw edge features as E. We can obtain the normalized features, denoted as E, using the following procedure of doubly stochastic normalization operator.
Eip
Bijp
(11)
N Lk
Eikp
Eekop Eeghp
Eijp
(12)
Ev=1 Eukk
where E' is tensor representing the edge features of the graph; Eg R" represents the P- dimensional feature vector of the edge connecting the i-th and j-th nodes; Enp denotes the p-th channel of the edge feature in Esj. In addition, when the i-th and j-th points are not contiguous, Eijp for any p. Such kind of normalized edge feature tensor E has the following properties.
Fajp 20 0, N
(13)
N Σ j=1
Eajp
Eajp =
(14)
In simpler terms, the edge feature matrices É, where p ranges from to P, are square, nonnega- tive real matrices in which both the rows and columns sum up to 1. This property classifies them doubly stochastic matrices, meaning they exhibit both left and right stochastic characteristics. In mathematical terms, when you have a finite Markov chain with a transition matrix that is dou- bly stochastic, it will have a uniform stationary distribution. Now, in the context of multi-layer graph neural network, these edge feature matrices undergo repeated multiplication across the layers. Utilizing doubly stochastic normalization can enhance stability in this process.
A.4 FENNEL GRAPH PARTITION ALGORITHM
Algorithm 1 FENNEL-based Graph Partition Algorithm
Input: The number of blocks k. graph G (V,E), parameters μ4 Init: Label F = {. block P = {t)... 0}
< V
m [3]
vi_ 33/2
load miad_iimite- 2
for 1 to do
for = to & do
if P:] < load_limie then
(v)) + {u, (u. E
(u,
(P,N(()) a
end if
end for
ind <- argmax, (v, P.)
Add e into P;
Flv) <- ind
end for Return: F
For graphs the million-level scale, the streaming graph partitioning algorithm is commonly em- ployed. There exist two primary heuristics for streaming graph partitioning. On one hand, newly arrived vertices are placed in the cluster with the greatest number of neighbors. On the other hand,
13

---

Published as a conference paper at ICLR 2024
they can be placed in the cluster with the fewest -einngegboor... FENNEL, however, introduces an innovative approach by combining these two heuristics.
Formally, for graph G (V,E) comprising vertices and edges, to be partitioned into k blocks, FENNEL aggregates vertices with dense edges into a single block, while segregating vertices with sparse edges into separate blocks. More specifically, it systematically evaluates each newly arrived vertex v in the graph, one by one, and computes 5n (v. P.) for each block P. that satisfies [P] < D as follows:
(u P.) t [P: N())) P.)
(15)
where ((v) denotes the neighbor node set of v, v, 7 are preset parameters related to block balancing and minimum cut, and = v m shown in Algorithm
denotes the balance of two types of heuristics. The details are 37/2
A.5 INITIAL SOLUTION PREDICTION
The initial solution prediction based machine learning often uses Graph Convolutional Neural Networks (GNN) to predict the initial solution of the complete problem (Gasse et al.] 2019 Nair al.. 2020 Sonnerat et al. 2021 Ye et al., 2023b). However, this approach faces two major chal- lenges. On one hand, as the problem scale increases, the required storage resources, especially GPU memory, steadily rise, making difficult solve large-scale or even super-large-scale problems. On the other hand, GNNs achieve initial solution prediction by learning the distribution mapping of isomorphic mixed- -ntteeer problems to optimal solutions. However, in more complex problems, the predicted solutions obtained using this method are often infeasible.
To overcome the shortcomings of existing methods, we propose a novel initial solution prediction strategy. To address the first problem, we propose using the FENNEL graph partitioning algorithm to decompose large-scale Mixed-Integer Linear Programming (MILP) into several smaller subprob- lems. We predict the optimal solution for each subproblem and concatenate them to obtain the initial feasible solution for the complete problem, allowing training and inference to be performed only on small-scale problems. Regarding the second problem, previous work attempted to predict the prob- ability of each point being set to 1. Then, for parameters (Ko, k1), ku probabilities with the highest values fixed to 1, and kn probabilities with the lowest values are fixed 0 (Han et al.) (023). However, this method requires setting different hyperparameters for different problems. Therefore, for Mixed-Integer I. Linear Programming problems, we propose using the Repair algorithm to obtain a feasible solution from the current solution. This algorithm identifies illegally constrained decision variables. cancels the predictions for these variables, uses small-scale solver to solve for the initial values of the canceled decision variables, and ultimately obtains feasible solution. See Appendix Algorithm 5 for details on the Repair algorithm.
It's worth notice that the framework's 's solving approach is designed for problems with the same struc- ture and mathematical properties. It involves unified training, prediction, and neighborhood search to obtain optimized solutions. Additionally, it can efficiently handle large-scale problems using only small-scale training data. For problems with different properties, a sccondary training process is required to construct new feasible solution prediction model tailored to the specific problem. For example, problems with different scales of minimum point cover can be trained together. However, if the goal shifts to solving minimum set cover problems, new feasible solution prediction model needs to be retrained.
A.6 INITIAL SOLUTION SEARCH
Given the predicted value OJ and the prediction loss P, for each decision variable, the decision vari- ables are arranged in ascending order based on their prediction losses. For the pre-defined coefficient a E (0, 1) which denotes that the lightweight optimizer can solve small-scale MILP containing at most an decision variables, the first (1 ajn decision variables are held constant, while the maining variables are explored within a predetermined fixed radius. The specific steps are outlined in Algorithm
In Algorithm, 77 E (0, 1) is a reduction coefficient used to expand the fixed proportion, REPAIR ( the function shown in Appendix A.8.
14

---

Published as a conference paper at ICLR 2024
Algorithm 2 Initial Solution Search
Input: The number of decision variables n, predicted value ú, prediction loss P, variable propor-
tion
Init: Initial Solution X'
X' < 9
Sort the decision variables in ascending order of p
aset a
repeat
F < The first (1 - Oset) decision variables D-Fixed
u The last Okset decision variables
>UUnfixed
F 1' f- REPAIR(F,U X) if [2' > an then
Qest = 17 Ceett
end if
until [4') < on X <- SEARCH(F' ())
Return: X
A.7 NEIGHBORHOOD SEARCH AND INDIVIDUAL CROSSOVER
Specifically, for the i-th neighborhood N, Algorithm 3 shows the details in neighborhood search.
Algorithm Neighborhood Search
Input:
The set of decision variables X, the number of decision variables n, predicted value g, prediction loss P, variable proportion neighborhood Nnow, current solution X
Init: Neighborhood search solution X' = 0
Sort the decision variables in N Noww in descending order of P: lob. Úel
A The first am decision variables in Nnow
F <- { E X A N}
>> Fixed
U + { E X A E N X' < SEARCH(F,U,A)
Unfixed
Return: X"
where P,, X₂ and h. denotes the prediction loss, the value in the current solution and the predicted value of the i-th decision variable respectively.
Algorithm Neighborhood Crossover
The set decision variables X, the number of decision variables n, neighborhood N2, neighborhood search solution X Ki
Input:
Init: Neighborhood crossover solution = (
X" ()
for i = to n do
if The i-th decision variables in Ni then
X" + x7
else
X + X
end if end for
F +- X U 0
>-Fieed >Unffiee
F' Fllll .1' +- REPAIR(F..F. (F, if [4' am then
E < SEARCH( (U""")
end if
Return: X
15

---

Published as a conference paper at ICLR 2024
Given that the size of the neighborhood is constrained most on, there is a heightened risk of becoming trapped in local optima due to the limited radius the neighborhood search. Conse- quently, neighborhood crossover plays pivotal role. Algorithm outlines the specific procedure for crossing two neighborhoods, denoted as N₁ and N2.
A.8 REPAIR ALGORITHM
Algorithm 5 REPAIR Algorithm
Input: The set of fixed variables F, the set of unfixed variables U. the current solution X (,, u} t- The coefficient of the given MILP <- the number of decision variables
m < the number of constraints
for i to do
NV < 0
for j to do
if The j-th decision variable E F then .V < N X2 Asj
else
A. > 0 then
N + N + Aij
end if
if Ag < then
N + N + uy An
end if end if end for
if M
> b, then
for j = if The j-th decision variable F then Remove the j-th decision variable from F Append the j-th decision variable into M
do
N N X, * As,j
if A. > 0 then
N + N + 1 Ar
end if
A. < 0 then
N . + uj A
end if
if N by then
BREAK
end
end if end for
end if
end Return: F,u
The initial solution search, neighborhood search and individual crossover with a lightweight opti- mizer for MILP are widely used in the proposed framework to improve the current solution, which can be written as the following.
min Tx ag.
subject Ar b,1 S x E Z.j EI, 24 Vx: F
(16)
where z; represents the value the i-th decision variable in the current solution, and F refers to the set of decision variables fixed to their current solution values. However, it is worth noting that
16

---

Published as a conference paper at ICLR 2024
the Mixed-Integer MILP corresponding to Equation (16) may become infeasible, resulting in the failure of the current solution. To address this issue, we introduce a REPAIR Algorithm designed to examine and rectify constraints that are inherently infcasible by removing the fixation of certain illegal variables associated with these infeasible constraints.
In particular, when dealing with given Mixed-Integer Linear Programming (MILP) problem along- side a set of fixed variables denoted as FF the REPAIR algorithm systematically iterates through each constraint within the MILP. For each constraint under consideration, the algorithm assesses whether it is inevitably infeasible based on the upper and lower bounds of unfixed variables. If the algorithm determines that the constraint is indeed destined to be infeasible, proceeds release the fixation of specific decision variables associated with the constraint, aiming to restore its feasibility. The intricate steps of this process are elucidated Algorithm
A.9 PROBLEM REDUCTION RATE
Regarding the chosen dimension reduction ratio (at), it can indeed only be at (O(1)) level, and achieving a final subproblem significantly smaller than the original problem is not feasible. How- ever, this has crucial practical implications. For mixed-integer programming problems, people typ- ically resort to solvers. The scalability solvers depends on both internal algorithmic settings and the user's machine configuration. In a given solver environment and computational resource con- straints, individuals can only solve problems within a specific size limit, for example, those with k decision variables. Previous research on machine learning-basse solutions for large-scale mixed- integer programming problems also often required solvers of the same size as the problem being (ackled(Sonneeee et al. 2021 Wu al., 202T).
In our work, we introduced a dimension reduction approach that simultancously operates on the decision variable and constraint levels. In our test problems, when the number of decision vari- ables reduces to 30% and the number of constraints reduces to 20% of the original problem, our framework can still generate high-quality feasible solutions. This implies that within a given solver environment and computational resource constraints, we can surpass the limits imposed by solving problems of specific sizes (c.g., with (k) decision variables) and efficiently solve larger-scale mixed- integer programming problems (c.g.. with (2k) (3k) decision variables). Therefore, proposing the dimension reduction ratio (a) not only improves the efficiency of problem-solving but also serves inspiration for overcoming physical resource constraints in solving
larger-scale problems.
is worth notice that the choice of the decision variable reduction parameter a (which is set at approximately 30% based empirical findings (Nair et al. (2020) is fixed at the beginning and mains small-scale throughout the run; it does not change during the run to large-scale. For constraint reduction, reduce the drawbacks of empirical settings, we adopt progressive strategy. Initially, more constraint conditions are retained, and optimization progresses, redundant constraints are automatically identified based on the current solution. The number of constraint conditions gradu- ally decreases through the removal of redundant constraints. Practical experiments have shown that for most baseline tests, we can achieve a reduction of decision variables 30% and constraints to 20% of the original problem size. The automatic selection of a is our next research goal, and we will explore learning algorithms to automatically determine the value of a. is worth mentioning that with the variation of the final value is generally a unimodal function, effectively achieving the use of a certain scale of small-scale solvers to solve large-scale problems.
B EXPERIMENTS DETAILS
B. EXPERIMENTAL SETTINGS
All experiments machine with Intel Xeon Platinum 8375C @ 2.90GHz CPU and four NVIDIA TESLA V100(32G) GPU. Each scale of any Benchmark MILP is tested on five different instances, and the results shown the average of the five results.
17

---

Published as a conference paper at ICLR 2024
B.2 BASELINES
In this paper, two types of baselines are employed. One type of the baselines is the latest ML-based optimization framework based GNN al. (023b). The other type of baselines (Achterberg] 2009) and Gurobb(10.0.1) (Achterberg 2019). Their scale-constrained versions are used as the lightweight optimizer for both the proposed iramework and the latest ML-based optimization framework.
is the state-of-the-an MILP solvers, including SCIP(4.3.0)
In the comparative experiments with the advanced solver Gurobi (or SCIP), Gurobi is utilized in three instances: first, as the baseline solver; second, within the baseline machine learning frame- work GNN&GBDT, Gurobi with decision variable scale constraints is employed as a small-scale optimizer; third, in the proposed framework Light-MiLPopt, Gurobi with decision variable scale constraints is used as a small-scale optimizer. all these cases, Gurobi is used with default settings, without any parameter modifications, for reading and solving the problems. This approach of using solvers with default settings for fair comparisons is a common practice in prior works (Gasse et al, 2019
Nair et al. 2020 Sonnerat et al. 2021 Ye et al. 2023b Wu et al. 202I).
B.3 DATASET
For the four widely used NP-hard benchmark MILPs, the existing data set cannot meet such large- scale data requirements, we use data generators to generate training and test data sets. Specif- ically, for the Maximum Independent Set problem (MIS) or Minimum Vertex Covering problem (MVC) with n decision variables and m constraints, we generate a random graph with nodes and m edges to correspond to an MILP that meets the scale requirements. For the Set Covering problem (SC) with n decision variables and m constraints, we generate a random problem with n items and m sets where each set bid includes 4 items. For the Mixed Integer Knapsack Set (MIKS) with n decision variables and m constraints, we generate a random problem with items and m dimension where each dimension includes 4 items and at least half of the items are items with integer con- straints. For the optimal solution in the training data set, we use Gurobi to run for 8 hours to find the approximate optimal solution.
The decision variables and constraint scale of the one case study in the internet domain and four widely used NP-hard benchmark MILPs are shown in Table B
The size of one real-world case study in the internet domain and four widely used NP- hard benchmark MILPs. SC denotes the Set Covering problem. MVC denotes the Minimum Vertex Covering problem. MIS denotes the Maximum Independent Set problem. MIKS denotes the Mixed Integer Knapsack Set problem. Case Study denotes the real-world case study.
Table 3:
Number of Number of
Problem
Scale
Variables
Constraints
SC
SC₁
200000
200000
(Minimize)
SC₂
2000000
2000000
MVC
MVC,
100000
300000
(Minimize)
MVC₂
1000000
3000000
MIS
MIS
100000
300000
(Maximize)
MIS
1000000
3000000
MIKS
MIKS
200000
200000
(Maximize)
MIKS
2000000
2000000
Case Study
Case Study
2040000
100003
(Maximize)
C ADDITIONAL EXPERIMENTAL RESULTS AND DISCUSSIONS
C.I COMPARISON OF CONSTRAINTS REDUCTION
To facilitate ablation experiments concerning constrained reduction, pivotal innovation within Light-MILPop and to validate the efficacy of this technique, we conducted a comparative anal- ysis. We evaluated the solution outcomes of our proposed frameworks under two conditions: with
18

---

Published as a conference paper at ICLR 2024
Table 4: Comparison of the solving results of the Light optimization framework with constrains reduction and without constrains reduction for fixed runtime. With-30%S means the proposed framework with the scale-limited versions SCIP which limit the variable proportion to 30% and with constrains reduction. Without-50%S means the proposed framework with the scale-limited versions of SCIP which limit the variable proportion a 50% and without constrains reduction.
SC₂
MVC₂
MIS
MIKS,
With-30%5
166756.0
273014.6
227074.5
355887.6
Without-300 30%S
167169.5
292510.1
174894.4
354614.6
With-50%S
166966.9
269771.3
230278.1
357483.8
Without-5006 50%%
197515.8
284936.2
190243.5
349676.3
Time
12000s
8000s
8000s
12000s
Table 5: The size of three -rrra-arge--calle benchmark MILPs. SC represents Set Covering, MVC
represents Minimum Vertex Cover, and MIS represents Maximum Independent Set.
SC₁
MVC3
MIS,
Number of Variables Number of Constraints
20000000
10000000
10000000
20000000
30000000
30000000
and without constrained dimensionality reduction. This evaluation was performed on four standard large-scale Mixed-Integer Linear Programs (MILPs) under fixed solution time constraints. The re- sults of these experiments presented in Table The findings from our experiments demonstrate that constrained reduction significantly enhances the performance of our framework across all test problems. It effectively improves the framework' ability to find solutions and boosts overall solving efficiency.
C.2 FURTHURE ANALYSIS OF CONVERGENCE
To delve deeper into the solution performance and convergence capabilities of Light-MILPopt across varying problem sizes, conducted a comprehensive analysis. We generated time-objective func- tion plots for our proposed framework as well as baseline algorithms, utilizing Gurobi as a sub- solver, across a range of standard benchmark MILPs. The experimental results, depicted Figure and Figure [ unequivocally demonstrate the superiority of our proposed framework. Regardless of the problem size, it consistently outperforms the baseline algorithm, producing higher-quality solu- tions within fixed time constraints. Furthermore, our framework exhibits convergence performance on par with that of the commercial solver Gurobi.
C.3 COMPARISON ON ULTRA-LARGE-SCAN MILPS
We extend the generalization capabilities the proposed Light-MILPopt method, trained on small- scale data with decision variables and constraints in the order of tens of thousands, to solve problems with decision variables and constraints in the order of tens millions. The problem scales are illustrated in the Table 5 where SC represents Set Covering, MVC represents Minimum Vertex Cover, and MIS represents Maximum Independent Set.
The solution results presented in the Table 6 where Ours-30%S and Ours-50% represent the sults of the proposed framework using only 30% or 50% of the original problem scale for lightweight small-scale SCIP solving. SCIP indicates the results obtained directly using the baseline solver SCIP. is evident that the proposed Light-MILPopp method maintains a significant advantage over the baseline solver, even when dealing with problem scales in the order of tens of millions for both decision variables and constraints.
C.4 ANALYSIS OF GENERALIZATION CAPABILITIES
The proposed solution method for solving large-scale MILPs based on EGAT with half convolutions structure is notable for its of the FENNEL-based problem partitioning strategy. This strategy
19

---

Published as a conference paper at ICLR 2024
323000
Ours30%
100000
GNNSCBDT30SG GNNSCRDT 505CC Guro
Objective
Objective
240000
31,0000
300020
0urs50%
210300
GNNGG
GNNGGB DT50NG
250320
270020
2002
5000
Time
Time
(a)
230320
Ours500% Guroti
225000
325050
Objective
212000
Objective
190000
250000
182000
Durs509GG
Ours303sG
225000
272000
200000
GNN6G8OT50%G
342000
Gurobi
175000
2000
4:00
6000
2000
0000
6000
8000
16000
12000
Time
Time
(c)
(d)
Figure Time-objective figure for the large-scale benchmark MLIPs. (a) The minimized SC₂ problem. (b) The minimized MVC, problem. (c) The minimized MIS problem. (d) The minimized MIKSa problem.
Table Comparison of the solving results of the Light-MILPopt optimization framework with SCIP on three Ultra-large-sear benchmark MILPs. With-30%S means the proposed framework with the scale-limited versions of SCIP which limit the variable proportion a to 30%. With-50% means the proposed framework with the scale-limited versions of SCIP which limit the variable proportion to 50%.
SC3
MVC;
MIS;
0urs-30% G
1667157.94
2724414.73
2267990.75
0urs-50%
1603278.85
2694126.35
2299504.56
Gurobi
3198747.63
2834161.28 .28
2165906.72 72
Ours-30% SS%
1672097.50
2731152.61
2256644.32
Ours-50% S
2889696.49
2696953.27
2299950.04
SCIP
9190301.09
4909317.99
90750.01
Time
80000s
80000s
80000s
decomposes large-scale MILPs into several smaller subproblems, predicting the optimal solution for each subproblem and concatenating them to obtain the initial feasible solution for the complete problem. This approach allows training and inference to be performed exclusively on smaller-scale problems, Therefore, for specific new optimization problems, it is not constrained by the decision variable and constraint quantities of existing training datasets, demonstrating robust generalization capabilities across different scales of new optimization problems. For instance, while the training dataset comprises small-scale data with decision variables and constraints in the order of tens of thousands, the testing dataset includes problems with decision variables and constraints ranging from hundreds of thousands millions, as shown in Table T and Table
20

---

Published as a conference paper at ICLR 2024
Ours30%
25000
DursSONG
14000
Ours507G
GNNGGBDT30NG
GNNGGEDTBOSS
CNNSCROTS0NG Gurobi
13000
CANAGBOTSONI4 Gurobi
Objective
Objective
22000
11000
20000
18000
20000
16000
27000
1000
3:0
15:00
Time
Time
(a)
(b)
23200
12500
Objective
Objective
19000
37500
18200
Our:50%G
22500
GNN5G8DT30NG
30%G
Gurcii
Gurabi
17500
Time
Time
(c)
(d)
Figure 7: Time-objective figure for the medium-scale benchmark MLIPs. (a) The minimized SC₁
problem. (b) The minimized MVC, problem. (c) The minimized MIS, problem. (d) The minimized MIKS; problem.
Table 7: Comparison of initial solution prediction results applying only small-scale training data versus using mixture of small-scale and medium-scale training data. Ours-30% means the pro- posed framework with variable proportion a to 30% using only small-scale training data. MIX-30% means the proposed framework with variable proportion a 50% using mixture of small-scale and medium-seat training data.
SC
SC₂
MVC,
MVC,
MIS
MIS,
Ours-30%
29962.09
295981.16
34634.96
346677.69
15275.82
158352.06
MIX-30% %
28882.44
290205.17
31788.13
318258.13
14577.61
152015.11
Ours-50%
30694.93
312419.34
33280.27
333192.51
16384.02
167161.47
MIX-50% %
29710.68
300873.89
32424.85
323032.42
16044.14
162911.65
The proposed method also demonstrates adaptability to different scales of training data and uniform learning capabilities. Even when training data vary in scale, the model can be trained consistently and coherently. We supplement the results of training using mixture of small-scale and medium- scale training data, shown in Table 7 Specifically, Ours represents the results of training with only small-scale training data, while Mix represents the results of training with the addition of medium- scale training data on top small-scale training data. The results indicate that, in the case of SC and MVC problems, adding medium-scale training data enhances the generalization capability for initial solution prediction in large-scale data. Meanwhile, for MIS problems, the addition of training data of different scales yields results comparable to those without further improvement, suggesting satu- ration in the training data for the specific problem. Thus, even when using training data containing problems of different scales, the trained model can efficiently solve large-scale problems.
21

---

Published as a conference paper at ICLR 2024
Table 8: Comparison of initial solution prediction results using confidence threshold versus using SelectiveNet. Ours-30% represents the initial feasible solution results obtained by reducing deci- sion variables to 30% of the original problem using confidence threshold- based reduction, while SelectiveNet-5099 represents the results obtained by reducing decision variables to 50% of the orig- inal problem using SelectiveNet.
SC₁
SC₂
MVC₁
MVC₂
MIS
MIS
00rs-30%
29962.09
295981.16
34634.96
346677.69
15275.82
158352.06
SelectiveNet-309
25605.41
261728.93
49993.15
500171.37
13804.92
145147.94
Ours-50% %
30694.93
312419.34
33280.27
333192.51
16384.02
167161.47
SelectiveNet-50% 25605.41
261728.93
49993.15
500171.37
13804.92
145147.94
Table 9: Comparison of the selection of network structure in initial feasible solution prediction. Var-30% represents predicting 70% of decision variables, and the remaining 30% are solved using small-scabe solver.
GNN&GBDT
GAT
EGAT
Var- 10-330% %
1817.3
1530.7
1872.3
Var-40 %
1928.5
1681.8
2002.3
Var-50
2007.0
1838.2
2067.9
Var-60
2036.1
1987.8
2096.5
C.5 ABLATION STUDIES
C.5.1 VARIABLE REDUCTION METHODS
For the choice of decision variable reduction strategy, we compare two methods: SelectNet and con- fidence threshold- based reduction. The experimental results are presented in the Table The results indicate that SelectiveNet selected in this paper has an advantage one of the three problems and is noticeably inferior in the remaining two problems compared the current method. Considering that SelectiveNet requires retraining the network for different reduction ratios, whereas the confidence threshold breshold-based method requires training only once and can be used for different reduction ratios, we ultimately chose the confidence threshold-basee selection method. Furthermore, further analysis revealed that the fixed selection threshold in SelectiveNet led conservative model predictions. In subsequent experiments, we combined the strengths of SelectNet and confidence threshold- based methods, resulting in better overall results.
C.5.2 NETWORK STRUCTURE SELECTION
In the model-based initial solution prediction module, classical methods often graph convo- lutional neural networks (Nair et al. 2020) Gasse et al.) 2019). However, these methods do not consider different correlations between neighborhoods. Therefore, Ding et al. (2020) introduced the GAT with an attention mechanism to capture correlations between points for better initial solution prediction. However, this GAT only updates node features and ignores the positive impact of edge feature updates on neighborhood aggregation. Therefore, we further introduced the EGAT (Gong & Cheng, 2019) with an edge update mechanism, combined with half convolutions layers for higher computational efficiency. We also compared the above methods and prediction methods based on GNN&GBDT Yee et al. 2023b) in the preliminary exploration.
So we compare the selection of network structure in initial feasible solution prediction. In our earlier exploration, we tried the GNN&GBDT structure, the integrated GAT structure, and the integrated EGAT structure with multiple layers of half convolutions layers. We conducted comparative tests on small-scale maximization MILP problems, where Var-30% represents predicting 70% of decision variables. and the remaining 30% solved using small-scak solver. Higher values indicate better predictive performance. The results are shown Table D It show that the current method, which adopts the EGAT method with multiple layers of half convolutions, has clear advantage.
22

---

Published as a conference paper at ICLR 2024
Table 10: Comparison of the proposed framework and Gurobi's initial solution generation. Ours- 30% represents predicting 70% of decision variables, and the remaining 30% are solved using
scale-limited versions of Gurobi which limit the variable proportion 30%.
SC₁
SC2
MVC1
MVC₂
MIS]
MIS₂
Ours-30%
29962.09
295981.16
34634.96
346677.69
15275.82
158352.06
Ours-50%
30694.93
312419.34
33280.27
333192.51
16384.02
167161.47
Gurobi
32040.60
320272.92
33802.45
338198.32
16190.70
161973.05
Table 11: Comparison of initial solution generation time between the proposed framework and Gurobi.
SC₁
SC2
MVC,
MVC2
MIS
MIS₂
Ours- Time
68.88s
655.00s
53.81s
495.38s
49.60s
480.74s
Gurobi-Time 336.77s
3399.88s
375.37s
2702.16s
279.23s
2742.89s
C.5.3 INITIAL SOLUTION GENERATION STRATEGIES
We compare the initial solution generation capabilities of the proposed method with commercial solver Gurobi on three standard benchmark problems, that is shown in table TO The results show that, under the same generation time, the proposed method, aided by initial solution prediction, can obtain better initial feasible solutions than Gurobi.
Further analysis shown in table reveells that our initial solution prediction method not only obtains better initial feasible solutions but also significantly improves efficiency compared to Gurobi. It requires only 20% of the time Gurobi needs to generate feasible solutions and achieves better-quality initial feasible solutions.
C.6 ADDITIONAL INSTANCES FROM MIPLIB
To further validate the effectiveness of the proposed method solving initial feasible solutions for complex real-world problems, we conducted tests on real-world problems SCP from MIPLIB. The results demonstrate that the proposed framework can effectively predict initial solutions for real- world problems and efficiently solve them. The table below presents experimental results.
Table 12: Comparison of objective value results with baselines under the same running time on SCP. Ours-30%S represents the results obtained by the proposed framework using a restricted version of SCIP with a solution size limited 30% of original problem, and Ours-50%G represents the results obtained using restricted version of Gurobi with solution size limited to 50% of the original problem.
scpml
scpn2
0urs-30%
718.0
666.0
Ours-50 %S
754.0
700.0
SCIP
807.0
19145.0
Ours-30 % G
662.0
665.0
Ours-50 % G
676.0
604.0
Gurobi
836.0
793.0
Time
2000s
2000s
D ADDITIONAL INFORMATION ON MILPs
Mixed Integer Linear Programs (MILPs) type of problem in which the objective function is linear under several linear constraints, where some or all decision variables are restricted to take integer values, and the other decision variables are real numbers. Formally, an MILP has the form as the following.
min cTa, subject to Ar S b, S u, E,iEl, 2
(17)
23

---

Published as a conference paper at ICLR 2024
where x the decision variables whose number is denoted by 2, with R being their lower bound, upper bound and coefficient, respectively. A E Rmxx" and b E R denote the linear constraints. I {1, 2, n is the index set of integer variables.
A solution is feasible for the MILP if decision variables z E R" satisfy all the constraints in Equation [17 An MILP is infeasible if there exists feasible solution, while it is infeasible if there exists solution that satisfies all of the constraints - in other words, no feasible solution can be constructed
(Guieu & Chinneck 1999).
A feasible solution is optimal if it attains the minimum objective function value of the minimized MILP. An MILP is bounded if there exists optimal solution, while unbounded if the objective function may be improved indefinitely without violating the constraints and bounds (Byrd et al. 1987)
24


Reviews:
[{"review_id": "1UgDJ538Re", "reviewer": "Reviewer_tDoY", "summary": "Problem: this paper studies the problem of using machine learning-based approaches to solve large-scale mixed integer linear programs.\n\nFramework: since the MILP problems can be represented as bipartite graphs, the authors use the FENNEL graph partition algorithm to split the original problem into small sub-problems with low correlations. Then use Edge Aggregated Graph Attention Network and Multi-Layer Perceptron to predict the initial predicted solutions of the small-scale MILP and concatenate them to obtain the initial predicted solutions of the original large-scale MILP. With the initial solution, they confidence threshold method to reduce variable dimension, and use KNN to predict the active constraint set. Then they use Neighborhood set updating, active constraint set updating, and the REPAIR algorithm to iteratively improve solutions.", "questions": "- At the end of subsection 3.2, you mentioned “the initial predicted solutions of the split small-scale MILP can be concatenated to obtain the initial predicted solutions of the original large-scale MILP.” While concatenating the multiple predicted solutions of small-scale problems, it is possible to have an initial solution that is infeasible to the large-scale problem, which part of your framework can handle this?\n- Is it possible to make your framework more flexible in the sense that the number of variables/constraints can be (slightly) different from your training data?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly structured and well-written.\n- From the numerical experiments, the proposed method can obtain better objectives within a limited time than other benchmarks.\n- The proposed framework requires less computational resources to train than other benchmarks.", "weaknesses": "I merge this with the Questions section.", "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": "clt2XJDzIA", "reviewer": "Reviewer_LzLN", "summary": "This paper proposes Light-MILPopt, a lightweight large-scale optimization framework that only uses a small-scale optimizer and small training dataset to solve large-scale MILPs. Experiments show that it outperforms both the SOTA ML-based approaches and modern MILP solvers like Gurobi and SCIP.", "questions": "See weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Clear writing. the paper is very clearly structured and easy to go through flow.\n2. Impressive results on large-scale MILPs. The experiments on large scale MILPs (significantly larger than those used in previous research) is impressive. The results suggest that Light-MILPopt significantly improves both the efficiency and effectiveness of solving MILPs. \n3. Practical motivation. Light-MILPopt achieves such improvement with only a small-scale optimizer and small training datasets. This setting is practical for real-world applications.", "weaknesses": "1. Lack of comparison with previous work. From my perspective, the impressive results in this article are based on the results and approaches in many previous studies. However, both the detailed related work and the empirical comparisons to the previous research are missing. For example, previous research has pointed out that we can use a fixed threshold to replace the complex selective networks, which might motivate the variable reduction approach in this paper. \n2. More analysis and insights on the proposed modules are encouraged. In this paper, the authors proposed multiple techniques to improve the performance of different modules. Though I believe these techniques are all effective, can you give more clues about the motivations of them? For example, What is the logic behind your design of the EGAT with half-convolutions? Is it the only choice for this module?\n3. The nomenclature \"large-scale/small-scale optimizer\" appears unconventional. It might be more precise to employ terminology such as \"advanced/modern MILP solver\" and \"lightweight solver\".\n\nOverall, I appreciate the results in this paper. If the author can provide more details and insights, I am willing to further improve my scores.", "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": "XgbmdVbkRF", "reviewer": "Reviewer_6e4z", "summary": "The paper proposes a light-weight framework for large-scale MILP problems.  The framework consists four stages, and employs advanced machine/deep learning techniques to 1). find and improve solution 2). reduce the original problem into smaller subproblems 3). coordinate between subproblems. Numerical experiments are conducted on large-scale MILP instances to demonstrate the efficiency of the proposed method.", "questions": "1. The four stages in contribution 2 are actually part of contribution 1. Can you combine them?\n\n2. In Section 2.1, \"A feasible solution is optimal if it attains the minimum objective function value of the minimum MILP\". \n\n   What's minimum MILP here? Also it is better to mention unbounded and infeasible MILPs here.\n\n3. How does the approach guarantee feasibility of the solution? \n\n   The challenge of many real-life MILPs is to find a feasible solution. Most of the testing problems in the paper (all except case-study, which is unknown) seem to admit trivial feasible solution. How does your method work on problems like set partitioning?\n\n4. It seems that the framework has more focus on the primal side and cannot help improving dual bound. Is there a way your method can certificate optimality?\n\n5. It is recommended the authors conduct some ablation studies. For example, what if you directly feed the initial solution from *Model-based Initial Solution Prediction* to Gurobi?\n\n6. Table 2 says \"under the same optimization solution\". What if two different solutions have the same objective value?\n\n7. While the paper suggests the approach only needs to rely on small-scale solvers. The choice of variable proportion parameter $\\alpha$ still lead to subproblems of large scale. Will tiny values of $\\alpha$ (e.g., 0.01) give better/worse results?\n\n**Minor typos and stylistic issues**\n\n1. Section 2.4: node information. while on the other hand\n\n   \".\" => \",\"\n\n2. Figure 2 uses MIP instead of MILP. Please be consistent.\n\n3. Figure 2 contains much information and is a bit hard to parse due to massive legends. Is it possible to move \"data-drive\" stage below the first three stages? The rest of space can be used to make legends look better.\n\n4. Table 2: caption\n\n   Comparsion => comparison\n\n5. Page 13: where $E$ is a tensor representing the edge feautres\n\n   feautres => features\n\n6. Table 3: caption\n\n   SC denots the Set Covering problem\n\n   denots => denotes", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The paper proposes a framework that integrates several advanced tools from ML for MILP optimization. By breaking up the problem into subproblems, the framework only needs to be trained on small-scale datasets and exhibits less dependency on the capability of the MILP solver adopted.", "weaknesses": "Overall the presentation the paper is not accessible to the readers. There are a number of grammar and stylistic issues, making it difficult to understand the details of the proposed method.\n\nI also have some concerns around other aspects of the proposed method. See questions below.", "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": "QfYB4fGcK9", "reviewer": "Reviewer_RzQr", "summary": "This paper presents Light-MILPopt, a novel, lightweight optimization framework designed for large-scale Mixed Integer Linear Programs (MILPs). Conventional methods encounter difficulties, including high computational costs and complexities, when applied to large-scale MILPs. Light-MILPopt confronts these problems by adopting a four-stage strategy:\n\nProblem Formulation: MILPs are depicted as bipartite graphs, and computational efficiency is improved through a graph partitioning algorithm.\nModel-based Initial Solution Prediction: This stage involves using a specialized network to predict initial solutions for subproblems, necessitating less computational effort and a smaller, structurally coherent training dataset.\nProblem Reduction: This innovative method selectively diminishes decision variables and constraints, thereby boosting the efficiency of problem reduction.\n Data-driven Optimization: This phase utilizes subgraph clustering and active constraint updating to steer the neighborhood search and optimization processes, iteratively enhancing solutions with limited computational demands.\n\nThrough exhaustive testing against large-scale benchmark MILPs and in real-world situations, the framework has proven its effectiveness. It surpasses current methods, emphasizing considerable reductions in computational requirements and improved problem-solving abilities. Light-MILPopt stands out particularly for its performance with smaller-scale training data and optimizers, establishing a new standard for the resource-efficient tackling of extensive MILPs. The contributions of this paper are crucial, offering a methodology that not only simplifies the computational procedure but also strengthens the strategy for addressing sophisticated, large-scale MILP difficulties.", "questions": "MILP is an NP-hard problem, and, in the worst case, finding an optimal solution in polynomial time is considered impossible (though this has not yet been proven). The No Free Lunch theorem posits that no \"universal\" supervised machine learning model or search/optimization algorithm exists that can efficiently solve every problem (theoretically, it's unfeasible). However, assuming a prior distribution of problem generation, it becomes possible to efficiently solve specific instances with an approach like the one used in this study. Nonetheless, a substantial gap exists, limiting the effectiveness of such methods. The explanation of the limitations and constraints of this method in this context is inadequate.\n\nAnswering all of the following questions in a necessary and sufficient manner would be an onerous task for the authors; therefore, please respond as comprehensively as possible at this juncture.\n\n1: Representativeness and diversity of the dataset: Is the dataset chosen for benchmarking genuinely representative of the diverse spectrum of large-scale MILPs in real-world scenarios? How does the framework handle MILPs with varying attributes or those from different industries? While problems like Set Covering, Minimum Vertex Cover, Maximum Independent Set, and Mixed Integer Knapsack Set are appropriate for this method's application due to their definable problem structure, its effectiveness may be restricted for more complex practical problems. Consequently, using MIPLIB (https://miplib.zib.de/), where issues are meticulously curated for MIP benchmarking, is advisable.\n\n2: Generalizability of results: Considering that Light-MILPopt trains on merely 1% of the large benchmark MILPs, how effectively does the framework generalize to unfamiliar or more intricate MILPs? Is there proof of steady performance across a broader problem set?\n\n3: Fairness and consistency of benchmarks: Were the tests executed under uniform and fair conditions for all methods? Gurobi itself has numerous parameter settings, potentially leading to disputes from Gurobi's developers' standpoint.\n\n4: Detailed comparative analysis: While the summary underscores Light-MILPopt's superior performance relative to other solvers, it doesn't delve into why specific solvers underperform. Are there fundamental inefficiencies or constraints within the baseline solvers leading to subpar outcomes?\n\n5: Robustness and Efficiency: How does Light-MILPopt manage issues of diverse sizes and complexities? Does efficiency wane as the problem's size and intricacy escalate? What are the trade-offs between computational time and solution precision?\n\n6: Solution Quality and Optimality: Light-MILPopt is said to procure better outcomes in a shorter period, but how do these solutions compare to the global optimum? Is there a compromise in solution quality, risking a mere local optimum?\n\n7: Convergence Analysis: While convergence performance is broached, are scenarios where Light-MILPopt fails to converge efficiently identified? Comprehending its conduct under unfavorable conditions is also crucial.\n\n8: Training scalability: Given the framework's high efficacy with sparse training data, has there been an exploration of how augmenting training data influences performance? Is there a threshold where the benefits diminish, or does efficiency perpetually enhance with additional data?\n\n9: Analysis of real-world applications: The study incorporates real-world instances, but is this scrutiny exhaustive? Are the distinct constraints and hurdles present in real-world scenarios considered, and how does the system accommodate them?\n\n10: In (1) on page 2, the definition is not MILP (Mixed Integer Linear Programming Problem) but ILP (Integer Linear Programming Problem)", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper emphasizes the unique strengths of the Light-MILPopt framework for large-scale Mixed Integer Linear Programs (MILPs). Key highlights include its revolutionary four-stage process that enhances problem-solving efficiency and effectiveness, and its notable resource efficiency, being the first to tackle extensive MILPs with minimal computational resources. Light-MILPopt utilizes cutting-edge computational methods, effectively reduces problem dimensionality, and its efficacy is confirmed through rigorous testing, outperforming existing models. The framework significantly contributes to future MILP endeavors, particularly in efficiently solving substantial problems with limited resources.", "weaknesses": "The Light-MILPopt framework, despite its innovative approach to large-scale Mixed Integer Linear Programs (MILPs), faces critical limitations, including questions of scalability and generalization due to its dependence on small-scale training data. The complexity inherent in its advanced problem formulation and division techniques may hinder practical application, necessitating specialized expertise. The framework's simplification strategies in problem reduction could potentially neglect essential problem aspects, compromising solution integrity. Additionally, its heavy reliance on model-based predictions introduces risks of inaccuracies, and the lack of detailed validation experiments obscures comprehensive performance assessment. Finally, comparisons with advanced solvers appear limited to certain metrics, calling for a more exhaustive evaluation. Overall, these issues indicate the need for cautious implementation and enhanced development for broader applicability.", "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)