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

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.

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. 2. The presentation is neat.

Weaknesses

See questions.

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. 2. 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. 3. Where in the paper are the details on "passing the outputs to an off-the-shelf solver" provided? 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.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

See questions

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.

Strengths

1. The 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. 2. The 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. 3. The 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. There 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. 2. I 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. 3. In 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).

Questions

1. In 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. 2. How 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. 3. Should one apply the algorithm for symmetric problems where the number and the size of similar solutions is unknown? 4. how to compute \pi^' in line 267? Is argmin_\pi a trivial problem? 5. Refer to weaknesses

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors point to the potential slowdown on a large instance as a limitation. However, authors do not provide deeper analysis of it.

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.

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.

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. 2. 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. 3. I tried to check the anonymous code repository, but it was expired. 4. Could you add standard deviations / errors to Table 2? 5. 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? 6. 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. 7. Typos: Line 269: Is $\hat{x}$ supposed to be $\hat{y}$? Line 420 has a typo: "don not".

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

The paper properly indicates the main limitations of this work in Section 7.

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.

Strengths

1. The proposed formulation and method for symmetry-aware learning for ILPs is novel. 2. 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. 3. 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. Nonetheless, 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] [1] Fan, Zhenan, et al. "Smart initial basis selection for linear programs." International Conference on Machine Learning. PMLR, 2023. [2] Zhang, Yahong, et al. "MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness." Forty-first International Conference on Machine Learning. [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. 2. 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.

Questions

I don't have specific questions.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors talk about some limitations of the work, but not all that are known.

Question 4 (cont.)

Here we supplement the specification of Example B.0.2 in the Appendix. **1. Description:** Given a circle with circumference $8$, place $3$ ticks at integer points around the circle such that all distances between inter-ticks along the circumference are distinct. **2. Formulation:** $$\\begin{align} \\min_{x_1,x_2,x_3} &~~~~~0 \\notag \\\\ s.t. ~& y_{ij} = |x_i - x_j|, &&\\forall (i,j) \\in S,&&&(1)\\\\ ~& d_{ij} = \\min \\{y_{ij},8-y_{ij}\\}, &&\\forall (i,j) \\in S,&&&(2)\\\\ ~& d_{12} \\neq d_{13}, d_{12} \\neq d_{23}, d_{13} \\neq d_{23},&& &&&(3) \\end{align}$$ where $S = \\{(1,2),(1,3),(2,3)\\}$, $x_1,x_2,x_3 \\in \\{1,2,3,4,5,6,7,8\\}$ denote the positions of each tick, $d_{ij}$ are distances between ticks $i$ and $j$ with auxiliary variables $y_{ij}$. **3. Linearization of nonlinear constraints:** The constraints in the above formulation are nonlinear, we linearize them by big-M methods. - **Constraints (1):** Equalities $(1)$ can be linearized by introducing auxiliary variables $a_{ij} \\in \\{0,1\\} , \\forall (i,j)\\in S$ as $$ \\begin{align} &y_{ij} \\geq x_i - x_j, &\\forall (i,j) \\in S,&&&(4)\\\\ &y_{ij} \\geq x_j - x_i, &\\forall (i,j) \\in S,&&&(5)\\\\ &y_{ij} \\leq x_i - x_j + 8\\cdot a_{ij}, &\\forall (i,j) \\in S,&&&(6)\\\\ &y_{ij} \\leq x_j - x_i + 8\\cdot(1-a_{ij}),&\\forall (i,j) \\in S,&&&(7) \\end{align} $$ where $a_{ij} = 0$ enforces $x_i-x_j\\geq0$, otherwise $x_i-x_j\\leq0$. - **Constraints (2):** Similarly, equalities $(2)$ are equivalent to $$ \\begin{align} &d_{ij} \\leq y_{ij}, &\\forall (i,j) \\in S,\\\\ &d_{ij} \\leq 8-y_{ij}, &\\forall (i,j) \\in S,\\\\ &d_{ij} \\geq y_{ij} - 8\\cdot m_{ij}, &\\forall (i,j) \\in S,\\\\ &d_{ij} \\geq 8-y_{ij} - 8\\cdot(1-m_{ij}), &\\forall (i,j) \\in S, \\end{align} $$ where $m_{ij}\\in\\{0,1\\}, \\forall (i,j) \\in S$ are auxiliary variables, with $m_{ij}=0$ when $y_{ij}\\leq 8-y_{ij}$. - **Constraints (3):** The "not equal to" constraints $(3)$ can be linearized by $$ \\begin{align} &d_{ij} \\geq d_{k\\ell}+1 - 8\\cdot t_{ijk\\ell}, &\\forall (i,j,k,\\ell) \\in K,\\\\ &d_{k\\ell} \\geq d_{ij}+1 - 8\\cdot(1- t_{ijk\\ell}), &\\forall (i,j,k,\\ell) \\in K, \\end{align} $$ where $K = \\{(1,2,1,3),(1,2,2,3),(1,3,2,3)\\}$. By introducing auxiliary variables $\\{t_{ijk\\ell}\\in \\{0,1\\}, \\forall (i,j,k,\\ell) \\in K\\}$, we have $d_{ij} \\geq d_{k\\ell} + 1$ if $t_{ijk\\ell}=1$, otherwise $d_{ij} \\leq d_{k\\ell}-1$, i.e., $d_{ij}\\neq d_{k\\ell}$. **4. Symmetry group:** Assume $\\{x\_1=\\bar{x}\_1,x\_2=\\bar{x}\_2,x\_3=\\bar{x}\_3\\}$ is a feasible solution of this problem and let $[\\cdot]_T$ denote the $mod-T$ operation, then it's easy to verify that $\\{x\_i=[\\bar{x}\_i+b]_8\\}\_{i=1}^3$ (rotation) and its reverse $\\{x_i=[(8-\\bar{x}_i)+b]_8\\}\_{i=1}^3, \\forall~ b\\in \\mathbb{Z}$ (reflection) are both equivalent feasible solutions. That is, rotation and reflection acting on the ticks do not change their corresponding distances (please refer to Figure 6 of the Appendix for visual illustration). When representing $x_1,x_2,x_3$ by binary variables $z_{ip}\\in \\{0,1\\}, \\forall i\\in{1,2,3},\\forall p\\in\\{1,\\dots,8\\}$: \\begin{align} &x_i = \\sum_{p=1}^8 p \\cdot z_{ip}, & \\forall i \\in \\{1,2,3\\},\\\\ &\\sum_{p=1}^8 z_{ip} = 1, &\\forall i \\in \\{1,2,3\\}, \\end{align} the modulo symmetry leads to a dihedral group $D_8$ along the $p$ dimension of $z_{ip}$. Specifically, let $Z$ be a feasible solution with its $(i,p)$-th entry as the value of $z_{ip}$, then any permutation $\\pi \\in D_8$ acting on the columns of $Z$ yields another equivalent solution $\\left[ Z_{:\\pi(1)},\\dots,Z_{:\\pi(8)} \\right]$.