SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimization
Authors: Qian Chen
Tianjian Zhang
Linxin Yang
Qingyu Han
Akang Wang
Ruoyu Sun
Xiaodong Luo
Tsung-Hui Chang
Venue: NeurIPS 2024 poster (2024)
Keywords: integer linear programming
symmetry
machine learning
neural networks
Primary area: optimization

Abstract: Integer linear programs (ILPs) are commonly employed to model diverse practical problems such as scheduling and planning. 
Recently, machine learning techniques have been utilized to solve ILPs.  A straightforward idea is to train a model via supervised learning, with an ILP as the input and an optimal solution as the label. An ILP is symmetric if its variables can be permuted without changing the problem structure, resulting in numerous equivalent and optimal solutions. Randomly selecting an optimal solution as the label can introduce variability in the training data, which may hinder the model from learning stable patterns. In this work, we incorporate the intrinsic symmetry of ILPs and propose a novel training framework called SymILO. Specifically, we modify the learning task by introducing solution permutation along with neural network weights as learnable parameters and then design an alternating algorithm to jointly optimize the loss function.
We conduct extensive experiments on ILPs involving different symmetries and the computational results demonstrate that our symmetry-aware approach significantly outperforms three existing methods----achieving $50.3\\%$, $66.5\\%$, and $45.4\\%$ average improvements, respectively.

SymlLO: A Symmetry-Aware Learning Framework for Integer Linear Optimization
Qian C2 Tianjian Zhang! Linxin Yang Qingyu Han?, Akang Wang Ruoyu Sun Xiaodong Luo?., and Tsung-Hui Chang
Schooo of Science and Engineering. The Chinese University of Hong Kong, Shenzhen, China Shenzhen Research Institute of Big Data, China
School of Data Science, The Chinese University of Hong Kong, Shenzhen, China Shenzhen International Center For Industrial And Applied Mathematics, Shenzhen Research Institute of Big Data, China
Abstract
Integer linear programs (ILPs) are commonly employed to model diverse practical problems such scheduling and planning. Recently, machine learning techniques have been utilized to solve ILPs. A straightforward idea is to train a model via supervised learning, with an ILP the input and optimal solution the label. An ILP is symmetric its variables can be permuted without changing the problem structure, resulting in numerous equivalent and optimal solutions. Randomly selecting an optimal solution as the label can introduce variability in the training data, which may hinder the model from learning stable patterns. In this work, we incorporate the intrinsic symmetry of ILPs and propose novel training framework called SymILO. Specifically, we modify the learning task by introducing solution permutation along with neural network weights as learnable parameters and then design alternating algorithm to jointly optimize the loss function. We conduct extensive experiments on ILPs involving different symmetries and the computational results demonstrate that our symmetry-awas aware approach significantly outperforms three existing methods -ccievvvn 50.3%, 66.5%, and 45.4% average improvements, respectively.
Introduction
Integer linear programs (ILPs) optimization problems with integer variables and linear objective. and have a wide range of practical uses in various fields, such as production planning (Pochet & Wolsey 2006 Chen 2010), resource allocation (Liu & Fan 2018 Watson & Woodruff 2011). and transportation management (Luathep et al.] [201]] Schöhell 2001). An important property that often arises ILPs symmetry (Margot 2003), which refers situation where permuting variables does not change the structure of an ILP.
Recently, there emerges many approaches equipping machine learning methods, supervised learning in particular, to help efficient solution identification for ILPs (Zhang et al.) (203)). Among these approaches, important category derived from the idea of predicting the optimal solution has demonstrated significant improvements (Han et al.) 2023 Ding et al. 2020) Khalil et al., 2022 Nair al. 2020). In this paper, we consider classic supervised learning task that aims to train an MI. model to predict an optimal solution for an IIP. Specifically, given a training dataset = ((s,, v.)) with yi denoting optimal solution instance 8,, hope to train neural network
"Coresponding author: Akang Wang wwwngakang @ sribdden>>
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

model fo(-) to approximate the mapping from ILP instances to their optimal solutions, via minimizing the empirical risk defined on fo (s;) and y/-
However, for an ILP 8; with symmetry, there exist multiple optimal solutions including yi and its symmetric counterparts, any of which has an equal probability of being returned as a label. Training neural networks without taking symmetry into account is basically learning a model supervised by random outputs, leading to prediction models of inferior performance.
To address this issue, we propose to leverage the symmetry of ILPs to improve the model performance of predicting optimal solution. Specifically, given input 8;, we define a new empirical risk using fo(s:) and 77, (y:), where ( denotes the operation of permuting elements in yi into its symmetric counterpart. Along with ML model parameters, the permutation operators will also be optimized during training. To achieve this, we further develop a computationally affordable algorithm that alternates between optimization of model parameters and optimization of permutation operation. The distinct contributions of our work can be summarized as follows.
We propose a symmetry-aware framework (called SymILO) that introduces permutation operators as extra optimization variables to the classic training procedure.
We devise an alternating algorithm to solve the newly proposed problem, with a specific focus updating the permutation operator for different symmetries.
We conduct comprehensive numerical studies four typical benchmark datasets involving symmetries, and the results show that our proposed approach significantly outperforms existing methods.
2
Related works
Previous works on identifying high-quality solutions to ILPs via machine learning techniques mainly focus on reducing problem sizes. For example, [Dng et al. (2020) propose to identify and predict subset of decision variables that stay unchanged within the collected solutions. Li & Wu (2022)
formulate MILPs as Markov decision processes and learn reduce problem sizes via early-
It is noteworthy that the emergence of GNNs has had significant impact on solving ILPs. Gasse et al. (2019) are the first to propose bipartite-grap representation of ILPs and pass GNNs. Nair et al. (2020) adopt the same representation scheme and train GNNs to predict the conditional distribution of solutions, from which they further sample solutions. Rather than directly fixing variables, Han et al. 2023) conduct search algorithms in a neighborhood centered around an initial point generated from the predicted distribution. Other works based on GNNs (Sonnerat al., [022] Lin al. 20199 Khalil et al.] [0222] Wu et al., 202T) also illustrate great potential in improving the sol sol ving efficincy.
Limitations of the existing GNN-based approaches also noticed. Nair al. (2020); Han al. (2023) try to address the multiple solution problem by learning the conditional distribution. Chen al. (2022) introduce random features into the bipartite graph representation to differentiate variable nodes involving symmetries.
However, none of the existing learning- approaches explicitly leverage the inherent symmetries in ILPs to achieve improvements. In contrast, works from mathematical optimization perspectives suggest that symmetry handlling algorithms exhibit great abilities in solving yymmetry-involvinn ILPs (Pfetsch Rehn 2019). To name a few, such algorithms include orbital fixing (Ostrowski et al. tree pruning (Margot 2002), and lexicographical ordering (Kaibel & Pfetsch 2008).
201
3
Background and preliminaries
3.1 ILPs
An integer linear program (ILP) has a formulation as follows:
min {c Ax S b, )nd
where 2 are integer decision variables, and c R A px e n are given coefficients.

---

3.2 Symmetry Group
Symmetry of ILPs is typically represented by groups. We start with some basic notations and most of which follow Margot (2009). Denoting the index set by I" {1, 2.... n),, a permutation I" .....
is a bijective (one-to-one and onto) mapping т. 1 + I" For example, an identity permutation maps the index set itself (*( =) and a eyclie permutation has rotational mapping rules (i(1) i + 1) 1 and T(n) = 1. Schematic diagrams of these two permutations and other ones shown in Figure For brevity, we abuse the notation π a little bit and denote the permutation acting
vector y E RR by rearranging its coordinates, namely x (y) [ (2), Mr(n)] Let Q be the set of all feasible solutions of (I and S, the set of all permutations on I Note that S, is referred as the symmetric group, which should not be confused with the symmetry group discussed as follows.
Definition 3.1. A symmetry group of itself, such that each feasible solution is mapped to another feasible solution with the same objective value, i.c.,
I1 is defined as the set of all permutations that map Q onto
G = { E S. c y c cTT( (ū) and π (ī) E Q, vy Q)
(2)
Next, we will delve into three commonly en- countered symmetries, accompanied by typical example problems. Since not all variables in an ILP involve symmetry, the size of the symmetry group.
q S to indicate
カ-
(a) Identity permutation
(b) Swapping pemuutation
Symmetric group The symmetric group, de- noted by Sq, is the group that consists of all per- mutations (q! in total) on I". Problems with this kind of symmetry include bin packing (John- son 1974) and optimal job scheduling Graham al. (1979), etc. An example is illustrated Appendix B.0.1
1 2
(c) Cyclic permutation
(d) Reflective permutation
Permutation examples with directed edges denoting mapping rules.
Figure 1:
Cyclic and dihedral groups As its name sug- gests, cyclic symmetry allows elements be permuted to their right neighbors, cycling the right-most variables back to the left, e.g., cyclic (or rotational) permutation p Figure The elements of a cyclic group C, are powers of p. and |C₂l = Problems with cyclic group often have characteristies of rotations or cycles, e.g., periodic event scheduling problem (Serafini Ukovich 1989).
Compared to the cyclic group, a dihedral group (denoted as D2) additionally includes reflective permutations, which is illustrated in Figure (d). Consequently, D, comprises total of 2g distinct permutations. A typical problem with such symmetry is the circular (or modular) golomb ruler problem (see Appendix B.0.2..
3.3
Classic supervised learning for solution prediction
classic solution prediction task based on supervised learning formulated as follows. Let S be the
space of ILP instances and ) be the label (i.e., optimal solution) space. A model function so S + y parameterized by 9 E θ is used to learn a mapping from instances to optimal solutions. Let P(S, Y) be distribution over S x V. The performance of the model function is measured by criterion called true risk: R(fe) == EP(S.Y) [6 (ff(s), v)], where É: y x y - IR+ is a given loss function, e.g., mean squared error cross-entropy loss. An intuitive way to improve the model performance is to minimize the true risk. However, one cannot access all data from distribution P(S, Y), which makes it impossible to calculate the true risk. Practically,
can obtain set of (instance, solution)
pairs called training data D {(s,, v.) S (S V) sampled from P(S, Y). based on which define the empirical risk as
()o; = N
Σ (f)(s))
i=1
3

---

By minimizing the empirical risk, i.e., minøge 7, one aims to approximate the minimization of the true risk, under the assumption that the training data is a representative sample of the overall data distribution.
4 Methodology
4.1
Reformulation of the learning task
In Section 3.3 we introduce a classic supervised learning task for general ILPs, which aims at learning a mapping So from instances optimal solutions. In this task, a dataset D {(*,, M:) is given, and the mapping fo is learned by minimizing (3) with 0 as decisions. However, for ILPs with symmetry,
ILP instance has multiple solutions (let Y; be the set of optimal solutions of i-th instance). As a consequence, the labels this task have multiple choices, thus datasets choosing different optimal solutions labels (D' {(s:: v/) (/)), V v E Y;) all valid for the learning task. Empirically, we observe that different D' can lead to distinct performance, which motivates us to consider the selection of labels for ILPs with symmetry.
We reformulate the learning task as follows. Firstly, we augment dataset to dataset D, {ss, Mi. G.)), where G; is the symmetry group of i-th instance and n; G, Secondly, we define the symmetry-aware empirical risk as
Ta (fe. {T.) D.) = N E (ff(ss))
Then, the mapping fe is learned by minimizing the symmetry-awe aware risk as ming Ts (both @ and π as decisions). In contrast to the original task, the symmetry-awart task uses symmetry information by introducing extra decisions [ so as to dynamically selecting proper optimal solutions as labels. There are important differences between the symmetry-aweer aware empirical risk and the classic one:
Proposition 4.1. Let"" and r be the global minimal values of ming and ming, Ta. respectively. Then, the following claims hold:
(i) r S r*,
(ii) r r", if there exist i,j
NN. such that 8; = S. and y: Vj-
Claim (i) always holds since ming is special case of mine,7 Ts when Ti,...., TN are all identity permutations. Claim (ii) shows a significant advantage of r, compared to r. A non-rigorous proof is available in Appendix A.
4.2 An alternating minimization algorithm
The minimization of 4 is challenging due the discrete nature of æ. Motivated by the well-known block coordinate minimization algorithms (Mangasarian 1994), we update and x alternately, i.c.,
++ Ji=1 +- arg min Ta (for, {m) R.EG,
(5)
gh+1 f- arg min (fo, (1 k+11 Jim Dz).
8E0
Such alternating mechanism divides the minimization of into sub-problems: discrete optimization in (5) over sets [G and a classic empirical risk minimization in (6). Repeatedly solving (6) to optimal is unrealistic, thus it more practical to update by several gradient steps instead.
The sub-problem in (5) is further specified as shown in Section 4.2.1 according to the symmetry structures in the ILP instances.
We summarize the proposed alternating minimization algorithm in Algorithm In the main loop. { are updated first (line 5), after which an inner loop (lines 6-10) is operated to update through a gradient-based method GD, e.g., Adam (Kingma & Ba 2014). These two updates alternate until a preset maximum number of epochs is reached. We finally note that Algorithm [ can be casily adapted to mini-batch version, in which the data can be randomly sampled from D..

---

Data
Model Biportihe representation
Downstream Tasks
Graph Neural A Networks fo
Prediction
$1, m.. Sp
Fix optimize
Puzx
Solutions
Selection
22-32.-m Yn
Training
Symmetry-mec awarr emponical risk SoRLENG R
teraating updates Updale
Local Branching
Symmetiies
G2 G2 m. Gn
Update 0
Figure 2: An overview of the SymILO framework.
4.2.1 Optimization over symmetry groups in
In this section, we investigate the concrete formulations of the sub- uu-probleem in (5) for the symmetry groups mentioned in Section 3.2 (symmetric group, cyclic and dihedral groups), and devise algorithms to solve them.
Algorithm Alternating optimization
Input: Dataset D. [(>.: ye, G.) K,T 2: Output: 8%
Initialize ML model parameter 0¹;
for ls to
do
5: {m. k+tt
[ ji=1 < arg min,, T ra(Jon: (Ti)
Cyclic and dihedral groups The cardi- nality of cyclic group C is q. and it is 2q for dihedral group D,. For symmetry groups with such reasonably small size, a straightforward and effective way to solve 5 is to evaluate all possible permutations and select the one that yields the minimum T..
0'
+ p
7:
for f + 1 to
do
8:
0++1 +- GD(0", Varr(0'' (x (::t))):D.))
9:
end for
10: gh+1 <- 0":
1I: end for
Symmetric group The cardinality of a symmetric group is factorially large, |S,1 = d!, so it is impractical to traverse all permutations. Since :I,..., AN are not coupled, we can separate them and solve the N sub-problems individually:
min (fo(si), T. (T:)) vi I,
Without loss of generality, consider an ILP whose variables have matrix form (e.g., see Appendix B.0.Ip, denoted by X (pxx(pp> 9 < n), and symmetric group S, acting on its column coordinates. In this case, is equivalent to solve the following binary linear program (BLP),
(x,XP) s.t. PE (0, 13,1 P = P1 P
min
(8)
where P is a permutation matrix, X is the matrix form of fs:);) and 1 an all-one vector. We relax P to take continuous values between O and 1, and get linear program (LP),
min l (X,XP) s.t. PE P = 1, P1 11
According to Proposition 4.2 one can solve (). to get the optimal permutations for the original problem in (8). It can be done quite efficiently with the aid of off-the-shelf LP solvers, such Gurobi Optimization. LLC (2023), CPLEX IBM (2020), etc.
Proposition 4.2. When is the squared error or binary cross-entropy loss, the optimal solution to is also an optimal solution to ( (See the proof in A.2
4.3 An overview of the SymIL.O framework
In this section, we summarize a novel learning framework (SymlLO) that utilizes symmetry for solving ILPs. An overview is depicted in Figure 2 which consists of two parts: the upper row connected by green arrows delineates graph neural network (GNN)-based workflow, and the lower row connected by red arrows outlines the training process.
5

---

For the GNN-based workflow, an ILP is first converted to bipartite graph (see appendix C for details), which then fed GNN model fo (see appendix [ details), producing predicted solution. Notably, the predicted solution is finally used in downstream tasks for refinement, Due to the complexity of solving IIPss existing methods, such as [air et al. (2020); Ding et al. (2020);
Khalil et al. [022); Han et al. (2023). often include post-processing module taking the predicted solution as an initial point to identify higher-quality solutions. Our approach follows this routine and integrates certain downstream techniques. Section 5.1 specifies three downstream tasks.
For the training process, the data used to minimize the symmetry-aware empirical risk r, include the collected solution and the symmetry group G2 of each instance S,. Both parameters 0 of the GNN model and permutations { of each solution are optimized via an alternating algorithm mentioned in Algorithm[] Given trained model føx, the prediction fax (s') for an unseen instance is used to guide the downstream tasks identifying feasible solutions. Note that (z, (=:);=1 are utilized only in the training phase but not in the inference phase.
5
Experimental settings
In this section, the experimental settings are presented. The corresponding source code is available at https://gitbb..cm//eeeyyyyyp/pp
5.1 Downstream tasks and baselines
In our experiments, we pass the predictions of GNN models to three downstream tasks, namely fix and optimize, local branching, and node selection, identify feasible solutions. For each downstream task, we choose one existing method baseline. The downstream tasks and their corresponding baselines (in parentheses) are shown below.
Fix and optimize (ND): "Fix and optimize" refers to strategy where one first "fix" or set some variables to specific values and then "optimize" the remaining variables to find better solutions. The baseline we choose is "Neural Diving" (ND) proposed by Nair et al. (022). technique using graph neural network to generate partial assignments for ILPs, which creates smaller sub-ILPs with the unassigned variables.
Local branching (PS): Local branching is a heuristic method that constructs a linear constraint based given initial solution to the original IIP instance. This constraint restrains the search space a region around the initial solution. It can help guide the optimization process toward better solutions while balancing computational efficiency. Approaches based on this idea include Ding et al.) (2020); Han et al. (2023); (0023)/Chenn Chen et al. (2023) and we select the ppredict-and-eeae (PS) framework proposed by Han al. (2023) as a baseline.
In branch and bound algorithms, node selection is a process of choosing the proper nodes to explore next. Effective node selection is crucial for the algorithm's success in solving optimization problems. "MIP-GNN" (MIP-GNN) proposed by Khalil et al. (2022) uses GNN prediction guide node selection and warm-starting, and is selected as another baseline.
Node selection (MIP-GNN):
5.2 Benchmark datasets
We evaluate the proposed framework on four ILP benchmarks with certain symmetry, which consists of (i) two problems with symmetric groups: the item placement problem (IP) and the steel mill slab problem (SMSP), (ii) the periodic event scheduling problem (PESP) with cyclic group, and (iii) modified variant of PESP (PESPD) which has a dihedral group.
The first benchmark IP is from the NeurIPS MLACO 2021 competition (Gasse et al.) 2022 We use their source code to randomly generate instances with binary variables ranging from 208 1050. Each instance has symmetric group S₁ ~ S1p. We use 500 instances for our experiments, taking 400 as the training set and the remaining 100 for testing. The SMSP benchmark is from [Shauu et al.) (201T), and contains 380 problem instances. We randomly select 304 of them training data and take the others as testing data. The instances of this benchmark have 22k~24k binary variables and nearly 10k constraints, with each of them having symmetric group S111. The last two benchmarks are from

---

PESPlib Goerigk 2012). collection of periodic timetabling problems inspired by real-worke railway timetabling settings. Since PESPlib only provides a few instances, which are not sufficient to support neural network training, we randomly perturb the weights of the provided instances to generate more data (see Appendix G.3.1 for details). We respectively generate 500 instances for PESP and PESPD, taking 400 of them as training sets and 100 as testing sets. The symmetry groups of these two datasets are cyclic groups C₁ ~ C15 and dihedral groups Ds ~ D1s, respectively. For all training sets, 30% instances are used for validation. The average numbers of variables and constraints, well as the symmetry groups of each benchmark problem, are summarized in Appendix F.T Besides, more details about their ILP formulations and corresponding symmetries are supplemented in Appendix G
These benchmarks only include problem instances. We collect the corresponding solutions using an ILP solver CPLEX (IBM (020). However, solving ILP instances even with moderate sizes to optimal extremely expensive. is more practical to use high-quality solutions as the labels. Therefore, we run single-thread CPLEX for time limit of 3,600 seconds and record the best solutions.
5.3 Training settings
All models are trained with a batch size for 50 epochs. The Adam optimizer with a learning rate of 0.001 is used, and other hyperparameters of the optimizer set to their default values. The model with the smallest loss on the validation set is used for subsequent evaluations. Other training settings, such as the loss function and neural architectures, follow the configurations in Han et al. (2023). tuning for the downstream tasks and software resources are
More details about the shown in Section E
5.4 Evaluation metrics
To compare the prediction performance of the model trained on r and rs, we define the Top-m % error for evaluation. In addition, another criterion relative primal gap is used to evaluate the final performance in identifying feasible solutions in different downstream tasks.
Top-m % error:
We use the distance between rounded prediction and its nearest equivalent solution the error. Specifically, given a prediction ÿ and its label y. we define the equivalent solution closest to ÿ as ÿ = x' (v), where nO = arg min, a 11 - x (-)]l- Then, the Top-m% error is defined as
E(m) Σ REM
Round mel
(10)
where M is the index set of m% variables with largest values of [Round ύزو- This error measures the minimum distance between the prediction and all solutions equivalent to the label. Compared to naive use of the distance Σiem [Round(ū.) yel. (10) can more accurately represent how close a prediction is feasible solution. Since for the naive distance, when Round equals any equivalent solution (y) * y, the distance is greater than 0, while that of (10) is O.
Relative primal gap: We also feed the outputs of the models trained through r. to the downstream tasks mentioned in Section 5.1 to evaluate the quality of the predictions. All the three downstream approaches incorporate ILP solvers to search for solutions. We run these ILP solvers on a single thread for a maximum 800 seconds. Since all the problems used in the experiments are NP-hard, identifying optimality is highly time-consuming. Thus the metric used in our experiments is relative primal gap
Ic ū c. v PG( =
(11)
lc 1 +
which measures the relative gap in the objective value of feasible solution ý to that of the best-known solution y², and is small positive value to avoid the numerical issue. Additionally, let "r and 7r, respectively be the primal gaps of models trained through r and rs, then an improvement gain of our
approach is calculated as (+r 7r.)/ 7/r.)
7

---

Numerical results
In this section, we present the comparison results empirical risk and symmetry- rs. In addition, primal gaps of Symll. and baselines on three downstream tasks are reported.
6.1 On empirical risks and Top-m% error
We denote training and test risks by r" (-) = r(:; D(r) and pdr r(; Di respectively. and similarly use r and rs for symmetry-avee aware model obtained at k-th epoch by training with r and r" respectively. We plot both the training and test risks versus the number of epochs in Figure []] As predicted in Proposition 4.1 when algorithms converge, the classic empirical risk r is always greater than symmetry-avee -waar risk r
risk. Let f(k) and fa²) be the best classic model and symmetry-
(((t))
r (FiRi)
r ((
0.44
0.14
3.00
3.00
empirical
empirical
empiricllnis
empiricalrisk
0.38
0.09
2.11
2.44
0.31
0.05
1.22
1.89
0.25
0.01
0.33
1.33
0
50
50
50
50
epoch
epoch (b) SMSP
epoch (c) PESP
epoch
(a) IP
(d) PESPD
Figure 3: The training and test risks v.s. the number epochs on four benchmark problems.
As shown in Table 1 the symmetry-aware model f!k) always predicts smaller Top-m% errors in 10) compared to the classic model p(k), demonstrating the usefulness of proposed empirical symmetry-aware risk predicting solutions correctly.
Table 1: Top-m% errors (4) of model (() and 1(k) averaged over different datasets.
IP
SMSP
PESP
PESPD
((K)
(K)
((K)
5(R)
(4
f(0)
(K)
10%
0.8 +0.8
+0.6
0.6
0.0:1 0.0
7.5+17
0.1::0.2
87.4+:1
12.7==4.8
30%
3.9
2.9 +13
5.3+
2.6
0.1 0.1
44.2+35
0.1+-0.5
275+73
81.3++24
50%
17.0
4-2
5.1 +1.7
19.5 5.5
0.6 2.5
52.7+335
0.3+0.8
422+1102
2237777
70%
46.5
12.8
36.3 14.3
47.51 9.8
17.81 6.6
122.126
23:15.5
638.193
4861114
90%
82.9
+1.5
76.1
1:300
1034 15
47.01
1.6k130
212:123
854169
848:99
Moreover, the time costs of minimizing different em- pirical risks and r. for a mini batch are shown Table 2 Here, Ê denotes the average time of solving the permutation decisions per instance. The reported times for r, include the optimization time t. The ta- ble illustrates that the alternate training strategy does not significantly increase the training duration, and the optimization step over ı executed efficiently.
Table 2: Time cost for minimizing differ- ent empirical risks (in seconds).
IP
SMSP
PESP
PESPD
5.54
69.43
14.97
16.17
Fx
6.01
71.5
15.14
16.46
0.029
0.129
0.011
0.018
6.2 Downstream results
The relative primal gaps of different downstream tasks at different solving time are shown in Figure 4 and the final values 800 seconds are listed in Table 3 As Figure 4 shows, proposed empirical risk significantly improves the performance of different downstream tasks over the primal gap in 800 seconds.
Note that the node selection task exhibits modest performance in comparison to other tasks; possible reason is that it requires runtime interaction to call the callback functions provided by the CPLEX

---

ND
P8
MIP-GNN SymILO+ selection
Tuned CPLEX
SymlLLOFFiskoop Fiikooptiize
SymILO+Local Branching
12
Primal gap
0.3
Primal gap
Prima gap
Primal gap
0.0
0.2
0.6
0.4
0.1
02
18
205
420
332
332
10
200
400
600
100
200
400
820
100
10
200
402
023
000
Solving time
Solving time
Solving time
Solving time (d) PESPD
(a)
SMSP
PESP
Figure 4: Relative primal gaps at different times. Three downstream tasks, i.e, fix- fix-and-optimize, local branching, and node selection, are evaluated with a time limit of 800 seconds. The results the same downstream task use the same color. In addition, the relative primal gap of the Tuned CPLEX running on a single thread is also reported as the blue dashed line.
Python APIs, which can slow down the whole solving process. However, such flaw does not affect the demonstration of the effectiveness our proposed method.
For the primal gap at 800 seconds shown in Table 3 the models trained through significantly improve all downstream tasks. The performance gain of the model trained through r, is calculated by computing the relative gaps between our approach 's gap improvements and that of the baselines. Average gains over the three downstream tasks are 50.3%, 66.5% and 45.4%, respectively. The overall results demonstrate the effectiveness of the proposed empirical risk r., We also provide the corresponding p-values for the significance of improvements Appendix
Table 3: Average relative primal gaps (4) different downstream tasks at 800 second. The values in this table are averaged over primal gaps of all test data for each benchmark problem. "Tuned CPLEX" the result the tuned CPLEX running on a single thread.
Fix&optimize
Local branching
Node Selection
Dataset
Tuned CPLEX
ND
SymII.0
gain(t)
SymII.O
gain(t)
MIP-GINN
SymIl.O
gain(t)
IP
0.188
0.201
0.124
38.4%
0.168
0.102
39.4%
0.312
0.190
39.2%
SMSP
0.190
0.300
0.180
40.0%
0.230
0.160
30.4%
1.180
0.740
37.3%
PESP
0.056
0.084
0.050
39.8%
0.306
0.000
100%
1.899
0.280
85.3%
PESPD
3.194
2.389
0.404
83.1%
3.442
0.127
96.3%
3.755
3.006
20%
Avg.
50.3%
66.5%
45.4%
Limitations and conclusions
In conclusion, propose SymILO, novel symmetry-awee aware learning framework for enhancing the prediction of solutions for integer linear programs by incorporating symmetry into the training process. methods
Our approach shows significant performance improvements over symmetry-agnosee benchmark datasets. Despite the significant advancements presented in our symmetry-awan learning framework, SymlI.O, several limitations must be acknowledged. Firstly, while we provide realizations for three commonly encountered symmetry groups symps--smmmtric.... cyclic, and dihedral-the framework requires specific formulations for optimizing permutations, which limits its immediate applicability to other symmetry groups not discussed in this work. Secondly, for large-scale problem instances with extensive and complex symmetry groups, the sub-problems involved optimizing permutations can significantly slow down the training process. Enhancing the computational efficiency of our alternating optimization algorithm for these cases remains challenge and area for future research.

---

Acknowledgments
This work was supported by the National Key R&D Program of China under grant 2022YFA 1003000. Akang Wang also acknowledges support from the National Natural Science Foundation of China (Grant No. 12301416), the Shenzhen Science and Technology Program (Grant No. the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2024A1515010366) and the Longgang District Special Funds for Science and Technology Innova- tion (LGKCSDPT2023002) Ruoyu Sun also acknowledges support from the Hetao Shenzhen- Hong Kong Science and Technology Innovation Cooperation Zone Project (No. HZQSWS-KCCY? the Chinese University of Hong
(CBS20221008093300099
2024016), the University Development Fund (UDF0100149) Kong. Shenzhen, the Guangdong Provincial Key Laboratory Mathematical Foundations for Artifi- cial Intelligence (2023B1 21 212010001), and the Guangdong Major Project of Basic and Applied Basic Research (20238033300000), Tsung-Hui Chang acknowledges support from the Shenzhen Science and Technology Program (Grant No. ZDSYS2023006260110002000
References
Chen, Y., Gao, W. Ge, D., and Ye, Y. Pre-trained mixed integer optimization through multi-variable cardinality branching. arXiv preprini arXiv:2305. 12352 2023.
Chen, Z., Liu, J., Wang, X., Lu, J., and Yin, W. On representing mixed-intege linear programs by graph neural networks, 2022.
Chen, Z.-L. Integrated production and outbound distribution scheduling: review and extensions. Operations research, 58(1):130-148, 2010.
Dantzig, B. Linear inequalities and related systems. Number 38. Princeton university press, 1956.
Ding, J.-Y., Zhang, C., Shen, L., Li, S., Wang, B., Xu, Y., and Song. L. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaai conference on artificial intelligence, volume 34, pp. 1452-1455 2020.
Gargani, A. and Refalo, P. An efficient model and strategy for the steel mill slab design problem. In International Conference on Principles and Practice of Constraint Programming, pp. 77-89. Springer, 2007.
Gasse, M., Chetelat, D., Ferroni, N., Charlin, L., and Lodi, A. Exact combinatorial optimization with graph convolutional neural networks. Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F. Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: /ttp///htp////rrcdddngge neurips ww/ppperpppppppe/ppppp hecc//ppe_fffeess_._eeeeeee files/pap er
Gasse, M., Bowly, S., Cappart, Q., Charfreitag, J., Charlin, L., Chételat, D., Chmiela, A., Du- mouchelle, J., Gleixner, A., Kazachkov, A. M., et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurIPS 2021 Competitions and Demonstrations Track, pp. 220-231. PMLR, 2022.
Goerigk, M. Pesplib-a benchmark library for periodic event scheduling, 2012.
Graham, R. L., Lawler, F. I.,, Lenstra, J. K., and Kan, A. R. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics, volume pp. 287-326. Elsevier, 1979.
Gurobi Optimization, LLC.C Gurobi Optimizer Reference Manual, 2023. URL TtRlhttpss: www. www. bi. com
Han, Q. Yang, I.., Chen, Q., Zhou, X., Zhang, D., Wang, A., Sun, R., and Luo, X. gundddd predict-and-searee framework for mixed integer linear programming. In The Eleventh International Conference on Learning Representations, 2023.
IBM, I. C. O. V20. 1: User's manual for cplex. IBM Corp, 2020.
10

---

Johnson, D. S. Fast algorithms for bin packing, Journal of Computer and System Sciences, 8(3): 272-314, 1974.
Kaibel, V. and Pfetsch, M. Packing and partitioning orbitopes. Mathematical Programming, 114(1):
1-36, 2008.
Khalil, E. B., Morris, C., and Lodi, A. Mip-gnn: A data-driven framework for guiding combinatorial
solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10219- 10227, 2022.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Kuhn, H. W. The hungarian method for the assignment problem. Naval research logistics quarterly 2(1-2):83 97083,9--000 1955.
Li, L. and Wu, B. Learning accelerate approximate methods for solving integer programming via early fixing. arXiv preprint arXiv:2207.02087 2022.
Lin, X., Hou, J., Ren, H., and Pan, F. Approximate mixed-integer programming solution with ma- chine learning technique and linear programming relaxation. In 20/9 3rd International Conference on Smart Grid and Smart Cities (ICSGSC), pp. 101-107, 2019, doi: 10. 10.1109/CSSSC..2000 100CCSGG...21900--111 11.
Liu, L. and Fan, Q. Resource allocation optimization based on mixed integer linear programming in the multi-cloudlet environment. IEEE Access, 6:24533-24542 2018.
Luathep, P., Sumalee, A., Lam, W. H., Li, Z.-C., and Lo, H. K. Global optimization method for mixed transportation network design problem: mixed-intege linear programming approach. Transportation Research Part B: Methodological, 45(5):808 827,8887744 2011.
Mangasarian, O. L. Nonlinear programming. SIAM, 1994.
Margot, Pruning by isomorphism in branch-and-cut. Mathematical Programming, 94:71-90, 2002.
Margot, Exploiting orbits in symmetric ilp. Mathematical Programming, 98:3-21, 2003.
Margot, F. Symmetry integer linear programming. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, pp. 647-686, 2009.
Nair, V., Bartunov, S., Gimeno, F., Von Glchn, I., Lichocki. P., Lobov, L, O'Donoghue, B., Sonnerat,
N., Tjandraatmadja, C., Wang, P., et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.133443 2020.
Ostrowski, J., Linderoth, J., Rossi, F., and Smriglio, S. Orbital branching. Mathematical PaccermmmaccaaPoorammniiin Programming, 126: 126:147-178, 2011.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein,
N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8035-
Curran Associates, Inc., 2019. URI. htt.:htttp/ppprrr hwwpppppee....rrrrpeeeeeeeee pttp:rppp.../pppp///////11/////
n- n-imperative style- hiwhle-hhgh--erffrmee
learning Seearning-library. www.llirrryyp.. pdf
Pfetsch, M. and Rehn, A computational comparison symmetry handling methods for mixed
integer programs. Mathematical Programming Computation, 11:37-93, 2019.
Pochet, Y. and Wolsey, L. A. Production planning by mixed integer programming, volume 149. Springer, 2006.
Schaus, P., Van Hentenryck, P., Monette, J.-N., Coffrin, C., Michel, L., and Deville, Solving steel mill slab problems with constraint- based techniques: Cp, Ins, and cbls. Constraints, 16:125-147, 2011.
Schöbel, A model for the delay management problem based on mixed-ntege--rogramning Electronic notes in theoretical computer science, 50(1):1-10, 2001.

---

Serafini, P. and Ukovich, W. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581 1989.
Sonnerat, N., Wang, P., Ktena, I., Bartunov, S., and Nair, V. Learning a large neighborhood search algorithm for mixed integer programs, 2022.
Watson, J. and Woodruff, D. L. Progressive hedging innovations for class of stochastic mixed- integer resource allocation problems. Computational Management Science, 8(4):355-370, 2011 1.
Wu, Y., Song, W., Cao, Z.,, and Zhang, J. Learning large neighborhood search policy for integer programming, Advances Neural Information Processing Systems, 34:30075-30087,200 2021.
Zhang, J., Liu, C., Li, X., Zhen. H.-L., Yuan, M., Li, Y., and Yan, A survey for solving mixed integer programming via machine learning, Neurocomputingg, 519:205-217, 2023.
12

---

A Theoretical proofs
A.1 Proposition 4.1
Non-rigorous Proof: Consider the case where $1 = 82, V1 * y2, and is the mean squared error, and let fo() fo(32). Then,
1 2 (l0 y1l1 + 11ú y2ll²)
2 min
4 ll y2ll > 0.
While for the symmetry-aware risk, since 81 and 82 corresponds identical instances, there must exist permutations oí and Tz. such that 7ं (31) = x2( Consequently,
min 110 (1n)l + ll =
A.2
Proposition 4.2
Proof: When the loss function E(.; is the squared error (SE) or the binary cross-entropy loss (BCE),
(sn(X, || 2
(12)
= -tr(AT T 2X X
(13)
-tr(AT x - 2X X X),
(14)
(nCE(X,XP) = Σ ([XP) log X,x + (1 -1- [1P) log(1 log(1 - Xzx)),
(15)
j.k
equations 13 to 14 hold for permutations of a matrix's rows and columns don not change its
Frobenius norm, i.e., tr(PT X X XP) |XP = I tr(X X). (14) and (15) show that these two loss functions are linear w.r.t P. with which ( becomes linear assignment problem Kuhn (1955). is easy verify that the constriant matrix of linear assignment problem is totally unimodular- satisfies the four conditions of Hoffman and Gale (see Page 252 in Dantzig (1956)),
thus an optimal solution of the relaxed problem must be integral as well, namely an optimal
solution to problem
B ILP examples with different symmetry group
Example B.0.1. Consider bin packing problem, in which there are three items T == (1,2,3) with sizes {0r = 1, 12 2, a3 = 3) and three identical bins J = {1,2, 2, 3} with capacity B 3. Items packed into bins, and it is required to minimum number of bins without exceeding the capacity. The specific formulation is as follows:
min Ef0.1)
11 + 1/2 + 1/3
01 + 02 + 03T3) S Byj
Vj
(16a) (16b)
Ia + Σ22 - T33 = 1,
Vi 1
where y = 1 denotes j-th bin used and Tzy denotes i-th item placed in j-th bin.
Figure 5: Equivalent solutions of Example B.0.1
Since all bins are identical, arbitrarily swapping them does not change the feasibility and the objective value, e.g., the different assignments shown in Figure are all equivalent. Specifically, assume
V/
1/2
V/
[]
1 07
X
Ø11
.12
.13
0
.21
./22
.723
.311
.732
1333
1
0
0
13

---

is an optimal solution to the problem 16. then
1
0
0
1
0
0
1
1
0
0
1
0
0
1 0
1
0
x=
0
0
1
1
0
0
1
0
0
1 1
0
0
0
1
0
0
0
are all equivalent solutions to X. Formally, this problem has a symmetric group S3 {(1, 2,3), (1,3, 2), (2, 1,3,, (2, Example B.0.2. Given circle with circumference 8, place ticks at integer points around the circle such that all distances between inter-ticks along the circumference are distinct. The formulation of this problem as follows:
2, (3,2,1), (3,12), w.r.t its bin numbers J.
min 0 F2.33
s.t. Yij x; zzl:
v(i,J) e S.
(17a)
dı min ( Uijs 8 yish:
v(i,j) E S,
(17b)
d12 # d13, d12 d23, d13 + d23
V(i,j)
(17c)
where S (1,, (1. 3), (2. 3)), 21, 22 23 {1. 3, 4, 7,8) denote the positions of each
tick, dij are distances between ticks i and j with auxiliary variables Yij. The constraints in this
formulation are nonlinear, we linearize them by big-M methods. Equalities (Ta) can be linearized by introducing auxiliary variables di E {0, 1}. (i, E Sas
Vij 2 Ii Fzj
v(i,)) E,
(18a)
Mij 2 Ij Ti.
v(i,)) E S
(18b)
y4 $ T; I. + 8 Oij. -
v(i,)) E S,
(18c)
Yij S
xs + 8 (1 (1- a:y).
(18d)
when 2 ky. az = 0, otherwise asj = 1. Similarly, equalities (1b are equivalent to
dij < Vij.
V(i,j) E S,
(19a)
dœ < 8 Yij
v(i,)) E S,
(19b)
dæ 2 Y4j 8 8.mij:
V(i,) E S,
(19c)
d 2 8 Vij - 8 (1- miy),
V(i,)) E S,
(19d)
where my E {0, 11. (i.j) E S are auxiliary variables, with my
0 when Vyj S 8 ytj.
The not-equal constraints 17c can be linearized by
dj 2 du + 1 8 tijke:
Vi,j,k, K, Vi.j,k, () E K,
(20a)
du 2 dij -- tazke);
(20b)
where K 21,,2,1,3), (1, (0. 1), V(i, ki E K, we have dj 2 d&e + if tizke = otherwise dig I des - 1, i.e.,
By introducing auxiliary variables tizkt
de dRe.
Assume {x) = 31, 222 32, 23 = 33} is a feasible solution of this problem and let [+]r denote the mod- T operation, then it's easy to verify that {#; [T; + b]s b (rotation) and its reverse {rr = [[8 ).) + b V E Z (reflection It is more intuitive to see the illustration in F rotation and reflection acting the ticks do not change their corresponding distances.
rotation) are both equivalent feasible solutions.
When representing 3 T2, by binary variables Zip (0. E
1,, 1,2,3, E (1,...,8).
8):
p Zips
Wi (1,2,3),
(21a)
8
Zip
1,
Vi E (1,2,3)
(21b)
14

---

the modulo symmetry leads to a dihedral group D3 along the dimension of Zip. Specifically, let Z be a feasible solution with its (i. p)thh entry as the value of Zip. then any permutation Dg acting on the columns of Z yields another equivalent solution (I)( (i)
1
8
2
rotation
reflection
7
3
7
3
6
6
5
Figure 6: Equivalent solutions of Example B.0.2
C Bipartite graph representation for MILP
Gasse et al. (2019) proposed to represent a MILP (also works for ILP) by bipartite graph G (V. C, E) with two disjoint sets nodes, V {oi, .op.......... and C {ci. c,.... Cm denoting the decision variables and constraints in Problem [ respectively. And E = {Aju|Aşa + 0, C, u E } is the set of weighted edges connecting variable nodes and constraint nodes, where A is the coefficient matrix in Problem (T) Each node has feature vector Vk or e, describing the information of the variables or constraints. For example, in our experiments, these features include variable types (continuous or binary), variable positions, lower and upper bounds, right- hand side coefficients, constraint types (=, S. 2), etc.
D Graph convolutional neural network
In the graph convolutional neural network (GCNN)-based approach proposed by Gasse et al. (2019), a bipartite graph = (V, C, E') (with node features of = Cj. 1t Uk. and edge features Azx) is taken the input. Stacked layers are applied to aggregate information from neighbors and update node embeddings. Each layer has two consecutive half convolutions computed as
o0= f(()
|1 1)
Σ
(0 (1-1) 1.).AAj)) ,
80th (c"-",
(22)
j.AAEE
0k
(
(1)
(1-1)
Σ K(G.EEE
(1-1) Io !)) (0) (1-1) Axe) A
(23)
where E (0.-.... L} denotes the layer index, f and ga are non non-linear transformations gathering information from variable nodes and update on constraint nodes, 1( and gi are on the contrary. All of these four transformations are two-layer perceptrons with ReLU activations. Lastly, another two- layer perceptron fout with sigmoid activation is used to convert the final embeddings to the predictions of integer variables by i Sigmoid( (fur (v(()) ()))). We denote fo as the GNN parameterized by and the output vector for the discrete part as I = fo(G) in the remaining sections.
E Detailed experimental settings
E.1
Hyper-parameter tuning
The experiments involved three downstream tasks: fix&oottmizee, local branching, and node selection. For the first two, we utilized grid search for hyperparameter tuning. In fix&optimize, we adjusted a, the fraction of variables to fix, exploring values from 1 to 0.9. For local branching, we varied (3, the percentage variables in the local branching constraint, within the same range. For node selection, adhered to default settings stated in Khalil et al. (022). In Table E. we report the optimal
15

---

hyperparameters for each task and dataset, ensuring clarity and aiding in the reproducibility of our work.
Table Hyper- Hyper-parameetrs for different down- stremmt tasks
Dataset
Ta
O
B
0.1
0.2
0.1
0.1
SMSP
0.5
0.5
0.5
0.6
PESP
0.1
0.1
0.3
0.4
PESPD
0.1
0.1
0.3
0.2
E.2 Computational resources and software
All evaluations performed under the same configuration. The evaluation machine has one AMD EPYC 7HI2 64-Core Processor @ 2.60GHz, 256GB RAM, and one NVIDIA GeForce RTX 3080. CPLEX 22.2.0 and PyTorch 2.0.1 (Paszke al.) (019) utilized in experiments. The time limit for running each experiment is set to 800 seconds since a tail-off solution qualities was often observed after that.
F
Other supplements
F.1
Dataset details
Table 5: More information about benchmark problems include average number of variables ("bin." for bianry while "int." for integer) and constraints, well as symmetry groups.
problem
# of Var.
of Cons.
symmetry
IP SMSP
208 ~ 1050 bin.
46 ~ 196
S1 ~ S10
22k 24k bin.
20k 22k
S111
PESP
5k ~ 15k int.
7k ~ 21k
Cs ~ C15
PESPD
5k 15k int.
10k 30k
D5 D15
F22 p-values for the significance of improvement
We use the paired-sample T-test in MATLAB and report p p-values in the following table. p-value less than 0.05 means the mean difference (improvement) is significant. It shows that our proposed framework effective in finding a better solution.
Table 6: p-values of paired-sample T-tests for the difference of means of the relative primal gaps
p-value
Fix and Optimize
Local Branching
Node Selection
IP
0.0012352
0.0007626 0.0007752
0.0044869 0.0000026
SMSP
0.0000441
PESP
0.0589491
0,0585871
0.0012326
PESPD
0.0000002
0.0000054
0.0088221
G Problem formulation and their corresponding symmetry group
G.1 IP
There are items, J bins, and K resource types. Each item has fixed resource requirement as for each resource type k. Each bin j has fixed capacity by for each resource type kt The goal is to
16

---

place all items in bins, while minimizing the imbalance of the resources used across all bins. This problem has formulation follows:
min 2,y6
ΣΣ JEJ KEK
Ondlik +
Σ
Bkzk
KEK
s.t.
Σ Tij =1
ViEl
(24a)
JEJ
Σ dik-iij S bk
VjEJ
(24b)
VEl
Σ VEI
dussi Mikk 2
VjEK,
(24c)
Vik I 2
(24d)
Zi E {0,
VELLjEJ
(24c)
Yık 20
Vj J.KE
(24f)
where miy denotes assigning item i bin j. di is normalized resource requirement for each item, Výk and 24 are implicit decision variables to track the imbalance of the resources. Since each bin in this problem identical (i.e., with the same capacity), reordering bins would not change feasible solution's feasibility and objective value. This problem naturally has symmetric group lrl w.r.t. the ordering of bins J. Specifically, let X {0, 13 /|x|J| be a feasible solution of an IP instance with its (i.j)-th entry as the value of variable Tay- Then arbitrary permutation ı E Srjl acting on its columns (X.j, Vj E J} yields an equivalent solution [X.=(1)= (2)))):-... ... X.x]
G.2 SMSP
Given order set O and slab set S. Color set C, and slab weights Q = ( 0, W1, W2, ... uk uo denotes unused slab. The ILP formulation of SMSP used in our experiments is from (Gargani &
Refalo 2007) as
Σ q x
min 2.8.3
ygs
SES
s.t.
Fos
vs S,
(25a)
oEO
Σ Bge 1
As S.
(25b)
GEQ
Σ WooJos
Σ
q yqs
E S
(25c)
6EO
NEQ
Dos
< Z0g8
Vo N0E0,SE S,
(25d)
Σ Jes S 2
E S,
(25e)
SEC
Tos: Bo8s Zes E (0.1}
Yo E 0, S.E.,EEECCCC
(25f)
G.3 PESP
Periodic event scheduling problem involves determining optimal schedules for a of events that occur repeatedly over fixed period, such as bus or train departures. Consider a set of events 3. For each event i E & we would like to schedule a time I; E (1,.... T 1}. where length. Besides, a set of activities A C E x È connect events with each other. Each activity a E A has lower bound la E N, an upper bound u, E N, and a weight w,. The goal is to minimize the weighted sum of the slack ya of all activities, while ensuring all activity slacks are within [0, u, fa].
the periodic
17

---

It can be formulated as:
min
Σ walaa + Ea)
oEA
8.1. Vo = [1 - 11]l
Aa = (1,5) E A, Va A, ViEE
(26a)
0 < Ya Uh la
(26b)
4 E ,0,..., --
(26c)
where [|r denotes the modulo operation, which enforces the periodic nature. is modeled as [t - t/rr & 1j 1; + za by introducing additional implicit variables { E NJ. Due to the existence of modulo operation, [0..... -
regard {t,, Vi {} as frames in clock with intervals T 1]. all t; rotate the same angles simultaneously, then the activity slacks Ya remain
145 unchanged. In experimentation, we substitute by t, E. 1) Fit and Σx 2zk 1, where
Ji {0. 1), E & k E {1, Let X {0, 111 denotes feasible solution with its (i, k--th entry as the value of variable zik. then this problem has cyclic group OT w.r.t. the column indices of X, i.e. any permutation и E Cr acting on the columns of yields equivalent feasible solution (.(())
G.3.1 Data generation by perturbation
As mentioned above, PESP instance has a set of events & and set of activities S & x connecting events with each other. Each activity has weight Wg. The goal is to assign an appropriate time t2 to each event by [Way E AJ. These weights heavily impact the time assignment. We perturb these weights to generate new instances by introducing Gaussian noises, i.e., w Wa nas where nl N
meet some constraints while minimizing the total time slack weighted
Waa = 0.1 W.).
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer to Abstract and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
See Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer Section and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer: [Yes]
Justification:
We provide a code link in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.com cc/p
blic/ httgg/gddd//osuuuunna
wwriiisssiiiiiiinii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
wwwpc//ggus////eee CoodeSubeiiieeee ssi onoolicyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section 3
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the p-values in Appendix F2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
21

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See Appendix E.2.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httt:p/://aurrrssscc///bbbb//eat
Answer: [Yes]
Justification: The research presented in this paper adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not present any such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Please refer Section
5
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, haperswithcoda com datasstss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: See the code link in Section
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "lTDffDRd6q", "reviewer": "Reviewer_7rcN", "summary": "The paper provides an ML-based framework, SymLo, for solving MILPs that leverages symmetries of ILPs to improve ML performance. SymLo takes into account symmetric groups on the solutions and formulates a learning task with respect to the model parameters and the permutations that belong to the symmetric group of each instance. The loss is challenging to minimize, and an alternating algorithm is proposed to mitigate the issues. In experiments, the method is evaluated on three different tasks and on four benchmarks.", "questions": "I don't have specific questions.", "limitations": "The authors talk about some limitations of the work, but not all that are known.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed formulation and method for symmetry-aware learning for ILPs is novel.\n\n2. Empirical results are promising, suggesting its usefulness for instances that have symmetric properties in the solutions. It is also applicable to different ILP learning tasks.\n\n3. The paper is engaging and well-written.", "weaknesses": "This is the second time I have reviewed this paper. I am satisfied with the authors in addressing my previous comments.\n\nNonetheless, I still believe that evaluating the method on a third task would make the contribution of this work more solid and convincing.  The fix&optimize task and the local branching task are similar to each other. I am not surprised to see that it works on one if it already has worked for the other. Some tasks that you could consider: Initial Basis Selection [1][2], Backdoor variable predictions [3]\n\n[1] Fan, Zhenan, et al. \"Smart initial basis selection for linear programs.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Zhang, Yahong, et al. \"MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness.\" Forty-first International Conference on Machine Learning.\n\n[3] Ferber, Aaron, et al. \"Learning pseudo-backdoors for mixed integer programs.\" International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Cham: Springer International Publishing, 2022.\n\n2. The limitation of generalizing the method to larger instances was discussed with the other reviewers last time. It would be important to include such a discussion in the main paper to provide a more comprehensive understanding of the method's pros and cons.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "___Weakness 1: evaluating the method on an additional task___\n\nThank you very much for listing potential tasks that we can consider in our experiments. Regarding the relevance, we have cited them in our revised manuscript. \n\nWe agree that evaluating on a third task could improve our work's contribution, and we are now conducting experiments on some potential methods. Since the training and evaluation do require a certain time, we are not sure whether complete results could be obtained within the rebuttal period. If done, we will submit a follow-up comment to present these results.\n\n\n\n___Weakness 2: generalization to larger instances___\n\nThank you again for your valuable comments. We will add such a discussion in our main paper. Similar to Weakness 1, we are now conducting experiments on larger instances and will report corresponding results once finished.", "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": "FIy9goYR8w", "reviewer": "Reviewer_HH73", "summary": "This paper aims to enhance solution prediction methods for ILPs that contain certain types of symmetry. The main methodological contribution of the paper is a loss function that considers symmetry, along with an optimization algorithm for it. In particular, the loss function applies a permutation to each optimal solution label, and these permutations are learned along with the solution predictor. This is done via an alternating algorithm that alternates between optimizing (graph) neural network weights with a classical loss function and optimizing this permutation. For symmetric groups where any permutation is allowed, the authors show that the latter problem can be efficiently solved via LP. This method is then combined with three downstream methods that use a solution predictor and tested on four sets of problems with symmetry, showing consistent improvements in obtaining better solutions in all cases.", "questions": "1. It would be helpful for the reader to know earlier in the Introduction that the predicted optimal solution will be coupled with downstreams approaches rather than used directly. Options are to mention this in the introduction, or alternatively move Figure 2 (which is very helpful) near the introduction, as it easier to go through the paper with the big picture in your head. If you do opt to move Figure 2 earlier, consider adding some context in the caption since the reader does not have much context at that point.\n\n2. Please add a description of the problems in the Appendix, preferrably (but not necessarily) with the MILP formulation used, and point out where the symmetry comes from. In addition, indicate how the perturbation for PESPlib was done.\n\n3. I tried to check the anonymous code repository, but it was expired.\n\n4. Could you add standard deviations / errors to Table 2?\n\n5. The Appendix says that the evaluation machine has a GPU, but I cannot clearly find if the training time reported in Table 2 is for GPUs. The reason why this matters is that this paper shows that the LP is not a bottleneck, but the picture might be different if Table 2 were CPU times. In particular, I am assuming that the $r_s$ time includes: GPU training time + CPU LP solves + communication overhead between GPU and CPU. Could you clarify this in the paper?\n\n6. The paper does not describe what is \"Tuned CPLEX\". In particular, an important question is, do you tune the symmetry breaking parameters in CPLEX? If you do not, would be able to include it in the paper? Please also mention in the paper how the tuning is done overall, and you might as well mention that CPLEX contains its own symmetry handling methods based on classical approaches. Another important set of parameters to tune are primal focus (e.g. heuristics), but I assume that is already included in your tuning.\n\n7. Typos: Line 269: Is $\\hat{x}$ supposed to be $\\hat{y}$? Line 420 has a typo: \"don not\".", "limitations": "The paper properly indicates the main limitations of this work in Section 7.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This method overall is a solid and clean approach to incorporate symmetry information in solution prediction methods in ILP. While the alternating algorithm seems quite natural in retrospect, it is a suitable approach particularly with the nice observation that optimizing the permutation for the symmetric group case can be done efficiently via LP. It is also not too complicated to implement. If one is solving a problem with known symmetry via a solution prediction approach, I see little drawback to using this method. The experimental setup is sound and sufficiently extensive, covering four sets of instances and three different methods to integrate this with. Even before reading the computational section, I could see that some computational improvement was expected since it allows the neural network model to not worry about permuted optimal solutions, and the computational section does confirm that with substantial improvements across the board. The paper is overall clear and easy to follow.", "weaknesses": "I do not see any major weaknesses in this paper. Perhaps a concern in terms of relevance is that work does apply to a rather narrow class of instances (those with the types of symmetry in the paper) and it also requires prior knowledge of which type of symmetry the problem has. However, this does include a number of important problems in discrete optimization, so I do not view this as a significant issue. Other than that, there are a few parts of the experimental setup that need to be clarified as discussed below, but they can be easily fixed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and valuable comments. We address each question below.\n\n___Question 1: suggestion of presenting downstream approaches earlier___\n\nWe appreciate your valuable suggestion and already added a short paragraph in the Introduction to explain the downstream part. Meanwhile, Figure 2 is moved to the earlier page adding the necessary explanation in the caption.\n\nHere is the added description: Due to the difficulty of satisfying complicated constraints in ILPs, existing methods are usually equipped with a post-processing module to identify high-quality solutions based on the initial solution predicted by GNNs. A number of methods utilize ILP solvers in the post-processing module. The initial prediction from GNNs is taken as guidance for the ILP solver to solve the target ILP. We call these post-processings as downstream approaches according to how they utilize the prediction as guidance. In our method, we follow their routines and incorporate some downstream approaches.\n\n\n___Question 2.1: Detailed information for used MILP and symmetry___\n\nThanks for your valuable suggestion, we have added detailed descriptions of all benchmark problems with their formulations, as well as symmetry groups corresponding to their decision variables. An example is shown in part III of the global author rebuttal. Please refer to it.\n\n___Question 2.2: indicate how the perturbation for PESPlib was done.___\n\nProblems in PESPlib involve determining optimal schedules for a set of events that occur repeatedly over a fixed period, such as departures of trains and buses. Each problem has a set of events $\\mathcal{E}$ and a set of activities $\\mathcal{A} \\subseteq \\mathcal{E} \\times \\mathcal{E}$ connecting events with each other. Each activity has a weight $w_a$. The goal is to assign an appropriate time $t_i$ to each event $i\\in \\mathcal{E}$ to meet some certain constraints while minimizing the total time slack weighted by $\\{w_a, a\\in \\mathcal{A}\\}$. These weights heavily impact the time assignment. We perturb these weights by introducing Gaussian noises, i.e., $w_a' = w_a + n_a$, where $n_a \\sim \\mathcal{N}(\\mu=w_a, \\sigma=0.1*w_a)$.\n\n___Question 3: I tried to check the anonymous code repository, but it was expired.___\n\nThanks for catching this. We have fixed this issue.\n\n___Question 4: Could you add standard deviations/errors to Table 2___\n\nYes, the results with standard deviations are shown in the brackets as follows:\n\n| Dataset |   |CPLEX|   || Fix&optimize |||| Local Branching |||| Node Selection |||\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|||||ND|SymILP|gain ||PS|SymILO|  gain |   |MIP-GNN|SymILO|  gain ||\n|IP||0.188(0.15) ||  0.201(0.18) |  0.124(0.10) | 38.4% ||  0.168(0.15) |   0.102(0.09)  | 39.4% |   |0.312(0.30) |   0.190(0.16)  | 39.2% |   |\n|SMSP|| 0.190(0.001) || 0.300(0.002) | 0.180(0.001)| 40.0% || 0.230(0.001) |0.160(0.001)| 30.4% || 1.180(0.004) |0.740(0.004)| 37.3% ||\n|PESP  ||  0.056(0.08) ||0.084(0.14) |0.050(0.06) | 39.8% ||  0.306(0.63) |0.000(0.00)|100% ||  1.899(1.41) |0.280(0.49)  | 85.3% ||\n|  PESPD  ||  3.194(1.94) ||  2.389(1.28) |  0.404(0.31) | 83.1% ||  3.442(2.09) |   0.127(0.14)  | 96.3% ||  3.755(1.88) |3.006(1.65)  |  20%  |   |\n\nNote that the standard deviations among datasets IP, PESP, and PESPD are relatively large because: \n- the reported primal gaps are averaged across instances, while different instances may have very distinct objective values.\n- these three datasets include instances with very different sizes, please refer to Appendix F.1 for more details.\n\n\n___Question 5: GPU and CPU time___\n\nWe are sorry for the confusion, here we add more explanation for Table 2.\n- The time costs reported in lines $r$ and $r_s$ are training time averaged over iterations (update steps). Those in line $r$ are \"GPU training time\", while those in line $r_s$ are \"GPU training time + CPU LP solves + communication overhead between GPU and CPU\".\n- The time cost reported in line $t$ is the time of solving LP averaged over instances, they are pure CPU time for LP solving.\n- The batch size is set to $B = 16$, so in each iteration, the number of LPs is 16.\n- Approximately, $t*B$ (CPU time) + $r$ (GPU time) $\\approx$ $r_s$ (CPU+GPU+communication time). Take the column of \"IP\" as an example, 5.54 + 0.029 * 16 = 6.004 $\\approx$ 6.01. The communication time cost is quite small.\n\n___Question 6.1: Are symmetry-related parameters of CPLEX tuned in experiments?___\n\nYes, we tuned two CPLEX hyper-parameters: \"emphasis switch\" (which balances speed, feasibility, optimality, and moving bounds, etc.) and \"symmetry breaking\" (the level of symmetry-breaking)\n\n\n___Question 6.2: How CPLEX is tuned.___\n\nThe tuning is conducted through a grid search strategy on the validation set for each dataset. We selected the set of hyper-parameters that produced the best average primal gap within a time limit of 800 seconds. These hyper-parameters are then used for evaluation on the test set. Different datasets can have distinct sets of tuned hyper-parameters.\n\nIndeed, as pointed out by [1], commercial solvers such as CPLEX have their own symmetry-handling methods including orbital fixing.\n\n\n___Question 6.3: Primal focus___\n\nThe setting of the primal focus is included in the \"emphasis switch\" hyper-parameter, which was considered in our experiments. It has 6 choices: balanced, feasibility, optimality, bestbound, hiddenfeas, and heuristic. The \"heuristic\" option emphasizes finding high-quality feasible solutions earlier.\n\n\n\n___Question 7: Typos: Line 269: Is $\\hat{x}$ supposed to be $\\hat{y}$? Line 420 has a typo: \"don not\".___\n\nYes, thank you for the correction, we have fixed them in the revised manuscript. \n\n\n[1] Pfetsch, M.E. and Rehn, T., 2019. A computational comparison of symmetry handling methods for mixed integer programs. Mathematical Programming Computation, 11, pp.37-93.", "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": "r2Klz8sj3I", "reviewer": "Reviewer_cWBm", "summary": "The article examines the problem of predicting solutions to MILPs with a large number of symmetric solutions. An integer linear program (ILP) is symmetric if its variables can be permuted without changing the structure of the problem. The authors propose a new formulation of supervised learning for problems with symmetry. It includes choosing the optimal permutation of the target solution in the training set. The authors provide a new algorithm that updates learning parameters and permutations alternately. The proposed paradigm can be applied to complement existing methods in which the output of the model is the prediction of the solution. Experiments are conducted together with SL methods for node selection, local branching, and Neural Diving.", "questions": "1.\tIn the vast majority of real cases, a symmetry group G is not known, we know only one of its subgroups. It would be interesting to compare the effect of adding a search for an optimal permutation over a symmetry group, with the same search over some subgroup.\n\n2.\tHow to check the symmetry of the new problems for real-world scenarios, if one wants to apply the proposed symmetry-aware framework? Does it work for non-symmetry problems? Prop 4.1 holds only for the known symmetry group.\n\n3.\tShould one apply the algorithm for symmetric problems where the number and the size of similar solutions is unknown?\n\n4.\thow to compute \\pi^' in line 267? Is argmin_\\pi a trivial problem?\n\n5.\tRefer to weaknesses", "limitations": "The authors point to the potential slowdown on a large instance as a limitation. However, authors do not provide deeper analysis of it.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe motivational part is well explained, and examples of symmetry are provided to understand this problem. The theoretical preliminaries provide the reader with the necessary information to understand the symmetry group, permutation classes, etc.\n\n2.\tThe framework is theoretical and general, since it reformulates the supervised learning objective. Hence, it is applicable to any SL-based task, where the target is a solution for combinatorial optimization problem. It also contains proofs that symmetry-aware risk is theoretically preferable, if there exist permutations of instance’s optimal solutions.\n\n3.\tThe experimental design is solid, since the proposed method is combined with three popular deep learning-based frameworks (Neural diving, Node selection with GNNs, Predict-and-search) and for each of them shows a significant increase in quality when solving problems with a large number of symmetric solutions.", "weaknesses": "1.\tThere exist classical approaches (Dantzig-Wolfe decomposition, orbital branching, and etc) that are applied to tackle the symmetry in MILPs. So, the discussion if some of them can be theoretically utilized together with the proposed framework, or some comparison (for example ND + symILO vs ND + some classical method for symmetric problems) would benefit the paper.\n\n2.\tI would also suggest testing performance on other problems (probably with less symmetry) and comparing the computational time. This would trigger a discussion about whether the proposed structure should be applied if the degree of symmetry is unknown.\n\n3.\tIn limitations, the authors say that the sub-problems involved in optimizing permutations can significantly slow down the training process for large-scale problems. An analysis of how significant it will be is needed, as well as an analysis of the convergence and scalability of the alternating minimization algorithm (4.2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and valuable comments. We address each weakness and question below.\n\n__W1: Applying classical approaches.__\n\nThank you for raising the insightful comments. Below is our clarification. \n\nOur framework includes two parts.\n- a learning part: a GNN model that predicts an initial solution. \n- a post-processing part: different downstream approaches can be equipped in this part to identify high-quality solutions based on the initial solution.\n\nWe argue that 1) classical symmetry-handling methods can not be directly applied in the *learning part*.\n- Symmetry-handling techniques such as orbital branching are often applied during the branch-and-bound process, while Dantzig-Wolfe decomposition reformulates problems for tighter relaxations. Both approaches are beyond the scope of the learning framework.\n- For future research, it is interesting to learn ideas from classical symmetry-handling methods and design appropriate learning algorithms.\n\n2) Most downstream approaches already utilized classic symmetry-handling methods.\n- All downstream approaches considered in our work have the aid of ILP solvers. For example, \"fix&optimize\" fixes variables based on GNN's predictions, and solves sub-ILPs via an ILP solver.  \n- ILP solvers, such as CPLEX, have integrated symmetry-handling methods (e.g., orbital branching/fixing). Besides, parameters are tuned to properly handle symmetry. Please refer to our response to Question 6 of Reviewer HH73.\n\n__W2: Testing on other problems.__\n\nThank you for the valuable comment.\n\nWe extend our experiments with two additional datasets with less symmetry. One is \"Workload Appointment\" (WA) from [1], and the other is from \"assign\" problems in MIPLIB 2017 (AP). We report the averaged **primal gaps** for each algorithm, alongside with LP solving time and the degree of symmetry.\n\n|Dataset||Tuned CPLEX||PS||SymILO|LP time|| $\\text{log}\\|G\\|$|gain($\\uparrow$)|\n|-|-|-|-|-|-|-|-|-|-|-|\n|WA||0.08||0.02||**0.02**|0.000||0|0.00%|\n|AP||0.72||0.41||**0.34**|0.011||4.54|17.0%|\n|IP||1.14||0.97||**0.58**|0.029||15.1|39.4%|\n\nFrom the above table, we have some observations:\n- Problems with more symmetry can benefit more when using SymILO.\n- Our method can also be applied to no-symmetry problems (WA), and has a comparable performance to the baseline PS.\n- Although more symmetry requires longer LP solving time, it is not a bottleneck on the considered datasets.\n\nIf the symmetry is unknown, we need some well-developed tools such as Nauty [2] and Bliss [3] to detect it. Otherwise, our method would turn into a \"symmetry-agnostic\" one, and would not bring improvements compared to classic ones.\n\n__W3: Scalability analysis.__\n\n1. complexity of the sub-problems over the symmetry group\n\n    1.1. The complexity of different symmetry groups.\n    - cyclic group $C_q$ and dihedral group $D_q$:  $O(q)$.\n    - symmetric group $S_q$: $O(q^2\\text{log}q)$ (a linear assignment problem).\n    \n    1.2. Our claim in the limitation part comes from $O(q^2\\text{log}q)$ for the symmetric group. The training process can be slower when solving larger sub-problems.\n\n2. analysis of the convergence and scalability of the alternating minimization algorithm\n    \n    2.1. convergence\n    \n    - Empirically, the alternating algorithm could converge in our experiments (as shown in Figure 3 in the manuscript). \n    - Theoretically, existing convergence conclusions can not be directly applied due to the discrete nature of sub-problems over symmetry groups.\n    \n    2.2. scalability\n\n    - Compatibility to variable sizes: benefiting from the message-passing mechanism of GNNs, our alternating algorithm can be applied to ILPs with different sizes.\n    - Computational complexity: as mentioned before, the complexity of our algorithm depends on the sub-problems over the symmetry group. In our experiments, it is more scalable when handling cyclic and dihedral groups $O(q)$ than the symmetric group $O(q^2\\text{log}q)$.  \n\n__Q1: Search over a subgroup of symmetry.__\n\nYes, getting the full symmetry group of an ILP is rather difficult, and the symmetry groups considered in our implementations are actually already subgroups of the full one.\n\nHowever, it is still interesting to investigate the effects of considering subgroups with different sizes. We are now conducting some experiments on it and will submit another comment box to report these results once finished.\n\n__Q2: Symmetry related.__\n\n1. How to check symmetry\n    - Symmetry groups of ILPs can be efficiently detected by well-developed tools, such as Nauty [2] and Bliss [3].\n\n2. Non-symmetry problems?\n    - Yes, our method works for non-symmetry problems, as it turns into a \"symmetry-agnostic\" method trained via classical supervised learning. An example (WA) is given in the response to Weakness 2.\n\n__Q3: Should one apply the algorithm for symmetric problems where the number and the size of similar solutions are unknown?__\n\nAs mentioned in Question 2, if the symmetries of the ILP problems are unknown, we should identify them first. Otherwise, our method can not utilize the symmetry information and would turn into a \"symmetry-agnostic\" one.\n\n__Q4: sub-problems over symemtry groups__\n\nThe optimization over symmetry groups requires customization, i.e., we need to design appropriate ways to optimize a specific symmetry group. \n- For cyclic and dihedral groups, it is trivial, since there are only $q$ and $2q$ ($q<n$) possible permutations, respectively.\n- We designed a specific sub-problem to get the optimal permutation from the symmetric group's $q!$ possible permutations. We supplemented a detailed example in Part III of the global author rebuttal, please refer to it.\n\n[1] Gasse, Maxime, et al. \"The machine learning for combinatorial optimization competition (ml4co): Results and insights.\"\n\n[2] McKay B D. Nauty user’s guide (version 2.4). \n\n[3] Junttila T, Kaski P. Conflict propagation and component recursion for canonical labeling", "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": "UdKsu0qm90", "reviewer": "Reviewer_nCep", "summary": "This paper proposes the SymILO framework for solving combinatorial optimization problems (using machine learning). Building on traditional supervised learning, this method leverages the inherent symmetry structure of the problem to guide the model in learning the true patterns. The author also show its performance on several datasets.", "questions": "1. Although the idea is good, the permutation group, which plays a crucial role, is only vaguely explained in the paper. In most typical combinatorial optimization problems, the permutation group is subtle and may even vary with the instance. In the main body of the paper (Section 4), the authors' direct use of $ G_i $ is confusing. \n2. Following up on the previous point, the authors should explain how to identify the appropriate permutation group for a new problem and clarify whether selecting a specific permutation group significantly impacts the computational complexity during the optimization process.\n3. Where in the paper are the details on \"passing the outputs to an off-the-shelf solver\" provided?\n4. I expect the authors to explicitly formulate the problem as a MIP problem in the examples provided in Section B and specify the permutation group.", "limitations": "See questions", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea of considering symmetry is interesting and crucial, especially when using the optimal solutions as labels. Since the solution space could be symmetry-invariant, using one particular solution as a label may cause the model to fail in learning the intrinsic pattern.\n2. The presentation is neat.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments. We apologize for any misunderstanding caused by our presentation and will address your questions below. **Please note the top-most \"author rebuttal\", a brief summary, and part of the response is put there**. \n\n___Question 1: ... the permutation group ,..., is only vaguely explained in the paper. In most typical combinatorial optimization problems, the permutation group is subtle and may even vary with the instance. In the main body of the paper (Section 4), the authors' direct use of $G_i$ is confusing.___\n\n\n_**Question 1.1:** ... the permutation group ,..., is only vaguely explained..._\n\nSome notions related to the symmetry group are additionally clarified in **part I of the global rebuttal**. Besides, concrete symmetry groups and the optimization over them for benchmark problems are specified in **part III of the global rebuttal**. Please refer to them accordingly.\n\n\n_**Question 1.2:** In most ... problems, the permutation group is subtle and may even vary with the instance. In the main body of the paper (Section 4), the authors' direct use of $G_i$ is confusing_\n\nWe agree that \"the permutation group is subtle and may even vary with the instance\". That's also why we focus on ILP problems with specific symmetry types, instead of general ILPs. \nInstances in the same dataset share the same type of symmetry group, while the group size may vary with their instance sizes. For example, in the IP dataset, instances $\\\\{s_1,\\dots,s_N\\\\}$ have bin numbers $\\\\{b_1,\\dots,b_N\\\\}$, then their corresponding symmetry groups $G_i=S_{b_i},\\forall i=\\\\{1,\\dots,N\\\\}$.\n\n\n___Question 2: ..., the authors should explain how to identify the appropriate permutation group for a new problem and clarify whether selecting a specific permutation group significantly impacts the computational complexity during the optimization process.___\n\n\n_**Question 2.1**: on the identification of the symmetry group_\n\nAccording to the problems considered, the situations for symmetry identification are different:\n- Case I: For a general ILP, its symmetry group can be efficiently detected by well-developed tools, such as Nauty[1], Bliss[2], etc.\n- Case II: For specific types of problems, such as bin packing, periodic scheduling, and job scheduling, the symmetry groups are already well-known by area experts [3].\n\nThe problems considered in our experiments belong to Case II, thus the corresponding symmetry group is known. Although only three types of symmetry in Case II are considered, just as Reviewer HH73 commented, \"this does include a number of important problems\". \nBesides, **we remark that our framework is also applicable to Case I if the corresponding subproblems have appropriate customization and be solved**.\n\n\n_**Question 2.2**: whether selecting a specific permutation group significantly impacts the computational complexity during the optimization process._\n\n\nWe do not fully understand the meaning of \"selecting a specific perumtation group\". In our work, the symmetry group of an ILP is its intrinsic property and should be known before trainning, hence it's not selectable. Could the reviewer clarify this a bit more?\n\nThe computational complexity of the sub-problem over the symmetry group depends on its symmetry types. For the three symmetry types considered in our paper, the corresponding complexities are $O(q)$ for both a cyclic group $C_q$ and a dihedral group $D_q$, and $O(q^2log^q)$ for a symmetric group $S_q$, respectively. Here, $q$ is a number related to the sizes of the specific symmetry group.\nFor other symmetry groups that are not considered in our paper, it depends on how the sub-problem over symmetry groups is customized.\n\n\n\n___Question 3: Where in the paper are the details on \"passing the outputs to an off-the-shelf solver\" provided?___\n\nIn the main paper, there is no \"passing the outputs to an off-the-shelf solver\". Does the reviewer mean \"It can be done quite efficiently with the aid of off-the-shelf LP solvers, such as Gurobi Optimization, LLC (2023), CPLEX IBM (2020), etc.\" at line 175? \nSince the optimization over symmetric groups is equivalent to solving a Linear Program (LP) (see Proposition 4.2), we directly leave the job to an LP solver such as CPLEX and Gurobi. Given an LP, it can efficiently identify its optimal solution.\n\n\n___Question 4: I expect the authors to explicitly formulate the problem as a MIP problem in the examples provided in Section B and specify the permutation group.___\n\nThe formulation and symmetry group of Example B.0.1 has been specified in **part III of the global author rebuttal**. Due to the limited space, we put the specification of Example B.0.2. to another comment box, please refer to it. \n\n\n--- \n\n[1] McKay B D. Nauty user’s guide (version 2.4)[J]. Computer Science Dept., Australian National University, 2007: 225-239\n\n[2] Junttila T, Kaski P. Conflict propagation and component recursion for canonical labeling[C]//International Conference on Theory and Practice of Algorithms in (Computer) Systems. \n\n[3] Margot F. Symmetry in integer linear programming[J]. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, 2009: 647-686.", "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:
Thanks all reviewers for their detailed review and valuable comments. In the global rebuttal, we would like to supplement some common clarifications.

___Part I. Clarifications on some notions___

---
**1. Permutation :** A permutation is a bijective mapping from a set $I^q=\\{1,\\dots,q\\}$ onto iteself, e.g., an identity permutation on $I^3$ is (1&rarr;1,2&rarr;2, 3&rarr;3) and a reverse permutation is (1&rarr;3,2&rarr;2, 3&rarr;1). For simplicity, **we omit the ordered and identity preimage part in the following text**, e.g., (1,2,3) and (3,2,1) denote the identity and reverse permutations, respectively. A permutation $\\pi$ acts on a vector $x=[x_1,\\dots,x_q]^\\top$ by rearranging its elements, i.e., $\\pi(x)=[x_{\\pi(1)},\\dots,x_{\\pi(q)}]^\\top$

**2. Permutation group :** A permutation group $G$ is a group [1] whose (i) **elements** are permutations, (ii) and group **operation** $\\circ$ is _combination_, i.e. $a\\circ b=a(b),\\forall a,b\\in G$. 

**3. Symmetric group, cyclic group, and dihedral group:** These three groups are typical permutation groups [1]. Below we list examples for each one on set $I^3$.
- Symmetric group: $S_3=\\{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\\}$ (**all permutations**)
- Cyclic group: $C_3=\\{(1,2,3),(3,1,2),(2,3,1)\\}$ (**rotation**)
- Dihedral group: $D_3=C_3\\cup\\{(3,2,1),(2,1,3),(1,3,2)\\}$ (**rotation + reflection**)

**4. Symmetry group:** A symmetry group is a permutation group associated with specific ILPs. It is used to express an ILP's intrinsic symmetry. For any feasible solution $x$, each permutation in this group can map $x$ to another feasible solution with the same objective.

[1] Grayland A. Automated static symmetry breaking in constraint satisfaction problems[D]. 

___Part II. Recall and outline the steps of our method___

---
1. Get a dataset $\\{(s_i,x_i,G_i)\\}_{i=1}^N$ with $N$ samples.
   > - $s_i$ : $i$-th ILP instance
   > - $x_i$ : a feasible solution of $s_i$
   > - $G_i$ : a symmetry group of $s_i$.
2. Training a NN model $f_\\theta$ by $\\arg\\min_{\\theta \\in \\Theta, \\pi_i \\in G_i} \\frac{1}{N}\\sum_{i=1}^N\\ell (f_\\theta(s_i),\\pi_i(x_i))$.
   > - $\\pi_i$ : a **decision variable** for $s_i$, i.e., a permutation to be selected from $G_i$.
   > - $\\ell$ : a loss function
   > - Decisions $\\theta$ and $\\pi_i$ are optimized in an alternating manner.

    2.1. Optimize $\\pi_i$ by solving a sub-problem $\\pi_i^{k+1}=\\arg\\min_{\\pi_i\\in G_i}\\frac{1}{N}\\sum_{i=1}^N\\ell(f_{\\theta^k}(s_i),\\pi_i(x_i))$
    >> - **this sub-problem needs customization for different symmetry groups.**
   >> - **Supplementary details are in part III**
    
    2.2. Optimize $\\theta$ by $\\theta^{k+1}=\\arg\\min_{\\theta\\in\\Theta}\\frac{1}{N}\\sum_{i=1}^N\\ell(f_\\theta(s_i),\\pi^{k+1}_i(x_i))$
    
   >> - A trained GNN model after $K$ iterations is $f_{\\theta^K}$.
3. Evaluation on a test instance $s_t$

    3.1. Predict an inital solution by $\hat{x}\_t = f\_{\theta^K}(s_t)$.

    3.2. Post-processing to identify high-quality solutions based on $\\hat{x}_t$


___Part III. Specification of the considered problems___

---
**1. Bin packing problem:**

**Description :** This is the toy example in Appendix B.0.1, it packs $I$ items into $J$ bins, aiming at a minimum number of used bins without exceeding the capacity.

**Formulation :**
\\begin{align}\\min_{x_{ij},y_j\\in\\{0,1\\}}~&y_1+y_2+y_3\\notag\\\\&a_1x_{1j}+a_2x_{2j}+a_3x_{3j}\\leq By_j,&\\forall j\\in J\\\\&x_{i1}+x_{i2}+x_{i3}=1,&\\forall i\\in I\\end{align}
where $y_j=1$ denotes $j$-th bin is used and $x_{ij}=1$ denotes $i$-th item is placed in $j$-th bin.

**Symmetry group :** All bins have the same capacity $B$, which leads to a symmetry of reordering them.

Specifically, let $X=\\begin{bmatrix}y_{1}&y_{2}&y_{3}\\\\
x_{11}&x_{12}&x_{13}\\\\x_{21}&x_{22}&x_{23}\\\\x_{31}&x_{32}&x_{33}\\end{bmatrix}$ be an optimal solution and $X_{:j}$ be its $j$-th column, one can easily check that $[X_{:1},X_{:3},X_{:2}],[X_{:2},X_{:1},X_{:3}],[X_{:2},X_{:3},X_{:1}],[X_{:3},X_{:1},X_{:2}],[X_{:3},X_{:2},X_{:1}]$ are all equivalent to $X$. Formally, it has a **symmetric group** w.r.t. bins $J$.

**2. Item placement (IP) problem:**

**Description :** Similar to bin packing, IP places $I$ items to $J$ bins with $K$ types of resouces. The difference lies in its goal of balancing packed resources on each bin.

**Formulation:**
\\begin{align}&\\underset{x,y,z}{\\text{min}}&&\\sum_{j\\in J}\\sum_{k\\in K}\\alpha_{k}y_{jk}+\\sum_{k\\in K}\\beta_k z_{k}\\notag\\\\&\\text{s.t.}&&\\sum_{j\\in J}x_{ij}=1&&&\\forall i\\in I\\\\&&&\\sum_{i\\in I }a_{ik}x_{ij}\\leq b_{k}&&&\\forall j\\in J,\\forall k\\in K\\\\&&&\\sum_{i\\in I}d_{ik}x_{ij}+y_{jk}\\geq 1&&&\\forall j\\in J,\\forall k\\in K\\\\&&& y_{jk}\\leq z_{k}&&&\\forall j\\in J,\\forall k\\in K\\\\&&& x_{ij}\\in\\left\\{0,1\\right\\}&&&\\forall i\\in I,\\forall j\\in J\\\\&&& y_{jk}\\geq 0&&& \\forall j\\in J,\\forall k\\in K\\end{align}

where $x_{ij}=1$ denotes assigning item $i$ to bin $j$, $a_{ik}$ and $d_{ik}$ are resource coefficients. Besides, $y_{jk}$ and $z_k$ are auxiliary variables tracking resource imbalance.

**Symmetry group :** Each bin $j$ can also be permuted. So it has a **symmetric group $S_{|J|}$** w.r.t. the bins $J$. Specifically, let $X \\in \\{0,1\\}^{|I|\\times |J|}$ be a feasible solution of with its $(i,j)$-th entry as the value of variable $x_{ij}$. Then arbitrary permutation $\\pi \\in S_{|J|}$ acting on its columns $\\{X_{:j}, \\forall j\\in J\\}$ yields an equivalent solution $\\left[X_{:\\pi(1)},X_{:\\pi(2)},\\dots,X_{:\\pi(|J|)} \\right]$.

**Sub-problem over the symmetry group :** Since the permutations of the symmetric group involve all possible reordering of the matrix columns. The sub-problem $\\min_{\\pi \\in S_{|J|}} \\ell(f_\\theta(s),\\pi(X))$ can equivalently modeled as $\\min_{P \\in \\mathcal{P}} \\ell(f_\\theta(s),XP)$, where $\\mathcal{P}$ is all permutation matrices (refer to Section 4.2.1).

Meta-review: This paper proposes a machine learning framework to solve mixed integer linear programming (MLIP). The main idea is to use a symmetry-aware loss function that incorporates permutations of solutions, which allows the model to learn more stable patterns for symmetric solutions. The authors also propose an alternating algorithm to train the neural network and the solution permutations. The framework was tested on three different tasks and four benchmark datasets, showing consistent improvements over traditional, symmetry-agnostic methods.

The reviewers unanimously support acceptance of the paper. I also recommend acceptance for this work.
Decision: Accept (poster)