SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimization

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.

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.

Question 1.1: ... the permutation group ,..., is only vaguely explained...

Some 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.

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

We 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. Instances 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\\}$.

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.

Question 2.1: on the identification of the symmetry group

According to the problems considered, the situations for symmetry identification are different:

• Case I: For a general ILP, its symmetry group can be efficiently detected by well-developed tools, such as Nauty[1], Bliss[2], etc.
• 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].

The 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". Besides, we remark that our framework is also applicable to Case I if the corresponding subproblems have appropriate customization and be solved.

Question 2.2: whether selecting a specific permutation group significantly impacts the computational complexity during the optimization process.

We 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?

The 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. For other symmetry groups that are not considered in our paper, it depends on how the sub-problem over symmetry groups is customized.

Question 3: Where in the paper are the details on "passing the outputs to an off-the-shelf solver" provided?

In 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? Since 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.

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.

The 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.

[1] McKay B D. Nauty user’s guide (version 2.4)[J]. Computer Science Dept., Australian National University, 2007: 225-239

[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.

[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.

Thank you for the detailed review and valuable comments. We address each weakness and question below.

W1: Applying classical approaches.

Thank you for raising the insightful comments. Below is our clarification.

Our framework includes two parts.

• a learning part: a GNN model that predicts an initial solution.
• a post-processing part: different downstream approaches can be equipped in this part to identify high-quality solutions based on the initial solution.

We argue that 1) classical symmetry-handling methods can not be directly applied in the learning part.

• 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.
• For future research, it is interesting to learn ideas from classical symmetry-handling methods and design appropriate learning algorithms.

2. Most downstream approaches already utilized classic symmetry-handling methods.

• 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.
• 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.

W2: Testing on other problems.

Thank you for the valuable comment.

We 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.

From the above table, we have some observations:

• Problems with more symmetry can benefit more when using SymILO.
• Our method can also be applied to no-symmetry problems (WA), and has a comparable performance to the baseline PS.
• Although more symmetry requires longer LP solving time, it is not a bottleneck on the considered datasets.

If 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.

W3: Scalability analysis.

1. complexity of the sub-problems over the symmetry group

   1.1. The complexity of different symmetry groups.

   • cyclic group $C_q$ and dihedral group $D_q$: $O(q)$.
   • symmetric group $S_q$: $O(q^2\text{log}q)$ (a linear assignment problem).

   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.

2. analysis of the convergence and scalability of the alternating minimization algorithm

   2.1. convergence

   • Empirically, the alternating algorithm could converge in our experiments (as shown in Figure 3 in the manuscript).
   • Theoretically, existing convergence conclusions can not be directly applied due to the discrete nature of sub-problems over symmetry groups.

   2.2. scalability

   • Compatibility to variable sizes: benefiting from the message-passing mechanism of GNNs, our alternating algorithm can be applied to ILPs with different sizes.
   • 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)$.

Q1: Search over a subgroup of symmetry.

Yes, 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.

However, 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.

Q2: Symmetry related.

1. How to check symmetry

   • Symmetry groups of ILPs can be efficiently detected by well-developed tools, such as Nauty [2] and Bliss [3].

2. Non-symmetry problems?

   • 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.

Q3: Should one apply the algorithm for symmetric problems where the number and the size of similar solutions are unknown?

As 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.

Q4: sub-problems over symemtry groups

The optimization over symmetry groups requires customization, i.e., we need to design appropriate ways to optimize a specific symmetry group.

• For cyclic and dihedral groups, it is trivial, since there are only $q$ and $2q$ ($q<n$) possible permutations, respectively.
• 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.

[1] Gasse, Maxime, et al. "The machine learning for combinatorial optimization competition (ml4co): Results and insights."

[2] McKay B D. Nauty user’s guide (version 2.4).

[3] Junttila T, Kaski P. Conflict propagation and component recursion for canonical labeling

Thank you for your detailed review and valuable comments. We address each question below.

Question 1: suggestion of presenting downstream approaches earlier

We 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.

Here 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.

Question 2.1: Detailed information for used MILP and symmetry

Thanks 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.

Question 2.2: indicate how the perturbation for PESPlib was done.

Problems 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)$.

Question 3: I tried to check the anonymous code repository, but it was expired.

Thanks for catching this. We have fixed this issue.

Question 4: Could you add standard deviations/errors to Table 2

Yes, the results with standard deviations are shown in the brackets as follows:

Note that the standard deviations among datasets IP, PESP, and PESPD are relatively large because:

• the reported primal gaps are averaged across instances, while different instances may have very distinct objective values.
• these three datasets include instances with very different sizes, please refer to Appendix F.1 for more details.

Question 5: GPU and CPU time

We are sorry for the confusion, here we add more explanation for Table 2.

• 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".
• The time cost reported in line $t$ is the time of solving LP averaged over instances, they are pure CPU time for LP solving.
• The batch size is set to $B = 16$, so in each iteration, the number of LPs is 16.
• 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.

Question 6.1: Are symmetry-related parameters of CPLEX tuned in experiments?

Yes, 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)

Question 6.2: How CPLEX is tuned.

The 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.

Indeed, as pointed out by [1], commercial solvers such as CPLEX have their own symmetry-handling methods including orbital fixing.

Question 6.3: Primal focus

The 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.

Question 7: Typos: Line 269: Is $\hat{x}$ supposed to be $\hat{y}$? Line 420 has a typo: "don not".

Yes, thank you for the correction, we have fixed them in the revised manuscript.

[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.

Weakness 1: evaluating the method on an additional task

Thank 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.

We 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.

Weakness 2: generalization to larger instances

Thank 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.