L2P-MIP: Learning to Presolve for Mixed Integer Programming
Authors: Chang Liu
Zhichen Dong
Haobo Ma
Weilin Luo
Xijun Li
Bowen Pang
Jia Zeng
Junchi Yan
Venue: ICLR 2024 poster (2024)
Keywords: Combinatorial Optimization; Mixed Integer Programming; Presolving
Primary area: general machine learning (i.e., none of the above)

Abstract: Modern solvers for solving mixed integer programming (MIP) often rely on the branch-and-bound (B&B) algorithm which could be of high time complexity, and presolving techniques are well designed to simplify the instance as pre-processing before B&B. However, such presolvers in existing literature or open-source solvers are mostly set by default agnostic to specific input instances, and few studies have been reported on tailoring presolving settings. In this paper, we aim to dive into this open question and show that the MIP solver can be indeed largely improved when switching the default instance-agnostic presolving into instance-specific presolving. Specifically, we propose a combination of supervised learning and classic heuristics to achieve efficient presolving adjusting, avoiding tedious reinforcement learning. Notably, our approach is orthogonal from many recent efforts in incorporating learning modules into the B&B framework after the presolving stage, and to our best knowledge, this is the first work for introducing learning to presolve in MIP solvers. Experiments on multiple real-world datasets show that well-trained neural networks can infer proper presolving for arbitrary incoming MIP instances in less than 0.5s, which is neglectable compared with the solving time often hours or days.

Published as a conference paper at ICLR 2024
L2P-MIP: LEARNING TO PRESOLVE FOR MIXED INTEGER PROGRAMMING
Chang Liu', Zhichen Dong', Haobo Ma', Weilin Luo?, Li², Bowen Pang", Jia Zeng". Junchi Yan-* 'Department of Computer Science and Engineering, Shanghai Jiao Tong University Huaawi Noah's Ark Lab
(only-changer, ptrcchanger,nconnil1.. miconi19, witcher, yetccheryannjunchi 8sjtu.
(lucweilins, pangbowen2, jijun. -1, zeng. @ com PyTorch Code: https: /titthu.
thub. com / http://hnnkaab-suu//------
ABSTRACT
Modern solvers for solving mixed integer programming (MIP) often rely on the branch-and aad---und-bddddd (B&B) algorithm which could be of high time complexity, and presolving techniques are well designed to simplify the instance as pre-processing before B&B. However, such presolvers in existing literature open-source solvers are mostly set by default agnostic to specific input instances, and few studies have been reported on tailoring presolving settings. In this paper, we aim dive into this open question and show that the MIP solver can be indeed largely improved when switching the default instance-agnosse presolving into instance-spect specific presolving. Specifically, we propose a combination of supervised learning and classic heuristics to achieve efficient presolving adjusting, avoiding tedious reinforcement learning. Notably, our approach is orthogonal from many recent efforts in incorporating learning modules into the B&B framework after the presolving stage, and to our best knowledge, this is the first work for introducing learning to presolve in MIP solvers. Experiments on multiple real-world datasets show that well-trained neural networks can infer proper presolving for arbitrary incoming MIP instances in less than 0.5s, which is neglectable compared with the solving time often hours or days.
INTRODUCTION AND RELATED WORK
Mixed integer programming (MIP) is a general optimization formulation of various real-world optimization applications, such as scheduling and production planning. In its commonly studied linear form, MIP minimizes linear objective function over a set of integer points that satisfy finite family of linear constraints. Due to its NP-hard nature, in modern MIP solvers (SCIP (Gamrath et al., 2020), GUROBI (Gurobi, 2021), CPLEX (IBM, 2021)), the branch-and-bourd (B&B) algorithm widely employed. B&B traverses the candidate solutions systematically, in which the set of candidate solutions is considered to form a search tree with the full set at the root. However, B&B can suffer from severe scalability issues in branching selections, especially for real-world applications.
Efforts have been made to reduce the time cost of B&B by including an extra step: given an MIP instance, the solver first pre-processes and simplifies the instance before passing it to B&B. This step is usually named Presolve, and various presolvers have been designed to reduce the size of the input instance. Via presolving, the original MIP instance is simplified by removing irrelevant information e.g. redundant constraints and variables. After presolving, B&B only needs to solve the smaller simplified instance. Though the presolving step itself does cost extra time, it leads to a great time saving for the B&B algorithm, and in total improves the performance of the MIP solver significantly (Achterberg et al., 2019). has been shown early studies (Bixby al., 2004; Achterberg & Wunderling, 2013b) that, after appropriately presolving. 1.3x speed up can be acquired and more than 15% unsolvable instances become solvable within the time limit. Due to the page limit, we place the description of the commonly used presolvers in the Appendix (A.1).
*Correspondence author. The work was in part supported by National Key Research and Development Program of China A202AAA00007000,, Huawei Technologies, NSFC (62222607). and SJTU Trans-med Awards Research (STAR) 20210106.

---

Published as a conference paper at ICLR 2024
MIP Instance
Presevingg
Simplified MIP festance
Branch and Bound Algarithm
c's
c'
Or
Preselvee
Start
Step
Step
jut
Proside Oytimmal Solittion
Preselver Paol
Prove Infeesible
Figure 1: Presolving MIP solvers. For each incoming MIP instance, the solver first presolves to simplify the problem, which includes multiple rounds and the utilization of multiple presolvers. Then, the simplified instance passed to the B&B algorithm and solved.
In existing MIP solvers, presolving is routinely adopted by the default setting, being agnostic to input instances. As the default setting may not always suitable, several works (Hutter et al., 2009; 2011; Lindauer et al., 2022) propose to find one single robust configuration (setting) for all problem instances. However, they still can not tailor presolving for each unseen instance. In this paper, we argue that tailoring suitable presolving for each individual instance could reach better performances. Researchers of the latest work (Galabova, 2023) conclude that "an analysis of presolve would be incomplete without an investigation of this effect for particular instances". which necessitates instance-specifte tailoring presolving. Moreover, the value of instance-specific tailoring in presolving has been empirically shown in (Frank et al., 2010).
To this end, we try to design an efficient method that can tailor presolving for MIP instances, which able to integrate into existing MIP solvers. In general, customized presolving includes how to pick the next presolver (determine the order), limit the max used rounds of each presolver, and set the time used for each presolver. Especially, some of the operations can be related to each other, for example, the order of the presolvers can influence their utilization rate and efficiency. Hence, finding the best presolving is challenging task and remains under-studied in literature.
To achieve instance-adaptive presolving, one provable way is using heuristic algorithms to search for the best presolving. However, heuristic searching can be too time-consuming to serve as a pre-processor. To improve efficiency, neural networks can be used to fit the behavior of heuristic algorithms, since neural networks can infer the suitable presolving in a short time. More specifically, by taking a closer look at the presolving parameters, argue that the priority is more influential and can affect the other parameters since priority determines the execution order of presolvers. As shown in many previous works (Elble, 2010; Lodi & Tramontani, 2013; Galabova, 2023), the performance of presolving is very sensitive to the order of the presolvers.
In this paper, we propose hybrid algorithmic neural framework for improving presolving, namely Learning to Presolve (L2P). Firstly, we modify simulated annealing to search for the most suitable presolving given each instance. Then, we adapt neural networks that learn the mapping from instance to the found presolving. When applied to unseen instances, the well-traine trainer neural networks can infer suitable presolving considerably short time (less than 0.5s in the experiments). Besides, considering the attributes and relations among different presolving parameters, we decide to build hybrid inference networks, which the priority is regarded as prior knowledge to guide the learning.
We conduct experiments on popular MIP datasets with scales from small to large and two industry- level datasets. Results show that there is indeed much room for improvement in the default presolving of MIP solvers, and the solver can be indeed largely improved when switching the default instance- agnostic presolving into instance-specifi presolving by L2P. This suggests that default presolving is a performance-liminn -imitinn factor of the solver and deserves more attention. We consider this task could be a new direction for using machine learning technologies to further improve MIP solvers.
The related works cover different aspects, including solving MIP instances, presolving in MIP solvers, and auto configuration, which we leave in Appendix A.2. The highlights of this paper are four-fold:
1) To the best of our knowledge, this is the first work in literature proposing adaptively tailored presolving w.r.t. MIP solvers. Better presolving could significantly reduce the time consumed in solving MIP instances but few works in the literature consider improving it.
2

---

Published as a conference paper at ICLR 2024
2) We propose a hybrid neural framework equipped with heuristic algorithms as supervision to predict the suitable presolving for each imput MIP instance, which combines the advantage of searching effectiveness of heuristic algorithms and inference efficiency of neural networks.
3) Experimental results on both public and private industrial benchmarks show the effectiveness and efficiency of our L.2.. It has also demonstrated the necessity of adaptively selecting presolving instead of the default aggosti- presolving to boost the performance of the MIP solver.
4) We have open-sourced our code as benchmark of utilizing machine learning to improve the presolving in MIP solvers, please refer to our Github repository for more details.
2 FORMULATION AND METHODOLOGY
In this section, first, we introduce presolving and its role in solving MIP. Then, we adopt a simulated annealing based heuristic searching method that can find the most suitable presolving but with large time consumption. Finally, we propose a deep learning approach to learn the presolving found by the simulated annealing with the advantage of efficiency, named learning presolve (I.2P).
2.1 PRELIMINARIES: MIP SOLVER AND PRESOLVING
It is well known that any mixed integer linear programming can be written in canonical form:
min(c"s x: Ax S b, e x"
where is the number of variables, m is the number of constraints, E R is the objective coefficient vector, A E [R=x" is the constraint coefficient matrix, b E Rm is the constraint right-hand-side vector, and p S is the number of integer variables. We assume the first p variables are integer variables and the last n p variables are continuous variables.
In general, the pranch-and-boud and-bound (B&B) algorithm is utilized to solve the MIP instance to global optimal, which follows a divide-and-conquue
However, the B&B algorithm requires lots of time and resources to find the optimal solution if the size of the input MIP instance is large. Therefore, in modern MIP solvers, presolving is conducted to simplify the original instance, as Fig. 1 shows. In the popular open-source MIP solver SCIP, multiple presolvers are used to reduce the size of the model by removing irrelevant information like redundant constraints, strengthening the linear programming relaxation by exploiting integrality information, and extracting useful information in presolving.
There are three key parameters for each presolver: 1) priority denotes the order in which different presolvers are exccuted; 2) max-rounds denotes the maximal number of rounds the presolver participates in; 3) timing denotes the timing mask of the presolver. In the process of presolving, at every step, one presolver selected from the presolver pool based on the priority of each presolver. When all presolvers less than their max-rounds times. As we can see, the priorities of the presolvers tend to have greater impacts on the performance of presolving, which also illustrated in (Eible, 2010).
selected, refill the presolver pool with the presolvers that are used for
In existing solvers, the parameters of presolvers are all set by default, no matter how the input instance varies. Though the default presolving parameters are designed by experts. we consider using unchanged presolving for changeable inputs is not good idea. In our opinion, the ideal MIP solver should analyze the feature of the input instance and tailor suitable presolving parameters. In this way, the power of presolving is fully utilized, and so is the power of the whole solver. Therefore, we aim to design general approach finding the best presolving parameters given each input instance, in other words, changed from instance-agnose presolving to instance-specifi presolving.
2.2 SIMULATED ANNEALING FOR SEARCHING BEST PRESOLVING PARAMETERS
We start with a search-based baseline for tuning the presolving parameters. SCIP includes 14 presolvers and 3 parameters (priority, max-rounds, timing) for each, and one needs traverse total 42 (14 x 3) parameters which can be challenging. For this purpose, we have tried several popular heuristic tools including Bayesian optimization (BO), simulated annealing (SA), and evolution strategy, we resort to SA (Van Laarhoven & Aarts, 1987) for its suitability for discrete variables which take up 2/3 parameters in our case. While BO with Gaussian processes is designed more suited to continuous variables. Our ablation in Sec. 3.4 shows that SA-based presolving tuning outperforms BO-based one. We place the detail of SA and how we adapted in our L.P in Appendix (A.3).
3

---

Published as a conference paper at ICLR 2024
Incoming
MIP Dataset
Update
MIP Instance
Feature
Fixed
Feature
Sample
Extractor
Extractor
Update
Embedding
Embedding
MIP Instance
Inference
Kixpd
Inference
Network
Network
Loss
Presolving
Presolving
Presolving Parameters
Parameters
Parameters
MiP
MîP
Data Pair
Solver
Solver
Simulated
Resulls
Results
Annealing
Training Process
Inference Process
Check Performance
(Solving Time, PD Integral)
Figure 2: Our proposed framework L2P for learning to presolve. (Left): in the training process, we use simulated annealing to search for the most suitable presolving parameters for each MIP instance, which will be the label to update in the inference process, we use the well-trained neural networks from the training process to tailor presolving in an instance-specifie manner. Multiple criteria including the solving time and the PD) Integral are used to evaluate the performance of the presolving parameters.
neural networks during the network training. (Right):
2.3
L2P: LEARNING PRESOLVE
The drawback of SA is its considerable time cost which can be even higher than the time for B&B to actually solve the problem. Therefore, we propose to utilize neural networks along with SA, and the paradigm termed learning to presolve (I.2P). We train the neural networks via the data generated by SA in the training set and use the well-trained neural networks for inference when testing. The inference time of neural networks is insignificant and can be readily used in real-world applications.
2.3.1 FRAMEWORK DESIGN
As shown in Fig. 2, proposed L2P includes the training process and inference process. Specifically, for each MIP dataset, we first feed the MIP instances from the training set to the simulated annealing algorithm, which outputs the best presolving parameters for each instance. Then, we regard the data pair (MIP instance best presolving parameters) as the (input / label) of our neural networks. The input instances first pass feature extractor and acquire the graph-embedding representation. Then, our inference network takes the embedding and predicts the presolving parameters. Now, for each input MIP instance, set the predicted presolving the corresponding position in the MIP solver, and let the modified solver solve the MIP instance. Finally, we analyze the results of the running via multiple criteria including the solving time and primal-dual gap integral. For network updating, we calculate the loss between the best presolving parameters from the simulated annealing (the label) and the predicted presolving parameters from the inference network (the prediction). The loss passed backward through both the inference network and the feature extractor.
For the inference process, we utilize the well-trained feature extractor and inference network after training. For every incoming MIP instance unseen before, we feed it to the neural networks and acquire the predicted presolving parameters. In the same way, we modify the solver and then solve the instance. Since save time for simulated annealing, the inference process costs very little time (less than 0.5s) and the whole framework is able to be embedded into real-world MIP solvers.
2.3.2 FEATURE EXTRACTOR DESIGN
For the design the feature extractor, we first represent given MIP instance as bipartite graph (G, E, V) based on the method in (Gasse et al., 2019). In the bipartite graph, C E mm corre- sponds to the features of the constraints; V x denotes the features of the variables; and an edge Gij E between constraint node i and variable node j if the corresponding coefficient A. * 0.
4

---

Published as a conference paper at ICLR 2024
Priority
Optimizer
Label
Lons
Extractor
Embedding
Prodiction
Priurily
Averaging
Embodding
Prior Knowledge
Max-rvunds
Inference
Network
Fratures
Shared
Natwork
Max-rvunds
Prediction
Presehring
Timing Label
Parameters
Layers
Outpat
MIP
Neural
Tining
Network
Prediction
Rosals
Network
Figure 3: Inspecting the inference network of L2P, follows the data to pass through inside modules. Inspired by knowledge-basee residual learning, regard the priority information as the prior knowledge for learning max-rounds and timing via hybrid neural networks. After calculating three losses, dynamic loss averaging method is adapted aggregate them.
We the same features the existing work (Prouvost et al., 2020). Next, the bipartite graph sent as input into a two-interleaved graph convolutional neural network (GCNN) (Gasse et al., 2019). In detail, the graph convolution is broken into two successive passes, one from the variable side the constraint side, and one from the constraint side to the variable side:
(b,)EE
(NEE
(R) (R) go v (ee)))
cf ((-1)) fo
(K) C
Σ
((+11) + fv
(K)
(R) (R) Σ gv(c,)) vy ees))
(2)
where fc, gc. fy and gv are 2-layer perceptrons. We adopt the ReLU as the activation function. While & represents the number of times that we perform the convolution.
2.3.3 INFERENCE NETWORK DESIGN
As for the inference network, we design the shared-bottom neural networks to predict the priority, max-rounds, and timing simultaneously, in other words, make three predictions. As Fig. shows, we first use hidden layer to process the graph-embedding representation and regard the results as shared features, which are used for all three predictions. As mentioned Sec. 2.1, we find that priority is the most important among all presolving parameters. Since priority determines the order of all presolvers, it can also balance the influence of all presolvers. In this sense, we believe that priority is more significant than max-rounds and timing. Therefore, we consider designing special hybrid neural networks after the shared features to utilize this property.
As Fig. 3 illustrates, there are three output branches after the shared features, corresponding to priority, max-rounds, and timing respectively. For the priority branch, we use the normal fully connected layers make predictions. Then, inspired by the knowledge-hand based residual learning (KRL (Zheng et al., b021b; Liu et al., 2021)), we consider using the priority as the prior knowledge to better predict the max-rounds and timing. The key idea of KRL is treat the prior knowledge as a weak learner and use another neural network model to boost it, which turns out to be hybrid model. In our inference network, the priority is considered as the prior knowledge in the other two branches, and we use two more fully connected layers as the neural network to boost the performance. Due to the page limit, we place the detailed derivation process and proofs of KRL in Appendix (A.4). As proved by KRL, these hybrid knowledge-based residual networks help to reduce the difficulty of learning the parameters and increase the robustness and accuracy of the inference network.
Although the total loss can decrease significantly during the learning process, we observe that the training of the three output branches always converges at different speeds. In fact, is the hardest task for our inference network to predict adequate priorities for presolvers. The loss of the priority branch can hardly fall as quickly as that of two other branches. Consequently, we have to spend additional time training the max-rounds and timing branches despite the learning of them having already converged, which could easily lead to over- fitting. To avoid this, we exploit a dynamic loss averaging method (Liu et al., 2019) respectively assign each output branch variable weight
5

---

Published as a conference paper at ICLR 2024
Table 1: Performance easy, medium, and hard datasets. and denotes the average number of constraints and variables. We calculate the solving time/PD Integral and report the improve- ment/efiectivenees compared to the default setting. For each instance, SA runs for hours/days but our L,P only needs milliseconds. (see more about time difference in Sec. 3.1.4) We run the experiments five times with random seeds and report the average results. (refer Sec. 3.2)
Easy: Set Covering
Easy: Max Independent Set
Easy: MIRP small
500, m 1953)
709, 841)
Time
Imprv.
Effect.
Time (5)
Imprv. f
Effect. f
Time (6)
Impry.
Effect.
Default
7.22
8.66
56.54
7.21
0.00%
0%
8.66
0.00%
46.67
17.46%
58%
Random
7.27
0.00%
0%
8.69
0.00%
54.42
3.75%
21%
SMAC3
7.24
0.00%
0%
8.70
0.00%
0%
50.52
10.64%
42%
FBAS
7.31
0.00%
0%
8.73
0.00%
0%
54.64
3.44%
21%
L2P
7.22
0.00%
0%
8.68
0.00%
50.25
11.12%
46%
Medium:
Medium: MIK
large
(n m 466, m 486)
(n
413, m 346)
(n 4120,
6857)
Time (8) 4
Impev.
Effect. f
Time (6)
Imprv. f
Effect. f
PD Integral +
Impry. 1
Effect.
Default
31.02
237.50
2958.85
SA
15.93
48.63%
65%
228.38
3.84%
1473.75
49.81%
60%
Random
29.34
5,43%
22%
239.85
0.00%
0%
2834.26
4.21%
19%
SMAC3
24.09
22.34%
42%
233.65
1.62%
2574.77
12.98%
40%
FBAS
16.69%
39%
238.75
0.00%
2746.09
7.19%
L2P
20.24
34.74%
55%
230.33
3.02%
7%
2118.23
28.41 %
35%
Hard: Item Placement
Hard: Load Balancing
Hard: Anonymous
1083,
195)
(n 61000. 64304)
(a= 37881,
49603)
PD Integral
Imprv.
Effect.
PD Integral
Impry.
Effect.
PD Integral
Impry.
Effect.
Default
221630.77
5857,95
68319.60
SA
210593.56
4.98%
56%
5550.99
5.24%
36%
44940.63
34,22%
55%
Random
221685.75
0.00%
0%
1879.17
0.00%
53132.15
22.23%
55%
SMAC3
217220.32
1.99%
30%
5733.76
2.12%
38%
42460.63
37.85%
55%
FBAS
222096, 19
0.00%
0%
5862.64
0.00%
0%
55181.74 1.78
19.23%
55%
1,2
210633788
4.96%
42%
5558.61
5.11%
48%
33278.48
51.29%
55%
when aggregating the three losses. We place the detailed mathematics formulation of dynamic loss averaging in Appendix (A.5). Intuitively, the branch with slower converge speed would be assigned larger weight and vice versa. In this way, we can accelerate the learning of priority prediction and thus provide more reliable prior knowledge for the inference max-rounds and timing.
EXPERIMENTS
Please note that except for the following subsections, we have placed the additional experiments and discussions in the appendix, including the multiple-run results with standard deviation (A.7), ablation studies by adjusting the size of training data (A.9), experiments on the popular MIPL.IB dataset (A.8), illustration of the searching process (A.10), illustration of the improved presolving parameters (A.11), and the discussion of limitations and future work (A.12).
3.1 PROTOCOLS
3.1.1 DATASETS
We follow (Gasse et al., 2019; 2022) and use popular datasets in our experiments. We evaluate our approach on the four levels of difficulty: casy, medium, hard, and industrial-level datasets:
1) Easy datasets comprise three popular synthetic MIP benchmarks: Set Covering (Balas Ho, 1980), Maximum Independent Set (Bergman al., 2016) and Maritime Inventory Routing Problem (MIRP) (Papageorgiou et al., 2014). We artificially generate instances in line with (Gasse et al., 2019; Sun al., 2021; Jiang & Grossmann, 2015).
2) Medium datasets include CORLAT (Gomes et al., 2008) and MIK (Atamtürk, 2003), which are widely used benchmarks (He et al., 2014; Nair al., 2020).

---

Published as a conference paper at ICLR 2024
3) Hard datasets from NeurIPS 2021 Competition (Gasse et al., 2022) include Item Placement, which involves spreading items that need to be placed; Load Balancing, inspired by real-life applications of large-scale systems; Anonymous, inspired by large-scale industrial application; and Maritime Inventory Routing problem (MIRP) with hard problem setrings.
4) Private Industrial Benchmarks. We collect real- weal-world data concerning planning and scheduling in production planning engine of an influential corporation and formulate them as MIP instances. The production planning problem is to plan daily production for hundreds of factories according to cus- tomers' daily and predicted demand. The problem is subject to material transportation and production capacity constraints, which aim to minimize the production cost and lead time simultaneously.
For the datasets used in our experiments, we follow the common usage in existing works (Gasse et al., 2019; Han et al., 2023; Wang et al., 2023; Li et al., 2023a) including splitting data into training and testing sets with 80% and 20% instances. For the easy datasets, we generate 1000 instances for each. For the medium and hard datasets, we directly split the instances provided by their original benchmarks. Here we list these datasets and their total number of instances: Corlat(2000) Gomes et al. (2008), MIK(100) Atamtürk (2003), Item Placement(10000) Gasse et al. (2022), Load Salancing(10000 Gasse et al. (2022), Anonymous(1 18) Gasse et al. (2022). The two industrial datasets contain 1,000 instances for each, as collected from two periods respectively (from 15 May 2022 to 15 Sept. 2022 and from 8 Oct. 2022 to 8 Dec. 2022).
3.1.2 EVALUATION METRICS
Throughout all experiments, we use SCIP 7.0.3 (Gamrath et al., 2020) as the back-end solver, which is the state-of-the-ar open-source MIP solver. Note it is nontrivial to test our approach on the commercial solvers e.g. Gurobi, for the limited access to their interfaces. Besides, we use Ecole 0.7.3 (Prouvost et al., 2020) and PySCIPOpt 3.5.0 (Maher et al., 2016) for better implementation. Except for the presolving module, we keep all the other SCIP settings/parameters by default. We use two popular evaluation metrics, i.e., the average solving time (Time, lower is better), and the average primal-dual gap integral (PD integral, lower is better). To better show the performance of improving presolving, we calculate the improvement (Imprv., the higher the better) made by the compared methods compared to SCIP's default settings. Morcover, we calculate the effectiveness (Effect., the higher the better), aka. the "better/win rate". Here "better" means the solving time/PD integral of improved presolving is better than the solving time/PD integral of SCIP's default presolving. The higher effectiveness means more instances the method can find better presolving. The testing based on the MIP solver itself, and we directly acquire the solving time/PD integral from the solver. The solving time/PD integral contains both the presolving process and the B&B process, which is directly required by SCIP, Ecole, and PySCIPOpt. For details and the mathematics formulation of PD integral, refer the documentation or our detailed description in Appendix (A.6).
3.1.3 IMPLEMENTATION DETAILS
For SA, we set the initial temperature as le5 with the decay rate 0.9 until it reaches the minimum temperature of le-2. For the neural networks, rate of 1e-4, and a hidden size of 64. For the feature extractor, we follow the same settings as (Gasse et al., 2019) for building graph embeddings. For the hybrid inference networks, size as 64. The loss functions used in our methods are ListMLE (Xia et al., 2008) for the priority and Cross-Entrropy (Good, 1952) for the max-round and timing. ListMLE is loss function designed for ranking, which is suitable for learning the priority since the priority denotes the order/rank of the presolvers. The number of epochs for training is 10,000. The experiments are conducted in Linux workstation with NVIDIA 3090 GPU and AMD Ryzen Threadripper 3970X 32-Core CPU. Particularly, for the hard datasets in which the instance scale is large, we gradually reduce the batch size to 4 until they can be put into the GPU wholly. Our work can be readily reproduced via these settings and our code in the Github repository.
ADAM with batch size of 32, and learning
set the hidden
3.1.4 COMPARED METHODS
1) Default: following the same presolving parameters by the default setting of SCIP to solve all MIP instances. 2) Random: we randomly select the parameters for all presolvers for 10 times and record the best ones. 3) SMAC3 ((Lindauer et al., 2022)): the latest automatic configuration framework
"https://wwwr hwtp://wwwcclllccooooo /2/20 /ml 4ca- compeo t on #metrics
7

---

Published as a conference paper at ICLR 2024
Table 2: Performance two industrial datasets. mn and denote the average number of constraints and variables respectively. We record the accumulation of the solving time over all instances in the dataset and report the improvement compared the default setting.
Industrial Datasct #1 (n 1494, 5583)
Industrial Datasct #2 (n 8456, 2392)
Solving Time (6)
Improvement
Solving Time (6)
Improvement 1
Default
21280.31
Default
2994.69
SA
20224.38
4.96%
SA
2347.07
21.62%
Random
21387.25
0.00%
Random
2887.32
3.57%
L2P (ours)
20420.28
4.06%
L2P (ours)
2447.56
18.27%
aims at finding one single configuration for each MIP category. 4) FBAS ((Georges et al., 2018)): one algorithm selection method designed for MIP, which combines several standard ML techniques to select perl-performing algorithm based on a feature description of the input MIP instance. 5) SA (simulated annealing): the sub-module in our I.2P that uses the simulated annealing to search for the best presolving parameters, of which the time consumption is huge. 6) L,P (Ours): our proposed L2P is orthogonal to other progress made in learning for MIP in previous literature.
For every method in our experiments, they use their own algorithm to improve the presolving (running time), and then SCIP uses the improved presolving to solve the MIP instance (solving time), where the solving time/PD integral is used for evaluation. In other words, there are two steps in our experiments: 1) Running step: use RA/Random/SMAC//FBBA.
to find better presolving, and deploy the new presolving in the MIP solver; 2) Solving step (including presolving and B): we use the adjusted MIP solver to solve the MIP instance without further intervention. The metries (solving time/PD integral) in the tables are directly acquired by the API from SCIP in the solving step.
In the running step, for each instance, our L2P needs less than 0.05s in the medium datasets, and less than 0.5s in the hard datasets, while the SA needs hours in the medium datasets and days in the hard datasets. When we claim that the time consumption of SA unacceptable, we mean its running time. Therefore, we can regard SA as an offline method (rumning for hours/days) while Mundoo//SMMAC//FBAA//22 are online methods (running for seconds). The running time of L2P is negligible compared to the improvement it brings. Therefore, we should focus on the comparison among online methods, in other words, between our L.P and Random/SMAAC/FFBA.
3.2 EXPERIMENTS ON PUBLIC MIP DATASETS
To verify the performance of our L2P, conduct experiments on various common MIP datasets in Table 1. We run the experiments with 5 random seeds and report the average improvement and effectiveness compared to the default setting. Due the page limit, we place the detailed standard deviation results in Appendix (A.7). For the easy datasets, the improvement is not significant. We consider because the MIP solver has made sufficient optimization to these classic problems. Besides, the easy datasets are constructed by experts in operational research, in which thus there is not much redundancy. Therefore, even SA cannot find more suitable presolving parameters. However, is impossible for the solver to pre-optimize all kinds of MIP instances, especially for real-world MIP instances. The MIP instances obtained from the real world are constructed by practitioners with different expertise in operational research. Usually, there is much more redundancy in MIP instances from the real world than those from the academy. In the medium datasets, we can see that our proposed methods can make significant improvement in the Corlat dataset, which can more than 1/3 of the solving time. When it comes to hard datasets, we change the evaluation metric from solving time to the PD) integral, and our I.2P still reaches good performances. Compared to SA which needs hours or days to finish searching for each instance, our proposed L2P can make inferences in merely seconds. It turns out that the special design of our proposed L2P for presolving does show its value since L2P can outperform the latest SMAC3 in most cases. Considering that SCIP has been well developed and updated for 20 years, we think our current improvements to SCIP are meaningful for both methodology development and practical use.
3.3 EXPERIMENTS ON PRIVATE INDUSTRIAL DATASETS
We conduct experiments on two industrial benchmarks provided by our industrial partner in Table 2. As shown in the caption, the scale of this dataset is large and of relatively high variance. There is still
8

---

Published as a conference paper at ICLR 2024
Table 3: Generalization test on MIRP small and large datasets. We train 1.2P the small/large dataset and test it on the large/small dataset respectively.
Easy:MIRP small 709, m 841)
Hard:MIRP large (n 4120, 6857)
Solving Time (8).)
Improvement
PD Integral
Improvement
Default
56.54
Default
2958.83
Random
54.42
3.75%
Random
2834.26
4.21%
1.2 (small small)
50.25
11.12%
L.2P (large large)
2118.23
28.41 %
1.2P (large- + small)
52.66
6.86%
1.2 (small - large)
2680.31
9.41%
Table 4: Generalization test of our L2P w.r.t improvement. We train our L2P on Corlat, MIK, and the combined dataset of Corlat and MIK. Then, we evaluate the performance of I.2P on the original Corlat and MIK dataset.
L2P
14
Figure 4: Performance drop by removing components from vanilla L2P on Corlat dataset. We remove the components one by one from the full version of L2P.
Full L.P M.A. BLA
W.C KAL
M.. Branch w.A Shared M.O. GCRN SA
test
train
Corlat
MIK
Corlat
34.74%
15.52%
33 53.84%
MIK
1.12%
3.02%
1.87%
a large improvement room for the default setting. SA can find more suitable presolving parameters, which reduces the solving time by 4.96% and 21.62% on the two datasets, respectively. Our method still shows notable improvement compared to the default setting and the performance gain (4.06% and 18.27%) is close to SA's, while SA needs hours run but our L2P only needs seconds. Due to potential privacy issue, we did not test SMAC3 and FBAS on these datasets.
3.4 GENERALIZATION TEST AND ABLATION STUDY
To test the generalization of I.2,, first, we conduct experiments on MIRP small and large datasets. The two datasets are significantly different complexity denoted by scale. We train L2P with MIRP small dataset and observe its performance on MIRP large datasets, and vice versa. The statistics of the datasets and experiment results are reported in Table We can see that on both tests our L2P outperforms the baselines when generalized from another dataset, which denotes its generalization effectiveness. Besides, we add more experiments in Table 4, where the experimental settings are the same as the settings in Table 1, including the data size and the metric. Instead of training domain by domain normally, we try multiple train/test settings on different domains. the first two columns, we that L2P can handle unseen domains (families) of instances. In the last column, train L2P with the mixed dataset and L2P still reaches good performance when testing on both two domains.
Fig. 4 shows the effect of removing components in L2P one by one: from the dynamic loss averaging (DLA), to the hybrid knowledge-band based residual learning (KRL), to the output branches, to the shared feature, to GCNN, and at last, replace SA with Bayesian optimization. We can see that removing the KRL module leads to a nearly 10% performance drop. Therefore, the hybrid KRL structure in L.P is more significant. When change SA to BO, we note that BO can hardly find better presolving parameters, as the improvement downgrades from 10% to almost 0%%
4 CONCLUSION AND OUTLOOK
We propose a paradigm learning to presolve for MIP solvers. Instead of using the default instance- agnostic presolving as in existing solvers, we use simulated annealing to search for suitable presolving an mnstance-specifi manner. Furthermore, we design the hybrid neural networks learn the results generated from SA. Experiments on both public and private MIP datasets show its performance and cost-efficiency. We hope our results and open-source can draw wide attention and further evaluation could be performed on commercial solvers which we believe is a less-studied yet promising area. One possible future work is to combine the learning- baaning-based solvers e.g. (Zhang et al., 2024) tailored to MIP and more general methods (Li et al., 2023c) with our presolve techniques. Also, other instance generation models (Li et al., 2023b; Chen et al., 2024) for training set augmentation. For more discussion of potential limitations and future plans, please refer to Appendix (A.12).
may combine
9

---

Published as a conference paper at ICLR 2024
REFERENCES
T. Achterberg and R. Wunderling. Mixed integer programming: Analyzing 12 years of progress. In Facets of Combinatorial Optimization, pp. 449-481. Springer, 2013a.
Tobias Achterberg and Roland Wunderling, Mixed integer programming: Analyzing 12 years of progress. In Facets of combinatorial optimization, pp. 449-481. Springer, 2013b.
Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, and Dieter Weninger. Presolve reductions mixed integer programming. INFORMS Journal on Computing, 32(2):433-566 November 2019.
Alper Atamtürk. On the facets of the -ixed-integer knapsack polyhedron. Mathematical Program- ming, 185551 2003.
Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning to search. In ICML, pp. 588-598, 2021.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: computational study. In Combinatorial Optimization, pp. 37-60. Springer, 1980.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. Eur. J. Oper. Res., 290:405-421, 2021.
David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization, volume 1. Springer, 2016.
Timo Berthold, Matteo Francobaldi, and Gregor Hendel. Learning to use local cuts. arXiv preprint arXiv:2206.110 11618, 2022.
Robert Bixby and Edward Rothberg. Progress computational mixed integer programming look back from the other side of the tipping point. Annals of Operations Research, 149:309-325.
December 2007.
Robert E Bixby, Mary Fenelon, Zonghao Gu, Ed Rothberg, and Roland Wunderling. lixeedinteege programming: A progress report. In The shurpest cut: the impact of Manfred Padberg and his work, pp. 309-325. SIAM, 2004.
A. L. Brearley, G. Mitra, and H. P. Williams. Analysis of mathematical programming problems prior to applying the simplex algorithm. Mathematical Programming. 8:54-83, 83, December 1975.
Xinyan Chen, Yang Li, Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for sat instance generation. In International Conference on Learning Representations, 2024.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In NeurlPS, volume 32, 2019.
Zhao Chen, Vijay Badrinarayanan, Chen-Yu Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient nor- malization for adaptive loss balancing in deep multitask networks. arXiv preprint arXiv:1711.0221 2017.
Joseph M Elble. Computational experience with linear optimization and related problems. University of Illinois at Urbana- Shaana--hampaign, 2010.
Mare Etheve, Zacharie Alès, Côme Bissuel, Oliver Juan, and Safia Sedad-Sidhoum Reinforcement learning for variable selection branch and bound algorithm. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2020, pp. 176-185, Cham, Switzerland, September 2020. Springer.
Hutter Frank, Hoos Holger, H., and Leyton- Brown Kevin. Automated configuration of mixed integer programming solvers. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp. 186-202. Springer, June 2010.
Ivet Galabova. Presolve, crash and software engineering for highs. 2023.
10

---

Published as a conference paper at ICLR 2024
G Gamrath, D Anderson, K. Bestuzheva, WK Chen, L Eifler, M Gasse, P Gemander, A Gleixner, Gottwald, K Halbig, et al. The scip optimization suite 7.0: Technical report, 2020.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. Advances Neural Information Processing Systems, 32, 2019.
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antomia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 202/ Competitions and Demonstrations Track, pp. 220-231. PMLR, 2022.
Alexander Georges, Ambros Gleixner, Gorana Gojic, Robert Lion Gottwald, David Haley. Gre- gor Hendel, and Bartlomiej Matejezyk. Feature-buus algorithm selection for mixed integer programming. 2018.
Carla P Gomes, Willem-Jan van Hoeve, and Ashish Sabharwal. Connections in networks: A hybrid approach. International Conference on Integration of Artificial Intelligence (Al) and Operations Research (OR) Techniques in Constraint Programming, pp. 303-307. Springer, 2008.
Irving John Good. Rational decisions. Journal of the Royal Statistical Society: Series B (Method- ological), 14(1):177-114, 1952.
Prateek Gupta, Elias B. Khalil, Didier Chetélat, Maxime Gasse, Yoshua Bengio, Adrea Lodi, and M. Pawan Kumar. Lookback for learning to branch. arXiv preprint orXiv:2206.1498)) 2022.
Gurobi. Gurobi solver. https: //wwp www.bi. com/. 2021.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. arXiv preprint 230.0033000066666, 2023.
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
Zeren Huang, Kerong Wang. Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed integer programming. Pattern March 2022.
Recognition, 123(108353):1-
Frank Hutter, Holger H Hoos, Kevin Leyton- Leyton-Brown, and Thomas Stützle. Paramils: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36:267-306, 2009.
Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In International conference on learning and intelligent optimization, pp. 507-523. Springer, 2011.
IBM. Cplex solver. https://wwwt ibm. com/ hhn aeli-ennannailn ht//aaallttssspppeee opt optimizieiz.. 2021.
Yongheng Jiang and Ignacio E Grossmann. Alternative mixed-integer linear programming models of
a maritime inventory routing problem. Computers & Chemical Engineering, 77:147-161, 2015.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. arXiv preprint arXiv:1705.0711 2017.
Pascal Kerschke, Holger H Hoos, Frank Neumann, and Heike Trautmann. Automated algorithm selection: Survey and perspectives. Evolutionary computation, 27,1):345,,2 2019.
Elias Boutros Khalil, H. Dai, Yuyu Zhang. B. Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. NeurIPS, 2017.
Lars Kotthoff. Algorithm selection for combinatorial search problems: A survey. Data mining and constraint programming: Foundations of cross-disciplinary approach, pp. 149-190, 2016.
11

---

Published as a conference paper at ICLR 2024
Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve in large-scale linear programming via reinforcement learning, 2023.
Sirui Li, Wenbin Ouyang, Max B Paulus, and Cathy Wu. Learning to configure separators in branch-and-cut. arXiv preprint 1rX552231..06650, 2023a.
Xijun Li, Fangzhou Zhu, Hui-Ling Zhen, Weilin Luo, Meng Lu, Yimin Huang, Zhenan Fan, Zirui Zhou, Yufei Kuang, Zhihai Wang, et al. Machine learning insides optverse ai solver: Design principles and applications. arXiv preprint arXiv:2401. 1.05600, 2024.
Yang Li, Yichuan Mo, Liangliang Shi, and Junchi Yan. Improving generative adversarial networks via adversarial learning in latent space. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. Curran Associates, Inc., 2022.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula gen- eration and a strong aructure-hardness--nn on Knowledge Discovery and Data Mining (KDD), 2023b.
baseline. In ACM SIGKDD International Conference
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023e.
Yang Li, Liangliang Shi, and Junchi Yan. lid-gan: an iid sampling perspective for regularizing mode collapse. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023d.
Jiacheng Lin, Jialin Zhu, and Huanggang Wang Tao Zhang. Learning to branch with tree-aware branching transformers. Knowledge-Baud Based Systems, 252(109455):1-12, November 2022.
Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. J. Mach. Learn. Res., 23(54):1-9, 2022.
Chang Liu, Guanjie Zheng, and Zhenhui Li. Learning to route via theory-guided residual network. arXiv preprint arXiv:2 185,0779,,,, 2021.
Chang Liu, Chenfei Lou, Runzhong Wang, Alan Yuhan Xi, Li Shen, and Junchi Yan. Deep neural network fusion via graph matching with applications to model ensemble and federated learning. In International Conference on Machine Learning, pp. 13857-13869. PMLR, 2022a.
Chang Liu, Shaofeng Zhang, Xiaokang Yang, and Junchi Yan. Self-supervised learning of visual graph matching. In European Conference on Computer Vision, pp. 370-388. Springer, 2022b.
Chang Liu, Zetian Jiang, Runzhong Wang. Lingxiao Huang, Pinyan Lu, and Junchi Yan. Revocable deep reinforcement learning with affinity regularization for outlier-robust graph matching. In The Eleventh International Conference on Learning Representations, 2023.
Shikun Liu, Edward Johns, and Andrew Davison. End-to-end multi-task learning with attention. In CVPR, pp. 1871-1880, June 2019.
Andrea Lodi and Andrea Tramontani. Performance variability in mixed-integer programming. In Theory driven by influential applications, pp. 1-12. INFORMS, 2013.
Han Lu. Zenan Li, Runzhong Wang, Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang, and Junchi Yan. Roco: A general framework for evaluating robustness of combinatorial opti- mization solvers graphs. In The Eleventh International Conference Learning Representations, 2023.
Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. In Mathematical Software ICMS 2016, pp. 301-307. Springer International Publishing, 2016. doi: 10.10077978-33319-4442--3
12

---

Published as a conference paper at ICLR 2024
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXhv:2012.133499 2020.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In NewrIPS, pp. 9839-9989, 2018.
Dimitri Papageorgiou, George L Nemhauser, Joel Sokol, Myun-Seok Cheon, and Ahmet B Keha. Mirplib-a library of maritime inventory routing problem instances: Survey, core model, and benchmark results. European Journal of Operational Research, 235(2):350-366 2014.
Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to by looking ahead: Cutting plane selection via imitation learning. In ICML, pp. 17584-17600. PMLR, July 2022.
Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimiza- tion solvers. In Learning Meets Combinatorial Algorithms at NeurlPS2020, 2020. URL
https: /ttp:///ppeeeeeeeeeeeeeee net.
Eorum?id=IVeehqee wttp:eeeweee/ooorneeieieeeeeee
Qingyu Qu, Xijun Li, Yumfan Zhou, Jia Zeng, Mingxuan Yuan, Jie Wang. Jinhu Lü, Kexin Liu, and Kun Mao. An improved reinforcement learning algorithm for learning to branch. arXiv preprint arXiv:2201.0621.3 2022.
Ohad Shamir. Are resnets provably better than linear predictors? In Advances in neural information processing systems, pp. 507-516, 2018.
Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement learning, 2021. URL https: : / oppp/evieeeeeeeeeeee/eeeee .nt ftr/mmrrmmmmmmm wouuumiidee d-MMM KwRsbhi5e.
Peter JM Van Laarhoven and Emile HL Aarts. Simulated annealing. In Simulated annealing: Theory and applications, pp. 7-15. Springer, 1987.
Runzhong Wang. Ziao Guo, Wenzheng Pan, Jiale Ma, Yikai Zhang, Nan Yang, Qi Liu, Longxuan Wei, Hanxue Zhang, Chang Liu, Zetian Jiang, Xiaokang Yang, and Junchi Yan. Pygmtools: A python graph matching toolkit. Journal of Machine Learning Research, 2024.
Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. arXiv preprini arXiv:
2023.
Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In International Conference on Machine Learning, 2008. URL https:/ / /api.. semant ieschollle ar. www.org////oooooo.ooooooooo Corpps 2071 68334.
Kaan Yilmaz and Neil Yorke-Smith. study of learning search approximation in mixed integer branch and bound: Node selection in scip. arXiv preprint 2007v:2000.033948, 2020.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and- search trees learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3931-3939, Menlo Park, CA, May 2021. AAAI.
Changwen Zhang, Wenli Ouyang, Hao Yuan, Liming Gong, Yong Sun, Ziao Guo, Zhichen Dong, and Junchi Yan. Towards imitation learning to branch for mip: A hybrid reinforcement learning based sample augmentation approach. In International Conference on Learning Representations, 2024.
Jiay Zhang, Chang Liu, Xijun Li, Hui- Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. A survey for solving mixed integer programming via machine learning. Neurocompating, 519; 205-217, 2023.
Guanjie Zheng, Chang Liu, Hua Wei, Chacha Chen, and Zhenhui Li. Rebuilding city traffic origin destination from road speed data. In 202/ IEEE 37th International Conference on Data Engineering (ICDE), pp. 301-312. IEBE, 2021a.
Guanjie Zheng, Chang Liu, Hua Wei. Porter Jenkins, Chacha Chen, Tao Wen, and Zhenhui Li. Knowledge-based residual learning. In IJCAI, pp. 1653-1659, 2021b.
13

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 1 PRESOLVERS IN MIP SOLVERS
Seeing its important role, different presolvers have been devised to modify the MIP instance before actually solving it. In the most popular open-source solver SCIP Gamrath et al. (2020), 14 presolvers are used in presolving. In Table 5, we list these presolvers with brief descriptions. For more information, please refer to the official document of SCIP
Table 5: Brief descriptions of fourteen commonly used presolvers in SCIP, For CPLEX the cases similar, while for Gurobi we can not acquire their interfaces since Gurobi is a commercial solver and not open-source.
Presolver
Description
Boundshift
converts domain [a,b] to domain [0,b-a]
Convertinttobin
converts integer variables with domain [a, a+ I] to binaries
Domcol
finds dominance relations hetween variables and derives lower bound
Dualagg
aggregates the variables with specific structure
Dualcomp
fixes the bound if the combination of continuous variables can compensate
Dualinfer
strengthens the bounds on continuous variables
Gateextraction
extracts gate-constraints constraints and set-partitioning constraints
Implics
implication graph presolver which checks for aggregations
Inttobinary
converts integer variables with domain [a,a+1] to binaries
Milp
calls the presolve library and uses the postsolve information
Qpkktref
tries add the KKT conditions as additional constraints
Redvub
removes redundant variable upper bound constraints
Stuffing
investigates singleton continuous variables if can be fixed at bound
Trivial
fixes variables with equal bounds to this value
A.2 RELATED WORK
In this subsection, we discuss the existing works closely related to ours: 1) solving MIP instances, which is the problem we focus on; 2) presolving and presolvers, which is the insight of this work; 3) Automatic configuration and algorithm selection as our work roughly falls into this category; 4) machine learning for combinatorial optimization, which is a general approach of combining machine learning into traditional solvers.
Machine learning methods have shown the potential to accelerate the solving of MIP instances. Specifically, many works learn to select branching variables (Etheve et al., 2020; Qu al., 2022; Gupta et al., 2022) or parameterizing B&B search tree directly (Zarpellon et al., 2021; Lin et al., 2022). Moreover, node selection is also appealing scenario where imitating learning can be leveraged to speed up the solving process (He et al., 2014; Yilmaz& & Yorke-Smith, 2020). Due to the significance of cutting planes to B&B, ML techniques have also been applied to train cut selection policy to improve the tightening of feasible region (Huang et al., 2022; Paulus et al., 2022; Berthold al., 2022). One recent work (Kuang et al., 2023) aims at using RL improve the solving of linear programming. However, rare works investigate how another important module in MIP solvers, i.e., the presolving module, can benefit from learning- based technologies. We recommend these surveys for more details (Li et al., 2024; Zhang et al., 2023).
Solving MIP Instances.
Presolving in MIP Solvers. Presolving plays a key role in MIP, which can improve the model constraints' description of the underlying polyhedron of integer-feasible solutions (Achterberg et al.,
/grcup
PRESO www................
14

---

Published as a conference paper at ICLR 2024
2019). Several studies (Bixby & Rothberg, 2007; Achterberg & Wunderling, 2013a) have empirically explored how various components in the MIP solvers affect the solution quality and one consensus is that presolving is one of the most powerful components. Essentially, presolving can be considered set of methods to drop redundant information of model formulation (Brearley et al., 1975), such as removing redundant constraints, fixing variables, and seeking generalized upper bounds. (Achterberg et al., 2019) introduced the presolving techniques as used in Gurobi. Despite the significance of presolving, there surprisingly relatively limited literature for comprehensive study, especially from the machine learning perspective for introducing adaptiveness for presolving.
Automatic Configuration and Algorithm Selection. Automatic configuration tries to find a single robust configuration across a set of problem instances. ParamILS (Hutter et al., 2009) provides a complete framework for parameter tuning and algorithm configuration (Hutter et al., 2011) further uses Bayesian optimization to find better configurations. The open-source SMAC3 (Lindauer et al., 2022) is a robust and flexible framework for BO in determining well-perfo hyperparameter configurations, Algorithm selection (Kotthoff, 2016; Kerschke et al., 2019) aims at choosing among a set of algorithms the ones that are likely to perform best for a particular instance. (Georges et al., 2018) combine several standard ML techniques to select werl-performing algorithm based feature description of input MIP instances. Instead of finding a single configuration for all instances, we tend to design an instance-specific presolving tailor method. Besides, our L.2P focuses on the presolving module with consideration of presolver order, which is hardly studied in the literature.
Learning for Combinatorial Optimization. There are growing interests in using learning in solving combinatorial optimization problems (Bengio et al., 2021), researchers have considered adopting deep learning in several NP-hard problems, such as traveling salesman problem (Li et al., 2023c; Khalil et al., 2017), vehicle routing problem (Nazari et al., 2018; Zheng et al., 2021a), la), job scheduling problem (Chen & Tian, 2019), maximal common subgraph (Bai et al., 2021). graph matching (Liu et al., 2023; 2022b; Wang et al., 2024), model fusion (Liu et al., 2022a). Aside from directly lever- aging learning to problem solving, methods are also developed to provide support to solving, such as utilizing generative modeling (Li et al., 2022; 2023d) to augment real-world combinatorial in- stances (Li ct al., 2023b; Chen et al., 2024) and evaluating the robustness of combinatorial solvers (Lu et al., 2023). As classic problem in combinatorial optimization, researchers have tried to utilize the power of deep learning to accelerate the solving of MIP during B&B (Gasse et al., 2019). However, no works focus the presolving part to the best of our knowledge.
A.3 DETAILS OF UTILIZING SIMULATED ANNEALING IN 1.2P
To find good solutions, SA continuously perturbs the known solution. If the new solution has better objective value, it is accepted. Otherwise, it could be accepted by a certain probability, which can be specified as: This mechanism helps SA jump out of the possible local optima. Generally, an exponential function is used to set the probability of accepting the worse solution:
P e
where T denotes the current temperature and Ay represents the difference between the objective value of the new and old solution. In the task of this paper, the objective value refers to the solving time/PD) integral of solving MIP instances. By continuously lowering the temperature, SA simulates the material coming into equilibrium, and thus effectively simulates the physical annealing. In practice, SA starts initially with T set high value, and then it is decreased at each step following a specific schedule, and SA terminates when the temperature T reaches preset threshold. In this way, the algorithm supposed to wander initially towards broad region of the search space containing good solutions and gradually drift towards better regions that become narrower and narrower, and finally move downhill according to the steepest descent heuristic.
When adopting SA to our presolving scenario, we set the first 14 variables as continuous variables and the last 28 variables as integer variables, corresponding to priority (float), max-rounds (int), and timing (int) respectively. The difference between continuous variables and integer variables is the disturbance (for the integer variables we only use +1). As for the object function, the most valuable one is the solving time. However, when facing large-scale instances, we can not use the solving time as the objective function the solving time is clearly more than 3600 seconds. Therefore, instead of solving the MIP instance the optimal, we set time limit and output the current solution.
15

---

Published as a conference paper at ICLR 2024
Based on the current solution, we design three surrogate objective functions: 1) int ratio: count the number of variables that are integers and should be integers by the MIP constraints. 2) bound gap: calculate the gap between the dual bound and primal bound as the bound gap. 3) primal-dual gap integral: the area between the curve of the solver's primal bound and dual bound. our experiments, find that all three surrogate objective functions work well. For each dataset, select the surrogate objective function with the best performance in SA.
A.4 DETAILS OF SNOWLEDGE-BASHE RESIDUAL LEARNING
Inspired by (Zheng et al., 2021b), we decide to utilize the knowledge-basee residual learning (KRL) in our neural networks, regarding the priority information the prior knowledge. Here we describe the detailed design of KRL. As Fig. 5 shows, KRL is a residual learning method to combine the prior knowledge model and the neural network model. Specifically, KRL utilizes a simple but effective residual unit with domain knowledge:
x p(x + Gx(x)
where p(x) is the prior knowledge model, Gx(x) is a neural net model. Intuitively, the prior knowledge model can help to infer reasonably well. Hence, the neural network model will be directed to predict the residual x' - p(x). As (Shamir, 2018) shows, learning the residual value x' p(x) is provable better than learning the original value when G& satisfies certain criteria and the output layer is linear. This ensemble significantly increases its robustness and accuracy. Moreover, theoretically, it is guaranteed yield superior performance over either a pure domain knowledge model or pure deep learning model. (proved in Section 4.3 of the KRL paper (Zheng et al., 2021b))
P
x
Figure 5: The knowledge- based residual learning unit. Gø: neural layers, p prior knowledge model. Credit to (Zheng et al., 2021b).
A.S DETAILS OF DYNAMIC LOSS AVERAGING.
Imbalance among multiple tasks is one of the most critical issues to be addressed in multi-task learning, many studies have attempted to balance the convergence rate of different tasks by assigning an adaptive weight to each task (Kendall et al., 2017: Chen et al., 2017; Liu et al., 2019). Inspired by them, the motivation of our Dynamic Loss Average method is to average task weighting over time via adjusting the rate of change of loss for each task. Formally, define loss weight: Wi for each task: as:
(1) = Keep RRx 1)/T)
(5)
Σ, exp eeppp 1)/T)*
Lx(t Lx(t-1)
R& -
Lx 2)
where (t) denotes the loss of task at the t iteration and (+) calculates the relative training convergence rate of task k T in the softmax operator represents the temperature that controls the softness of weighting for task-specific loss. In the implementation, temperature T is set to 2 and R1)(1) is initialized as when / 1, 2, but any other effective initialization methods with prior knowledge can also be applied here.
A.6 DETAILS OF PD INTEGRAL
For the definition of PD integral, the primal-dual integral in the field of mixed integer programming (MIP) is measure used to evaluate the performance of MIP solvers. Here we list several documenta-
16

---

Published as a conference paper at ICLR 2024
Table 6: Performance easy, medium, and hard datasets. We ran the experiments five times with random seeds and reported the average results with their standard deviations.
MIRP small
Corlat
MIK
MIRP large
Item Placerent
Load Balancing
Anonymous
Rundom
3.75%
4.21%
SMAC3
10.64%
22.3494-1..0 108%
1.62% 29%
12.98% 6.6
1.99%+0. 11%
2.00
37.85 1..8596b00.999
FBAS
3.44%=1 87%
16.699-+2.200 20%
<0
7.19%
<0
<0
19:235
L2P (ours)
11.12%41.56%
34.74%
3.02%
28.41%
4.96%
5.119200.1%%
51.29%41155%
tion of implementing PD integral for understanding it. It provides quantitative assessment of how effectively solver bridges the gap between the primal (the best feasible solution found) and dual (a bound on the optimal solution) bounds over the course of the solution process. Here we list a more detailed breakdown:
Primal and Dual Solutions in MIP: In mixed integer programming. a primal solution refers to a feasible solution that satisfies all the constraints of the MIP model. The dual solution, on the other hand, related to the bounds on the optimal solution value. In linear programming, this would be equivalent to the solution of the dual problem, but in MIP, it usually refers to bound derived from a relaxation of the integer constraints.
The primal-dual integral measures how the gap between the primal and dual solutions evolves over time. This gap the difference between the objective value of the best known feasible solution (primal) and the best known bound (dual).
Gap Measurement:
Purpose of the Primal-Dual Integral: the efficiency of solver in converging to the optimal solution. It can highlight whether a solver quickly identifies good feasible solutions and tight bounds whether it struggles to improve the primal and dual solutions over time.
This measure is especially useful in understanding
The primal-dual integral is calculated by integrating the gap the time taken for the computation. A lower integral value indicates a more effective solver, as shows that the solver able to keep the primal-dual gap smaller throughout its run.
Calculation:
Use in Analysis and Benchmarking: This metric valuable for comparing different solvers solution strategies in mixed integer programming. It provides insights beyond just the final solution quality or computation time, focusing on the overall trajectory of the solution process.
A.7 EXPERIMENTS WITH 5 RANDOM SEEDS
We conduct experiments with 5 random seeds, following the settings in (Gasse et al., 2019). For the bascline Random, its approach is already randomly selecting the parameters 10 times and recording the best ones. Therefore, we do not modify this baseline. Table 6 shows the solving time/PD integral improvement the methods on all datasets, the average results with standard deviation are reported. various datasets.
We can that our proposed methods can make significant improvements Compared to SA which needs hours or days to finish searching for each instance, our proposed L2P can make inferences in merely seconds (less than 0.05s in the medium datasets, and less than 0.5s in the hard datasets). As for the baselines, we find that SMAC3 reaches comparable performance while FBAS does not work well except for Corlat and MIK. It turns out that the special design of our proposed L2P for presolving does show its value since L2P can outperform the latest SMAC3 in most cases, including instance-specifie tailor, hybrid residual networks, dynamic loss, and hared-bottom branching. As we can see, in these popular MIP datasets, our L2P has shown its performance and cost efficiency.
http:///wwwc.c........oooo 1a0000/1mmm00-oooooooooo000 cocpetompt/iiooooooooooommm wttp://tttoo/oo/tteeeee 'https: ://ww co. com/ / fí co- xpress- optimi zer/HMMI/P CTC//PPIMAAAAA LIDUA VTRGRAI., html
17

---

Published as a conference paper at ICLR 2024
Sahrig Time(al
imprrmmntt L2F
Sdving time
inprovatment L2F
54
Susdine imprevmennt ofaadomm
14.0%
28
Base iec Inprovement of Randon
35.0%
Improvement Perceneeeeneeee percentage
Improvement Percentag
12.0%
30.0%
52
Solving Time
10.0%
Solving Time
24
25.0%
50
8.0%
20.0%
22
6.0%
15.0%
20
4.0%
10.0%
18
46
2.0%
5.0%
16
0.0%
0.0%
20%
40%
60%
80%
100%
20%
40%
60%
80%
100%
Percentage Total Training Data
Percentage of Total Training Data
(1) MIRP dataset
(2) CorLat dataset
Figure 6: Ablation study: impact of training data size the performance of L2P in the MIRP and Corlat dataset.
A.8 EXPERIMENTS ON THE MIPLIB DATASET
In the field of MIP, MIPLIB is the most widely used dataset, and we have thought this dataset during work period. However, the MIPLIB dataset contains diverse instances which are too diverse to be regarded as one distribution, as the machine learning dataset we require the data from an independent identically distribution. Known from their website", they try select instances as diverse as possible with multi-round filtering and clustering, It makes the MIPLIB dataset very hard become good dataset with independent identical distribution.
Nevertheless, we still tried to search for better presolving than default on MIPLIB via heuristics, but we ended up finding there is little improvement on this benchmark. Since we can not find enough labels (better presolving) for constructing the dataset, we did not include MIPLIB in our paper. We plot the search progress below: (represented by the average improvement compared to the default)
Table 7: Searching attempts on the MIPLIB dataset.
Searching step
0
15
30
45
60
75
90
105
Average improvement
-89.6%
-70.0%
-31.6%
-34.0%
-68.1%
-12.2%
-4.31%
-3.84%
Scarching step
120
135
150
165
180
195
210
225
Average improvement
-3.26%
-0.18%
-0.09%
0.04%
0.69%
-0.75%
-4.34%
-8.29%
Our analysis is follows: as a standing benchmark for evaluating MIP solvers themselves, instances of MIPLIB may be well pre-processed such that default presolving is already improved well by the researchers of the MIP solvers, including manually adding new presolvers and adjusting their default strategies. Therefore, there is little room for to further improve the presolving in MIPLIB. While in the real world, is impossible to researchers manually pre-improve with every incoming instance. Therefore, our method still make improvements MIP solvers, as the experiments multiple public datasets show.
A.9 ABLATION STUDY OF ADJUSTING THE TRAINING DATA
To see the influence of the training data, we conduct an ablation study by adjusting the number of training data, from 20%, 40%, 60%, 80%, to 100%. The results are shown in Fig. 6. We can see that with more training data used, L2P will perform better. But we also notice that after using 80% data, the performance of L2P tends to stabilize. Therefore, the idea of finding suitable data size for training indeed makes sense, and we will keep following.
hhttps://miplii zib. wtw.dee/e..e.eeeeee.eeeeeeee wtwpeleeettt__eeeehheeeeeee MetMMMthhollygy html
i
18

---

Published as a conference paper at ICLR 2024
Table 8: The improvement (%) compared to default presolving from the searching process of SA.
instance
step 0
step 15
step 30
step 45
step 60
step 75
step 90
step 105
step 120
step 135
avg.
-15.7
10.4
16.4
17.5
19.0
23.0
28.3
35.3
38.1
39.2
26.44
2.1
-2.1
9.1
9.1
9.1
24.0
24.0
24.0
30.3
-21.1
17.2
17.2
17.2
17.2
17.2
17.2
43.9
45.9
46.1
3
-20.8
6.2
6.2
6.2
14.3
14.3
22.1
22.1
39.4
39.4
-17.7
-10.8
-8.9
-8.9
-8.9
17.6
36.1
36.1
36.1
36.1
5
-17.3
3.2
20.8
20.8
20.8
20.8
31,2
31,2
31.3
33.1
-15.5
29.3
29.7
29.7
29.7
29.7
29.7
29.7
29.7
30.6
7
-14.0
25.0
25.0
25.0
25.0
25.0
25.0
39.2
43.3
45.5
-10.8
-2.1
34.6
38.4
38.4
9
-8.4
8.2
41.8
41.8
41.8
41.8
41.8
41.8
41.8
41.8
-5.6
29.7
31.2
31.2
31.2
44.6
46.2
51.0
51.0
A.10 ILLUSTRATION OF THE SEARCHING PROCESS
To show the information about the generated training set, we plan to show the searching process of the simulated annealing module of the proposed I.2P. As Table 8 shows, we can see that SA can indeed search for better presolving, and its convergence seems fine. For the time consumption of each step, the time limit is 3600s. As result, we find that SA can indeed find better presolving during the tremendous searching process, but the time consumption of it is unacceptable in practice usage since the time consumption of SA is even larger than the B&B algorithm. Therefore, we propose L2P to learn the results of SA while saving running time. Compared to SA which needs hours days to finish searching for each instance, our proposed L.P can make inferences in merely seconds (less than 0.05s in the medium datasets, and less than 0.5s in the hard datasets).
A.11 ILLUSTRATION OF IMPROVED PRESOLVING PARAMETERS
In this paper, we propose the learning to presolve task, which aims at improving the presolving module in existing MIP solvers. To achieve this goal, we propose our L2P to improve the presolving parameters. Here, we consider an illustration of the improved presolving parameters that can better reflect the performance our proposed method. However, the presolve may not be easy to quantify due to its complexity. In Fig. 7 8 9, we try to show the illustrations for improved presolving parameters of 14 diffcrent presolvers under the CorLat, MIK, and NeurIPS 21 Anonymous datasets, in Figure 1/2/3, respectively. Due to the space limit, we choose the top four instances for each dataset by their ranking in the original public zip (not randomly picked). In each figure, we can see that though these four instances are from the same problem classes, the parameters of the improved presolving vary a lot, especially with respect to the priority (order of the presolvers). Meanwhile, we can find that different problem classes show different patterns: some approximately wave-like patterns in each figure. Moreover, we use Tabel to show the decisions of the trained model L2P of the top 10 instances in the CorLat datasets. The [x.y.]] denotes the priority, max-round, and timing of each presolver (decided by our L2P). We also place the default parameters of the presolvers to compare.
A.12 DISCUSSION OF LIMITATIONS AND FUTURE WORK
In this paper, we focus on the mixed integer programming (MIP) area and propose the "learning to presolve" task for the first time. We design deep learning framework integrated with heuristic algorithms, which achieves non-trin non-trivial performance on multiple public MIP datasets. We hope our work could lead to proposing a new task definition and becoming a baseline for other researchers.
direction in machine learning for combinatorial optimization (ML4CO) by
Here, try list some interesting topics which may be direction for future work:
1) Extension to non-linear MIP: our method is designed as a plug-in to the MIP solver, focusing only on the presolve part. As the presolving part is algorithmically agnostic the blackbox of the MIP
19

---

Published as a conference paper at ICLR 2024
solver itself and the MIP instance, work on the MIP instance long the MIP solver can work on it. We plan to try some experiments about non-linear MIP in future work.
2) About scaling and decomposition: taking the scheduling problem as example, when the problem size increases by 10 times, the solving time usually increases by more than 10 times; unless can be strictly decomposed into subproblems (DoComponents), it can achieve the speed difference of only 10 times mentioned here; generally speaking, even if the problem size of the same scenario increases by 10 times, due the coupling of the problem, the presolve module will also increase more than 10 times the workload. Taking the common dominatedCols, dominatedRows, noltdRooBBunddStr in MIP as an example, the judgment method is also (n and above difficulty, In practice, we have also encountered the situation of high time consumption of presolve operators caused by coupling problems, and the time consumption bottleneck lies in SymmetryDDetcction adjust the presolve parameters according to the scenario. Meanwhile, if some problems have strong decomposition and solving properties (such as continuous scheduling problems, multi-stage planning problems, etc.), we can also adjust and train the presolving according the problem scenarios after decomposition, which shows the general applicability of our method: not only suitable for larger scenarios but also provide value for decomposable scenarios, which is also a future work direction.
It is very necessary to
3) Real-world scenarios to use our method: In practice, it is common to repeatedly solve similar MIPs collected from specific real-world applications, c.g., day-to-day production planning and vehicle routing problems. These problems are constructed as mathematical programming models (here, we refer MIP) by human experts in business scenario understanding and operation research. However, there might be a bunch of redundancy in these MIP models, Presolving techniques play a key role in removing redundancy and enhancing the numerical representation of the MIP model. Many modern MIP solvers such as Gurobi and SCIP are equipped with kinds of advanced presolving operators, which are hard-coded heuristics designed by experts. However, hard-coded presolving does not take into account underlying patterns changing among these problems (even if these problems originate from the same business scenario). Thus, we propose our method to exploit the existing presolving operators better, to solve those similar MIPs faster and more stably.
4) Usage on more MIP solvers other than SCIP: commercial MIP solvers may not have the APIs like SCIP, but as long as the presolving module exists, they may have similar parameters to adjust the presolvers. Their APIS are not exposed since they are commercial solvers and not open-source. We consider it impossible to directly improve commercial solvers in research papers, as existing papers mainly conduct experiments on open-source solvers (SCIP) like us. If we cooperate with the commercial solver company in the future, we can also add our method their internal strategy, integrating our machine learning technologies to help users better solve MIPs.
People may think that solvers. We have considered this approach before. Presolving using an open-source MIP solver and then solving the presolved instance using commercial solver is indeed feasible approach. Still, we are concerned that this may raise potential issues, as it requires disabling the presolving module of the commercial solver. Considering that the presolving module and the subsequent model solving are not fully decoupled, presolving algorithms may still be executed when solving sub-mips on non-root nodes and enabling the restart mechanism. we hastily turn off the presolving module of the proprietary commercial solver, it may have unpredictable impacts on its performance. Moreover, the presolving strategy obtained by training on the open-source solver may not be applicable to all solvers. It may also result in negative optimization (we did not verify this point due to time and paper topic constraints). Therefore, we choose a more open SCIP solver to provide personalized presolving settings and complete solving services.
write the presolved MIP to disk and then run it the commercial
20

---

Published as a conference paper at ICLR 2024
14
Instance Instance
Priority
10
Instance
5
Instancee
5
6
8
9
10
11
12
13
Instance Instance 2
Max-round
Instance 3
Instance
3
5
6
7
10
Instance
Timing
20
Instance
Instance 3
Instancee
5
Figure 7: Presolve parameters the Corlat dataset.
Instance Instance 2
Pririty
Instance
Instance
2
3
7
10
11
Instance
Mex-round
Instance
Instance 3
Instance
30
Instance 1
Instance 2
Instance
Instance 4
5
6
10
11
12
13
14
Figure 8: Presolve parameters on the MIK dataset.
Instance Instance
Prionty
Instance 3
instance
3
5
Instance Instance 2
Mox-round
Instance Instance
3
5
9
10
11
12
13
14
Instance
Timing
Instance
Instance 3
Instance
Figure 9: Presolve parameters on the NeurIPS 2021 competition anonymous dataset.
21

---

Published as a conference paper at ICLR 2024
presolver
[2, -1. 16)
[10. 0, 81
[13. 32]
[8. 11.1.32
[2, 02.0.44
12,
(12.0.4] 4]
04.0.41
[1.-1, 16)
[5. 15.1.87
[30.
presolver
[6. 16]
12,-1, 16)
[7,-1,8 8]
1.
[10, 1.8)
[14.
16,0.44
[1,
114,2, 16]
D8. 16]
[13. 0. 8]
presolver
[14. 10-1,,
[8. 16.1..1
[8. 1.
19. 1P.11.4
15. I. 321
111. 32)
14. 1.
12. 13-1..0
14. 1. 32]
15, 15.11.32)
17. F.J. 16)
presolver
[1. 0. [6]
19. -1, 16]
[10. 00.-1.81 81
19, 2. 32)
13. 13.11,33 12]
19. -1,1, 12]
16. -1-1 .2]
19, 2.
[3. 1.4]
[3. 1.8
D1.
Table 9: Detailed presolve parameters for each presolver on the Corlat dataset
presolver
|11,1 8]
[14.0, [6]
112. 16)
111-1, 32]
113,1, 32]
110. 1, 32]
110. 10.-1.8
[9. 0. 81
11.0
19. 11-1,88
7-0,332
presolver
[12,-1, 47
[3. 15.0.41
[6. 1.4]
-1.41
19. -1.11. 8]
(13,-1, 32)
[7. 0. 16]
17.1, 16]
(11.
(11 0. 32
presolver 8
[4,-1. 81
11.0, 321
[4,0.4]
[4,0.4]
[12, 1.
17.-188
15.-1, 81
[12. 11.81
1,
D.0. 8]
18. 16)
presolver
[10. -L. 16]
114,0. 321
112, 32]
111.11 32]
114.0,4 4]
15, 32]
114,0, 32]
[10, 32]
18. 18.0.41 41
112,0.44
14.11,32 32]
presolver
[5. -.-1, [6]
[1.1. [6]
[13. 11.-1.33 32]
[10. 16]
[8. 1. 32]
[12. 12.-1.44 4j
[9. 0, 32]
0,
13,1,44
[4.1.4]
presolver 5
[8, -1, l6]
[10, 2. 32]
114. 1.32 32]
14, 16]
[3,-1, 8J
1.
17, 1.44
0.
15. -1.444
[3.00
0,
presolver
B.0, 161
[12.0.4]
[11,11 32]
113. 32]
0, 32]
41
[11,0.4]
[13,0.8]
1, 8]
19-11.4
12, 1, 32)
presolver
17. -1. [6]
[10. -1. 16]
[14, 81
I1. 1. 321
112. 32]
[6, 2. 32]
13. 0. 32]
[3,0,8] 81
11. 1.
presolver
[I1, 0, 41
[13. -1
12, 0. [6]
(6, 1]
19. 0. 41
[14. 11
[3, 1, 32]
[14. -1.32) 32]
1.1.8 8
0,
18.
presolver
113, 0,
07.0, 16]
15,-1, 16]
13.-1.33 32]
04.0,80 81
13.11, 16]
12, 1,81
[11, 2,
113, 41
[12. 2. 8J
12.
Instance 10
Instance 6
Instance 8
Default
Instance
Instance
Instance
Instacee
22


Reviews:
[{"review_id": "O70xK55QU7", "reviewer": "Reviewer_iKXb", "summary": "The paper presents an innovative framework for Learning to Presolve (L2P) within the context of Mixed Integer Programming (MIP) solving using deep learning. To my knowledge, deep learning methods to solve MIPs haven’t explored L2P. Therefore, this work introduces a novel area of research. The proposed framework is well-conceived, offering a new perspective on presolving, and the evaluation suggests that deep learning can tailor presolving strategies to individual MIP instances, potentially enhancing solver efficiency.", "questions": "1. **Default Parameters:** For reproducibility, could the default parameters (42 x 3) be listed explicitly in the Appendix (Table 5)?\n\n2. **Neural Network Representation:** Figure 3 is unclear as it suggests that a neural network is derived from an MLP, which is already a type of neural network. Could this be clarified?\n\n3. **Graph Embedding Features:** How are these computed and what aggregation mechanism is used? Is there an aggregation of embeddings across all variables?\n\n4. **Priority Label Input:** Have the authors considered using Priority Label as an input, akin to teacher forcing, and could this approach be compared with the current methodology?\n\n5. **Dynamic Loss Averaging:** More details on this, including how weights are adjusted based on convergence, would be beneficial. If a library function is used, please reference it.\n\n6. **Section Clarity:** In Section 4.2, the fifth sentence needs grammatical correction. Additionally, could Section 4.3 further elaborate on the potential privacy issues mentioned?\n\n7. **PD-Integral:** A mathematical description of the PD-integral and its expected range would greatly aid in understanding its application and interpretation.\n\n8. **Table Details:** In Table 4, the metric used and the number of instances in each problem family should be stated for clarity.\n\n**Typos and Corrections:**\n\n1. **Appendix Repetition:** There is a paragraph repeated in Appendix A.1 that should be corrected.\n\n2. **SA Method clarification:** In Appendix A.2, following Equation 4, it seems that $\\Delta_y$ should correspond to the time to solve the instances, as this is the primary optimization concern. Please confirm if this is the case.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Novel Area of Research:** The paper investigates a novel and promising application of deep learning to improve MIP solving, a problem that has not been significantly explored before.\n\n2. **Framework Development:** The authors have developed a new framework to systematically address the identified research gap. This framework could serve as a foundational benchmark for future research in this area.\n\n3. **Empirical Evaluation:** The proposed framework has been rigorously evaluated, with results demonstrating its potential utility for the MIP solving community, which could lead to more targeted and efficient presolving methods.", "weaknesses": "1. **Lack of Detail in Methodology:** The manuscript does not adequately detail critical components of the proposed methods, such as the loss function and the domain of labels—information which is relegated to the Appendix. Moreover, key metrics like the PD integral lack a clear mathematical definition.\n\n2. **Reporting of Metrics:** The paper uses the arithmetic mean to report solving times, which could be skewed by outliers. The geometric mean is a standard in the MIP community for its robustness to extreme values, and its absence is felt in the current reporting.\n\n3. **Comparison and Ablation Studies:** The presolving time is only provided for the L2P method. For a comprehensive understanding of efficiency, it would be beneficial to see these times for other compared methods. Additionally, the specific benefits of KRL are not clear. An ablation study to evaluate the impact of KRL would be informative.\n\n4. **Experimental Details:** The number of instances evaluated in Table 1 is unclear. More detailed comparisons, including the time taken during the Running Step for each method, would strengthen the results section. In Table 4, the metric used and the number of instances in each problem family should be stated for clarity.\n\nWhile the authors have laid a robust foundation with their proposed framework, addressing a significant challenge within the field, I believe further refinement is necessary prior to its wider introduction to the research community. Enhancements such as additional methodological details, comprehensive ablation studies, and the adoption of standard metrics are essential to fully realize and validate the framework's potential.", "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": "6LyHLVElax", "reviewer": "Reviewer_zK3o", "summary": "This paper proposes Learning to Presolve (L2P) for Mixed Integer Programming (MIP). The presolving of the MIP solver is a routine that simplifies the MIP instance, enabling the succeeding main solving routine (e.g., B&B) to operate more efficiently. Current presolving routines are hard-coded and rely on expert knowledge, making them unable to account for instance-wise differences in MIP problems. L2P employs a supervised learning method to predict the best presolver routine while using the result of a powerful yet time-consuming search method as the training label.\n\nUsing the trained model, L2P proposes tailored presolving routines for each instance in fractions of a second. Such tailored routines lead to a significant improvement in MIP solving performance. The proposed L2P consistently demonstrates performance gains in various MIP datasets while requiring a negligible amount of presolving parameter suggestions.", "questions": "- Has the performance gain observed from SCIP also been found with other MIP solvers such as GUROBI and CPLEX?\n- Regarding the training of the L2P model, how crucial are KRL and dynamic loss averaging? Do they significantly affect the overall trend of the results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The writing is easy to follow and effectively conveys the necessary information to understand the manuscript.\n- L2P addresses an understudied aspect of MIP by proposing appropriate presolving parameters on an instance-wise basis.\n- L2P consistently demonstrates performance improvements in empirical experiments.", "weaknesses": "- While the current L2P model shows satisfactory improvements over the baselines, further performance gains may be achievable by leveraging more modern neural network architectures. For example, the authors used GCNN as the backbone of the feature-extracting GNN, which could potentially be replaced with graph-formers in a drop-in replacement manner.\n- It may be beneficial to include some related work in the literature review and experiment section. For example, I had the opportunity to review a paper titled \"Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning,\" which addresses the same problem but in the LP domain.", "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": "nGfG7Cq3Qv", "reviewer": "Reviewer_32Tw", "summary": "The authors propose a learning-based approach for selecting the priority, max rounds, and timing of presolvers for MIP solving. They do this by obtaining high quality presolver settings using simulated annealing for several training instances, then training a neural network to predict the high-quality setting for unseen test instances. The network architecture first predicts the priority then based on the priority prediction makes predictions for the max rounds and timing. They evaluate on a variety of settings that demonstrate their method gives improved performance over other hyperparameter prediction methods especially on hard MIP instances. The authors further perform an ablation study to determine the effectiveness of different components of their model and sensitivity to data collection method. Lastly, they investigate their resulting predictions to identify the impact of setting the individual hyperparameters. The paper is overall well written and they tackle an interesting problem of using machine learning to assist in presolving MIP instances.", "questions": "Simulated annealing also generates several examples of parameters and their values during the search process; however, that seems to be currently thrown away. Is there a way to use something like contrastive learning to learn from this thrown away data?\nSimilarly, is there some way to benefit from the fact that the “shape” of the parameter settings is the same throughout the experiment and don’t change from one instance to the next? Is it possible to re-evaluate several performant hyperparameter settings from one instance on a new instance to quickly collect data?\n\nFor hard/anonymous instances why is the 55% bolded when the other methods also have 55%?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength of this work is that they tackle a new problem in learning-accelerated optimization, namely learning to improve presolving of MIP instances. Additionally, their results seem to give improved performance over baseline hyperparameter tuning methods and improve runtime of optimization solvers overall. Furthermore, the authors conduct extensive evaluation of their approach to better understand where the performance improvement comes from and how sensitive performance is to modification of their approach. Lastly, the authors evaluate their approach on a variety of domains that are used in real-world settings including sustainable corridor optimization, maritime inventory routing, load balancing, and item placement which have practical impacts, and which the authors demonstrate improved performance.\n\nAdditionally, the authors release their code both as a way to benchmark against their approach, but also as a way to enable others working in the space of predicting performant presolver parameters.", "weaknesses": "One weakness is that their approach doesn’t go beyond tuning the hyperparameters of the presolving methods. While their approach does give good performance and is a good first step towards using learning for presolving, it would be interesting to see methods that dive deeper, such as using machine learning to determine new effective methods for presolving.", "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": "fKSYogkv5q", "reviewer": "Reviewer_hVoV", "summary": "MIP solvers make use of various presolving methods to improve their performance, and the parameters for these methods can be tuned for the specific problem instance for maximal effectiveness. The authors propose a deep neural net model that will select those parameters by analyzing the MIP problem structure. This neural network is trained using the solutions found from simulated annealing (SA). The SA takes too much running time to be used for practical cases, but the trained neural net, whose output will mimic the result of the SA, can get the job done very fast, allowing for both good speed and good performance.", "questions": "Questions are described in the weakness section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is an excellent pioneering work on applying a learning approach to the presolving stage of MIP solvers. The results are strong, and the proposed method may be readily applied to practical cases.", "weaknesses": "Reports on the details of the neural net training procedures are missing. For example, what are the sizes of the training set/test set? How many epochs were used for training? How much time used? How long did it take to prepare the SA solutions in each case?\n\nPerhaps the most important aspect of this method in terms of practical usefulness is the number of training data needed for the neural net to adequately learn the distribution of the problem set. Is there a rule of thumb on estimating the size of required training data?\n\nIt would be nice to see some ablation test results that will display the increase in the performance of the L2P+MIP and eventual saturation as more and more training data is used in constructing the neural net model.", "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)