When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach
Authors: Qian Chen
Lei Li
Qian Li
Jianghua Wu
Akang Wang
Ruoyu Sun
Xiaodong Luo
Tsung-Hui Chang
Qingjiang Shi
Venue: ICLR 2025 Poster (2025)
Keywords: integer linear programming
symmetry
machine learning
graph neural networks
Primary area: optimization

Abstract: A common characteristic in integer linear programs (ILPs) is symmetry, allowing variables to be permuted without altering the underlying problem structure. Recently, GNNs have emerged as a promising approach for solving ILPs. 
However, a significant challenge arises when applying GNNs to ILPs with symmetry: classic GNN architectures struggle to differentiate between symmetric variables, which limits their predictive accuracy. In this work, we investigate the properties of permutation equivalence and invariance in GNNs, particularly in relation to the inherent symmetry of ILP formulations. We reveal that the interaction between these two factors contributes to the difficulty of distinguishing between symmetric variables.
To address this challenge, we explore the potential of feature augmentation and propose several guiding principles for constructing augmented features. Building on these principles, we develop an orbit-based augmentation scheme that first groups symmetric variables and then samples augmented features for each group from a discrete uniform distribution. Empirical results demonstrate that our proposed approach significantly enhances both training efficiency and predictive performance.

Published as a conference paper at ICLR 2025
WHEN GNNS MEET SYMMETRY IN ILPs: AN ORBIT- BASED FEATURE AUGMENTATION APPROACH
Qian Chen! Lei Lit?, Qian Li,, Jianghua Wu?, Akang Wang"."" Ruoyu Sun Xiaodong Luo?, Tuu Chang2+ and Qingjiang Shi2.5
Schooo of Science and Engineering, The Chinese University of Hong Kong, Shenzhen, China =Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research
Institute of Big Data, China
3 School of Data Science, The Chinese University of Hong Kong, Shenzhen, China School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen, China School of Software Engineering, Tongji University, Shanghai, China
ABSTRACT
A common characteristic in integer linear programs (ILPs) is symmetry, allow- ing variables to be permuted without altering the underlying problem structure. Recently, GNNs have emerged promising approach for solving ILPs. How- ever, a significant challenge arises when applying GNNs to ILPs with symmetry: classic GNN architectures struggle to differentiate between symmetric variables, which limits their predictive accuracy. In this work, we investigate the properties of permutation equivariance and invariance in GNNs, particularly in relation to the inherent symmetry of ILP formulations. We reveal that the interaction between these two factors contributes to the difficulty of distinguishing between symmetric variables. To address this challenge, we explore the potential of feature augmen- tation and propose several guiding principles for constructing augmented features. Building these principles, develop an orbit- augmentation scheme that first groups symmetric variables and then samples augmented features for each group from a discrete uniform distribution. Empirical results demonstrate that our proposed approach significantly enhances both training efficiency and predictive performance.
INTRODUCTION
Integer Linear Programs (ILPs) fundamental optimization problems characterized by linear objective function and linear constraints, where the decision variables are restricted to integer val- ues. These problems play a critical role in various fields, including operations research, computer
science, and engineering (Pochet & Wolsey 2006 Liu & Fan 2018 Watson & Woodrufi 2011 Luathep et al., 2011 Schöbel| symmetry, where certain permutations of decision variables leave both the problem structure and the solution set unchanged (Margot (003). For example, the widely used collection of real-world
practice, many ILPs exhibit a structural property known as
ILPs, MIPLIB Gleixner et al. 2021 approximately 32% of its instances display certain symme- tries.
Classic methods for solving ILPs, such as branch-and-bong and branch-and-cut (Boyd & Mattin- gley| 20077: Morrison et al.) 2016), systematically explore the solution space by breaking down into smaller sub-problemn and eliminating regions that do not contain optimal solutions. However, the presence of symmetry in these problems can result in redundant exploration of equivalent solu- tions, which hampers efficiency. To address this, several approaches have been developed. Margot 2002) prunes the enumeration tree in the branch and bound algorithnn(Ostrowwsk OOstrosski et al. (2008) 200 propose branching strategies based orbits: Puget 2003 2006) enhance problem formulations by introducing symmetry-breaking constraints. A more comprehensive survey of related research is
Corresponning author; Akang Wang <wangakang@srihdlnn.

---

Published as a conference paper at ICLR 2025
provided in (Margot 2009). These techniques reduce the search space by detecting and removing symmetric solutions, allowing the solver to focus on unique, non-redundant parts of the problem. By leveraging symmetry in this manner, the overall efficiency and convergence of ILP solvers are significantly improved. While classic methods have been widely used, they fall short in terms of efficiency for real-world applications, calling for more advanced approaches.
Recent advancements in machine learning (ML) have opened new avenues for solving ILPs, offering approaches that enhance both efficiency and scalability (Gasse et al.) 2202). Among these techniques, Graph Neural Networks (GNNs) have shown significant superiority in capturing the underlying structure of ILPs. By representing the problem as a graph. GNNs are able to exploit relational information between variables and constraints, which allows for more effective problem- solving strategies. Several categories of works have demonstrated the potential of GNNs in this context. Gasse et al.] (2019) first proposed bipartite representation of ILPs and applied GNNs to learn efficient branching decisions in branch-and- bound algorithms. Such graph representation was then utilized or enhanced by many subsequent researchers. Nair et al. (2020) utilized GNNs to predict initial assignments for ILP solvers to identify high-quality solutions. Khalil et al. (2022) integrated GNNs into the node selection process of the branch and bound framework. Other notable examples include learning to select cuts (Paulus et al.) 2022), learning to configure (lommazzo et al.) 2020) and so A more comprehensive review of relevant works can be found in Cappart et al. 2023
Challenges: Despite the growing number of ML--based methods for solving ILPs, only few works have noticed the intrinsic property of ILPs-symmetry. This oversight often results in poor perfor- mance on problems with significant symmetries. Typical approaches, such as learning a GNN to predict the optimal solution, face the following indistinguishabiity issue when encountering sym- metries in ILPs (a specific example depicted in Figure I:
Traditional GNNs are incapable of distinguishing symmetric variables, limiting their effectiveness on ILPs with symmetry.
commetry-breakinn in ML: The issue of indistinguishabiiity stems from the limitations of permutation equivvariat functions handling data with inherent symmetries. Recent studies, par- ticularly in chemistry and physies, have explored solutions to similar issues. One approach is to introduce augmented features into graph- or set-structured data to break symmetry. For example, Xie & Smidi (2024) introduces equivariant symmetry-breakinng sets (SBS), which use symmetry groups to provide more informative inputs, breaking symmetry and improving computational effi- ciency. Similarly, Lawrence et al. (2024) extends SBS by incorporating probabilistic methods and canonicalization techniques for further efficiency. |Morris et al. (2024) takes a different approach, using orbits for symmetry- -breakiigg offering simple yet effective solution for graph data. Earlier works like (Smidt et al.] (202T), /Zhang et al. (202T). and Kaba & Ravanbakhsh (2023) have laid the foundation for understanding symmetry in neural networks. In the ILP context, few studies have also addressed this issue. CCen et al. (2022) tackles the problem of GNNs failing to distinguish fold- able instances by adding random features to enhance expressiveness. Likewise, Han al.) (2023) and [Chen et al. (2024) add positional embeddings to bipartite ILP representations, helping mitigate symmetry-relattdd challenges.
While the broader literature has extensively explored bymmetry-breaking in chemical and physical systems, research on addressing indistingushability issue ILPs remains limited. To date, no studies have fully adapted the advanced symmetry-breakinn techniques used in these fields to ILP problems, nor have they leveraged the unique structural properties of ILPs to tackle symmetry more effectively. Moreover, there is notable lack of theoretical analysis and empirical validation re- garding the efficacy of existing machine learning methods for handling symmetry in ILPs. This gap highlights the urgent need for more robust, symmetry- aware solutions that can exploit the inherent symmetries of II.Ss, ultimately improving the performance of IIP solvers on symmetric instances and making them more efficient in real-world applications.
Motivation:
Considering the limitation of traditional GNNs in predicting the solutions for ILPs with symmetric variables, we first explore the inherent formulation symmetry property of these ILPs. By investigating the interplay between it and the permutation equivariance and invariance of GNNs, we show that they together lead to the performance limitation. To address it. we exploit feature augmentation and propose three guiding principles in constructing augmented features, including
Contributions:
2

---

Published as a conference paper at ICLR 2025
i) distinguishability.. ii) augmentation parsimony, and iii) isomorphic consistency. The first prin- ciple enables GNNs to output different values for symmetric variables and the second one avoids introducing 'conflict' training samples that could mislead GNNs yield wrong predictions. Mean- while, the second principle aims to keep the augmented features as simple as possible to enhance the training efficiency. Further, devise orbit-based feature augmentation scheme and analyze the difference between our proposed design and other existing schemes under these principles. Finally, our proposed orbit-based scheme is tested over classic ILP problems with significant symmetry and compared with existing schemes to validate the effectiveness of our proposed principles and design. Our contributions are summarized follows.
Theoretically demonstrating that the interplay between the formulation symmetry and the properties of permutation equivariance and invariance GNNs makes classic GNN archi- tecture incapable of differentiating between symmetric variables.
Exploring the potential of feature augmentation to address the limitation, and proposing three guiding principles for the construction of augmented features.
Following these principles, developing an orbit-based feature augmentation scheme, and validating that can achieve a remarkable improvement the prediction performance of GNNs for the ILPs with strong symmetry.
2 PRELIMINARIES
Unless otherwise specified, scalars are denoted by normal font (i.e., 2, A), vectors are denoted by bold lowercase letters (i.e., at), and matrices are represented by bold uppercase letters (i.e.. X). The i-th row and the j-th column of matrix X are denoted by X;, and X. respectively.
Notation:
2.1 ILP AND SYMMETRY
An integer linear program (ILP) has a formulation as follows:
min {c TeTTolA4 Az & b. E z
where x: E n are integer decision variables, and e E TRn A E Rmxx, E R are given co- efficients. Let X denote the set of all feasible solutions of (I). A symmetry of (T) is bijection X' - X' such that c g(x) permute variables (Def. D while retaining the description Ax and the objective coefficients invariant. Such symmetries are called formulation symmetries (Def. 2 All formulation symmetries of (T) form group, which named symmetry group.
c x. Væ E X. In practice, one often considers symmetries that
Definition 1. (Permutation) A permutation over set === =1,........ (1. is a bijection π : I - I" such that for every element E I" (j E I"), there exists a unique element E I" I*) such that T()) - (n (j) i). The set of all n! permutations over 1 is denoted by S,.
In this work, given a permutation π E Sn, when acts on different objects such as the elements of a vector, the rows and the columns of a matrix, the notation will be added with different superscripts to distinguish them from one another. Specifically, the same permutation æ E S, acting on the top-most elements of a vector y, the top-most rows and the left-most columns of matrix X is denoted by
T" (y) (l((1): Vr(n), Vn.......
x" x"XX) (a()). Xx()). Xntt.s....]T
(X)
X. (()), X X.ntt.......
Definition 2. (Formulation symmetry) permutation π E Sp is a formulation symmetry of 1 there exists permutation Sm. such that
x" (c) =
(b)
A0(0 = Args Vi,
Another important concept in symmetry handling is orbit defined in Def. of elements that can be transformed into each other through symmetries. We call two variables are symmetric if they correspond to the same orbit.
3 which refers to the set
3

---

Published as a conference paper at ICLR 2025
Definition 3. (Orbit) Let 9 be the symmetry group of (.) then the orbit of 1" under G is set (i( VT E g). All orbits of 1 under 9 form partitioning of I i.e., {O1...., O where Op n 0. vp + q f K} and UK k= =
2.2 LEARNING TASKS
In this paper, we consider classic learning task aimed at developing model fo + R" to predict optimal solution for an ILP instance, where G is the space of the bipartite representation of the IIP, which will be explained detail later. While there could be multiple optimal solutions for ILP. this work only focus on predicting just one of them, since many practical applications typically require one solution rather than an exhaustive set. The training of model fe employs supervised learning, utilizing dataset D that consists of (input, label) pairs (B, i== where each 8; represents an ILP instance and ã; denotes one of its corresponding optimal solutions. The model is trained by minimizing loss function ((-) over all the N instances from the dataset, leading the optimization problem ming N ΣN ((o())),
2.3 BIPARTITE REPRESENTATION
In the learning task, an ILP instance s; is first transformed to an equivalent bipartite graph before be- ing imput to the GNN. Without loss generality, we consider the following bipartite representation. Specifically, an ILP ( is characterized by a bipartite graph {V, W, EY, where
V (UI,... )n is the set of variable nodes with v, E V denoting variable zy- The variable node n is associated with feature hj == E R.
W = [wi..... wm) } is the set of constraint nodes with denoting the i-th constraint. The constraint node w; associated with feature h b, IR.
E (ey v(i,)) Asg + 0} is the set of edges with Ety denoting that variable xy appears in the i-th constraint. The edge eij is associated with feature hig == Aij R.
An example of the bipartite graph representation is given in Fig. I For brevity, A == H
h="
A
b)
E ((m++)x(n++)) to denote the aforementioned bipartite representation.
(
0
c
0
ISSUES OCCUR WHEN GNNS MEET FORMULATION SYMMETRY
While GNNs excel at capturing the underlying structure of ILPs, their effectiveness is limited when the ILP problems exhibit specific formulation symmetries. As shown the example in Fig. [ the GNN fails to predict the optimal solution for an ILP instance with symmetry.
Instance min Ri
Graph Representation of the ILP
Optimal Solution (Label)
U1
W
A
Prediction
stt. 21 +
21
hy
0
U2
GNN
0
-1,
.5
21, 1)
Symmetry
A
Wx
Ag
23
x:x(1] = (2) 11, 1,) =3
Variable nodes
Constraint nodes
Figure 1: Left: An ILP instance where and 22 are symmetric. Middle: A bipartite representation of the II. instance. The variable and constraint nodes correspond to their counterparts the II.P instance, with edges connecting them denoting the coefficients of variables in constraints. Right: The outputs for the symmetric variables are identical due to symmetry, thus GNNs cannot correctly predict the optimal solution.

---

Published as a conference paper at ICLR 2025
In the following, rigorously show that it is the interplay between the inherent properties of GNNs and the formulation symmetry of ILPs that makes the model incapable of distinguishing between symmetric variables and predicting the optimal solutions.
Assumption 1. (Permutation equivariance and invariance) Assume the model fo is equivalent w.n.t. permulations acting the variable nodes (i.e. VT E Su. fo (A)) T² (So(A)) and invariant W.E. permutations acting on the constraint nodes (i.e., vo E Sm. folo" (A)) = fo(A)))
Notice that GNNs naturally satisfy the above assumption. Moreover, when such model is applied an ILP instance with formulation symmetry, the elements of the predicted solution corresponding to the same orbit will be identical. Accordingly, the following proposition (see proof in the Appendix A.4 will hold.
Proposition 1. Under Assumption 7 if a permutation π E Sn is formulation symmetry of 4 then we have (A); fo(AA)(()) Further, the elements of fo(A) correspond to the same orbit are identical, ie.. fo = fo(AA), Vi,j E O, 20 Orbit(g).
With Proposition I it is not difficult to derive the following corollary (see proof in Appendix (..5 Corollary 1. Under Assumption[] [ the model fo cannot always correctly predict the optimal solution of an ILP instance with formulation symmetries.
METHODOLOGY
The analysis in the previous section raises key question: How can we improve the ability of GNNs to solve ILPs with formulation symmetry? A promising approach is to augment the input features of the GNN, enabling it to differentiate between symmetric variables. While similar idea was adopted in (Chen et al. 2022), where random features were added into the bipartite graph representation to distinguish what they refer as 'foldable' ILP instances, the approach did not exploit the underlying symmetry properties, leading to suboptimal performance on IIPs with strong symmetries. In this section, we first establish three guiding principles for feature augmentation and, based on these principles, propose an orbit-basce feature augmentation scheme to handle symmetries more effectively.
4.1 PRINCIPLES FOR CONSTRUCTING AUGMENTED FEATURES
Motivated by the existing breaetty-brcaking methods (Chen et al. 2022 Xie & Smidt 2024]
Lawrence et al. 2024) that address symmetry by introducing augmented features into the data, we tackle the indistinguishabiityy issue in ILPs by incorporating random features into the bipartite graph representation. Specifically, let z E 1" be an augmented feature sampled from a space C R", and
11=3 0
A
b
it is assigned to the variable nodes. For brevity, let Á
c
0
R (
be the bipartite graph representation incorporating 2. In contrast to existing methods that add aug- mented features to all nodes in the graph, focus exclusively on the variable nodes. This strategy targets the symmetries inherent in the variables, which are sufficient to differentiate the outputs dur- ing solution prediction, while disregarding the constraint symmetries. By doing so, simplifies the symmetry groups that need to be processed, improving computational efficiency.
There are three principles the augmented feature should follow:
(distinguishabilitt) there exists function fa such that fo(A), # So(A),, Vi # O, YO E Orbits(AA,) G).
(augmentation parsimony) The cardinality of the augmented feature space V should be as small as possible
(isomorphic consistency) If (A, a)) and (A', w') are two training samples with isomorphic instances A and A' (i.c., 3т E Sn, E Sm such that (T" (A)) = A²), then T (x) n" (T)
The first principle, distinguishability is a necessity, which enables GNNs to output different values for symmetric variables. The simplest way to realize it is by assigning distinct features to variables
5

---

Published as a conference paper at ICLR 2025
in the same orbit, i..., 2, # a crucial role in the model's training process. By using à small cardinality of the augmented feature space, this guiding principle prevents the model from being overwhelmed by excessive irrelevant information that could slow down the learning of correct correlations. This enhances training effi ciency, fewer features require less computational effort learn and stabilize the model, leading to faster convergence and better overall performance. Note that the core ideas underlying these two principles are drawn from existing works (Xie & Smidi, 2024, Lawrence al. 2024 Morris al. 2024 and have been adapted to fit our augmentation scheme.
2,, #2,
O. The second principle, augmentation parsimony, plays
The last principle, isomorphic consistency, enforces that the labels of isomorphic inputs should remain isomorphic as well. This principle stems from the permutation equivarianccelivariince of the ground truth function, with further details provided in Appendix [A.2] Samples that fail to meet this criterion are termed conftict or inconsistent samples, which can negatively impact the GNN's s training. Proposition 2 (see proof in the Appendix [A.6] reveals that conflict samples will lead to a higher loss and should be avoided in constructing the training data.
Proposition 2. If the augmented features doesn't 't satisfy the principle of isomorphic consistency, then the minimal loss can not be O.
4.2 ORBIT-BASED FEATURE AUGMENTATION
Following the aforementioned three guiding principles, we develop a novel feature augmentation scheme that harnesses the formulation symmetry of ILPs in constructing the augmented features.
First, the principle of distinguishability can be easily achieved; the simplest ap- proach is to assign a unique augmented feature to each variable node. This is
Algorithm 1 Orbit-based feature augmentation
Input: ILP instance A with orbits (0.,...,Ok)
Procedure:
equivalent to sampling [=:} from the set .......]] without replacement. How-
3: Initialize x +-
4:
for k E (I....,K) K} 3: O&l 2 2 do nontrivial orbits
5:
{1, C+ 6: for i O2 do
10x...
ever, the cardinality of the augmented fea-
ture space by such an approach is [V] nl, which is too large to ensure good aug- mentation parsimony.
7:
& ~ Uniform(C) C=C\ {z}
b sampling
8:
b without replacement
end for 10: end for
9:
Additionally, the isomorphic consistency property stipulates that the augmented fea- tures and z for any two training samples (A, x), (A',
11: Output: augmented feature: z
x²) with isomorphic instances
π²" T²(x) ø'. This relation is imposed on not only the augmented feature but also the label. For ease of illustration, here we introduce the construction of augmented
should satisfy (=)
z' +
features first and leave the analysis on how isomorphic consistency handled to Sec. 4.3
Further, in accordance with the principle of augmentation parsimony, the augmented features with a smaller cardinality of their associated space [V] are preferable. Intuitively, 2; should be sampled over a set smaller than {1, {1...., ... n while maintaining the distinguishability. For IIPs with symmetry, one can find that sampling over the orbits can achieve the two targets at once. To this end, we propose an orbit- feature augmentation approach as follows. Specifically, consider an ILP instance A characterized by its orbits {O....., Ok). For any orbit O₂ E (O OK) } with |O 2 2, the augmented feature } O₂ are uniformly sampled from a discrete set C = 21, ..., [O without replacement. For trivial orbits that contain only a single element, we assign zeros as the corresponding augmented features. The proposed scheme is detailed in Algorithm] [nnd is referred to as Orbit in the remainder of this work.
By leveraging the structural symmetry, the proposed Orbit effectively reduces the cardinality of the augmented feature space. In many categories of IIPSs there usually exist certain connections between different orbits, which can be further exploited reduce the cardinality. Specifically, as- sume an ILP instance has < K orbits Oi,..., Op with the same cardinality c. The elements To11
0le
of these orbits form matrix O
where og E O,,i P =1, (1......) p).
Lop1 Ope
The formulation symmetry of the instance necessitates that all elements in each column of O be

---

Published as a conference paper at ICLR 2025
treated as an integrated unit under any permutations defined by the symmetry group. That is, VI E (,T(),)) = Osk @ T(o3)) = Oyk. Vi, E P.k E fl....,c.. For such an instance, the augmented features added to the variables corresponding to the same column of O can be iden- tical. Accordingly, it suffices to sample augmented features for the variables in one orbit and as- sign the same features the corresponding variables in the other orbits, e.g., Øij m,, Vj {I....,c) c} = Oig + my Vi E [l,.....p) ph.j j E {l,...,ch. As shown in the example in Appendix A.1 this updated scheme, named Orbit+, further employs the additional connections among the orbits in constructing the augmented features, achieving smaller [ with enhanced augmentation parsimony.
4.3 ANALYSIS
In this section, our proposed orbit-based feature augmentation schemes and two other existing schemes are analyzed with our proposed three principles in Sec. 4.1 Specifically, we will eval- uate whether the distinguishability and isomorphic consistency are satisfied, as well as assess the cardinalities of their respective augmented feature spaces. Before proceeding with the analysis, let's first introduce two existing feature augmentation schemes.
Random noise from a uniform distribution (Uniform) Chen al. (2022) noticed the lack of expressive power of GNNs to distinguish some ILP instances (called as "foldable"), and proposed to introduce random noise from uniform distribution to both variable and constraint nodes. Here consider the case where random noise added to variable nodes only, as is sufficient to meet the distinguishability.
Positional IDs (Position) The second scheme is adding positional IDs to the variable nodes, en- suring each variable node associated with a distinct ID. Han et al. (2023) adopted such trick in their feature designs, while without discussing insights and necessity.
4.3.1 ON THE PRINCIPLES OF DISTINGUISHABILITY AND ISOMORPHIC CONSISTENCY
The condition outlined in the principle of distinguishability is straightforward satisfy, provided that the variable nodes within the same orbit are associated with distinct augmented features. It's easy verify that the Position, Orbit, and Orbit+ schemes all strictly assign distinet augmented features to variable nodes in the same orbit, while the Uniform scheme does so with probability 1. Therefore, all these four schemes meet the principle of distinguishability.
Unlike the principle of distinguishability, the principle of isomorphic consistency imposes a more complex condition, as it applies to both the input instances and the output labels. As demonstrated in Appendix A.3] sampling strategies can violate this principle, resulting in situations where π =²(2) but (z) 7 æ'. To address this issue, there are two potential approaches: one is resampling when (z) z'. while the other replaces E and ø' with alternative optimal solutions ÿ and y', ensuring that T" (g) = D'. this paper, we adopt the second approach, as the first one relies on label- dependent reject sampling, which is infeasible during the testing phase when labels are unavailable. Specifically, we utilize the SymIL.O framework proposed by [Chen et al.] (2024), which supports dynamically adjusting the labels of the training samples. It jointly optimizes the transformation of solutions and the model parameters, aiming to minimize the prediction error. Since SymILO does not directly operate augmented features, we apply it uniformly across all methods in Section 5 to alleviate the impacts of violations of the principle isomorphic consistency.
4.3.2 ON THE PRINCIPLE OF AUGMENTATION PARSIMONY
Among the four augmentation schemes, the augmented feature of Uniform is sampled from a contin- uniform distribution. Therefore, the cardinality of its augmented feature space be infinite, i.e., Ca = +c. For the Position scheme, its augmented features are uniformly sampled from a discrete distribution from the set (l...., n). Accordingly, the cardinality of its feature space is Cp = n!. In comparison, for our proposed Orbit scheme described in Sec. 4.2] the augmented feature {2,} associated with each orbit O₂ E Orbits(A) is sampled from the set (1, As a result, the cardinality of our proposed Orbit scheme is c. (|Or1!) (I.,)))....((Ox))
where 1
12il < n. Further, when the formulation symmetry imposes additional connections

---

Published as a conference paper at ICLR 2025
among 1 p v K orbits, the augmented feature only needs to be sampled for one orbit and can be reused for the other (p - 1) orbits. Without loss of generality, assumee these p orbits are com- posed by O₁, Oz...., Op with |01 |02| = ..... Opl.- Correspondingly, the cardinality of the augmented feature space of Orbit+ is Co+ = (O,l!) ..... ([Ox!!). is not difficult to verify that Cot Co < cp Cu- Correspondingly, our proposed orbit-hased augmentation schemes achieve better augmentation parsimony.
5 EXPERIMENTS
In this section, we present numerical experiments to validate the effectiveness of the proposed ap- proaches. The souree code is available at http:///gttbbbcooo//m/syyggggugg
5.1 DATASET
We evaluate our proposed approach using three ILP benchmark problems that exhibit significant symmetry. The descriptions of these benchmarks are as follows:
BPP: The bin packing problem (BPP) a well-known practical problem where items must be placed into bins without exceeding capacity limits. The objective is to minimize the total number of bins used. We generate 500 instances, each with items, following the generation strategies outlined by Schherin & Wäscher (197]. These instances include 420 variables and 40 constraints, with an average 14 orbits, and orbit cardinalities reaching up to 140.
The balanced item placement problem (BIP) also involves assigning items to bins. However, unlike bin packing, the goal is to balance resource usage across bins. We use 300 instances from the ML4CO competition benchmarks (Gasse et al. 2022). These instances feature 1,083 variables and 195 constraints, with an average of 100 orbits.
BIP:
SMSP: The steel mill slab design problem (SMSP) is variant of the cutting stock problem, where customer orders are assigned to slabs under color constraints, with the aim minimizing total waste. We use 380 instances from (Schaus et al.) 2011), which range between 22,000 and 24,000 variables and nearly 10,000 constraints. On average, these instances have 110 orbits, with orbit cardinalities varying between 111 and 1,000.
In our experiments, 60% of the instances are used for training, and the remaining 40% reserved for valida- tion. Since these datasets include only the problem in- stances, we also gather corresponding solutions. Due to the complexity of the constraints, obtaining optimal so- lutions for every instance is not computationally feasi- ble. Instead, we run the ILP solver SCIP (Gamrath et al.) 2020) for 3,600 seconds on each instance and store the best solution found. The average numbers of variables, constraints, as well as orbits of each benchmark problem, are summarized Table D
Table Statistics about the datasets.
Avg. number
Problem
Var.
Cons.
Orbits
BPP
420
40
14
BIP SMSP
1,083
195
100
23,000
1,000
110
5.2 BASELINES AND THE PROPOSED METHOOS
We consider three baselines (No-Aug, Uniform and Position) which employ different feature aug- mentation strategies, and compare them our proposed methods (Orbit and Orbit+).
This is the baseline where no feature augmentation is adopted. To align with other strate- gies, the augmented features z are set as zeros for all variables. Uniform: As described Sec. 4.3 this baseline samples each element of individually from uniform distribution to distinguish symmetric variables, i.c., 24 ~ 4( 1), Vi E [n]. Position: As described Sec. 4.3 this baseline assigns unique integer numbers to the elements of z to distinguish between different variables by their positions. Specifically, the augmented features 2,, Vi E [r]] can be uniformly sampled from (1...., n without replacement. Orbit: This is our proposed augmentation scheme outlined in Al- gorithm which utilizes the structural information from orbits and adds augmented features within each orbit individually. Orbit This is enhanced version of the orbit-based feature augmen-
No-Aug:
8

---

Published as a conference paper at ICLR 2025
tation scheme mentioned in Section 4.2 which exquisitely assigns the same augmented features to multiple orbits for certain types of symmetries.
5.3 EVALUATION METRICS
To evaluate the prediction performance of models trained with different augmented features, the Top-m% error proposed by Chen et al. (2024) is used as the evaluation metric, which takes into account the impact of the formulation symmetry on the solutions.
Top-m% error: It is based the fi-distance between rounded prediction and its closest sym- metric solution. Given the label of a instance and a prediction ÿ. the equivalent solution of closest is defined as ÿ n' (y), where '² = arg ming | (V))l- Based on this observation, the Top-m% error is defined as:
Emm) Σ Round (j:) Wel-
(3)
where M the index set of the top m% variables with the smallest values of [Round (ūj) - Ønl. Vj. This error measures the minimum fi-distance between the prediction and all equivalent solutions of the label. Compared to the & distance Eiem ((x,nd(ū)) - yil that ignores the effect of multiple equivalent solutions caused by formulation symmetry, the metric adopted characterizes the distance between a prediction and feasible solution more accurately. With the standard l fi-distance, the error would be non-zero when Round () * y. whereas it would be reduced with (3). as long as there exists 2 = n' (y) and its element j matches (o.nd
5.4 MODEL AND TRAINING SETTINGS
The model architecture follows Han et al. (023), where four half-layer graph convolutions are used to extract hidden features and another two-layer perceptron is used to make the final prediction. We also follow most their settings for the initial features used in the bipartite representation of ILP instances. The only difference augmentation strategy in our baselines.
omit the "pos_emb" feature its role is the same as the "Pos"
In the training configuration, we utilize the Adam optimizer with a learning rate of 0.0001 and a batch size of 8. All models are trained for 100 epochs, with the parameters corresponding to the lowest validation loss preserved for subsequent evaluation. Since all augmented features randomly generated, multiple samples should be drawn for each training instance to mitigate over- fitting. Accordingly, we sample times for each training instance, while only single sample is taken for each instance in the test set. The symmetry detection is conducted with the well-developed tool Bliss, and more details are shown Appendix A.8
5.5
MAIN RESULTS
In this section, we present the numerical results comparing different augmented features. As shown in T among the three baselines, the Top-m% errors attained by Uniform and those by Position much smaller than those by No-Aug. This is natural since the last one does not employ any fea- ture augmentation. The large error of No-Aug demonstrates the necessity of addressing the issue that symmetric variables can not be distinguished. Meanwhile, the performance improvement brought by Uniform and Poisition validates the effectiveness of feature augmentation. Moreover, Position has smaller cardinality of augmented feature space, thus its performance generally better than that of Uniform.
Compared with the three baselines, our proposed orbit-based feature augmentation methods bring a notable reduction of the prediction errors. Notice that the reduction of loss from Position to Orbit more distinct than that from Uniform to Position. This because both Uniform and Position mainly consider enhancing the distinguishability in the feature augmentation but overlooking the in- herent formulation symmetry of these problems. In contrast, our proposed Orbit-based methods are symmetry- aware, where the associated augmented features are constructed explicitly based on the symmetry groups. As a result, the cardinality of the augmented feature space of our proposed Orbit and that of Orbit+ can be smaller, analyzed in Sec. 4.3.2 The remarkable improvement of the

---

Published as a conference paper at ICLR 2025
prediction accuracy of Orbit and Orbit+ demonstrates the superiority of the symmetry-aware feature augmentation and validates the effectiveness of our proposed guiding principles for constructing augmented features. Besides, one observe that Orbit+ generally attains a better Top-m% error performance than Orbit. This is in accordance with our expectation since Orbit+ leverages more symmetry information in constructing the augmented features and further reduces the cardinality of the feature space.
Table 2: Top-m% enrors (L) of different feature augmentation schemes.
BPP
BIP
SMSP
Methods
30%
50%
70%
90%
30%
50%
70%
90%
30%
50%
70%
90%
No-Aug
3.0
4.8
6.6
9.5
30.4
50.6
71.0
91.1
34.0
57.7
83.0
113.9
Uniform
0.0
0.4
2.4
6.4
4.8
15.9
44.9
80.2
18.5
34.7
53.3
80.0
Position
0.0
0.0
1.3
5.6
4.5
13.4
45.6
81.6
19.3
35.2
53.4
79.8
Orbit
0.0
1.3
4.3
3.6
8.6
39.0
75.7
0.0
1.5
17.9
51.1
Orbit +
0.0
0.0
0.9
4.3
3.2
5.5
39.4
79.2
0.0
1.0
14.9
50.3
In Fig. - the validation losses versus epochs of these baseline feature augmentation methods as well as our proposed Orbit and Orbit+ are presented. is evident that the attained validation loss after convergence satisfies Orbit+ < Orbit < Position < Uniform. This is consistent with the trend of the Top-m% errors in Table I Additionally, one can observe that the validation losses of Orbit and Orbit+ drop more quickly than those of the baselines. Specifically, Orbit+ merely takes around 20 epochs to reach the smallest loss over the BPP and BIP datasets, while Uniform and Position take around 30- ~ 40 epochs. The phenomenon is not surprising, since smaller cardinality of augmented space has the potential to achieve better training efficiency as analyzed in Section 4.] confirm that our proposed orbit-based feature augmentation not only provides more accurate solution predictions but also enhances the training efficiency of the learning model, offering competitive approach for solving ILPs with symmetries. Besides the main results, supplementary numerical results are available in Appendix A.7
The results in Fig. [ and Table 2
Uniformn
Position
B Orbit
Orbit
BPP
BIP
SMSP
0.35
0.9
0.35
Loss
Loos
0.8
0.7
0.25
0.3
0.6
60
100
Epoch
Epoch
Epoch
Figure 2: Validation losses of different schemes.
CONCLUSION AND LIMITATION
In this work, we demonstrated that the interaction between the formulation symmetry of ILPs and the permutation invariance and equivariance properties of GNNs limits the ability of classic GNN architectures to distinguish between symmetrie variables. Exploring the potential of feature aug- mentation to address this limitation, we proposed three guiding principles for constructing the aug- mented features. Based on these principles, we developed a new orbit-based feature augmentation scheme, which can distinctively enhance the prediction performance of GNNs for ILPs with sym- metry. There are several limitations of our orbit-based augmentation scheme, which also present opportunities for future research. First, our approach is specifically tailored for ILPs with formu- lation symmetry, and it is currently unknown whether it can be effectively applied to problems of other classes. Second, the principle of isomorphic consistency. which underpins method, is pri- marily applicable to supervised learning tasks where multiple label choices exist. These limitations highlight areas for further exploration and potential extension of our approach.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the National Key R&D Program of China under grant 2022YFA1003900. Akang Wang also acknowledges support from the National Natural Science Foundation of China (Grant No. 12301416), the Guangdong Basic and Applied Basic Re- search Foundation (Grant No. 100441555010366, the Shenzhen Science and Technology Program and the Longgang District Special Funds for Science and Ruoyu Sun also acknowledges support from the Hetao Shenzhen- Kong Science and Technology Innovation Cooperation Zone Project (No. the University Development Fund (UDF)1001491) at the Chinese University of Hong Kong, Shenzhen, the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B of Basic and Applied Basic Research (2023B0303000000), Qian Li also acknowledges support from Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project (No.HZQSWS- HHH.HHSSSSCCB---..... SCCCYB-2024016) Tsung- Chang acknowledges support from the Shenzhen Science and Technology Program (Grant No. ZDSYSS0023022691100000000
(Grant No.
Technology Innovation (LGKCSDPT202300))
NZQSWSSKCCYBB-2924000
and the Guangdong Major Project
REFERENCES
Stephen Boyd and Jacob Mattingley. Branch and bound methods. Notes for EE364b, Stanford University, 2006:07, 2007.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 2023.
Qian Chen, Tianjian Zhang, Linxin Yang, Qingyu Han, Akang Wang, Ruoyu Sun, Xiaodong Luo, and Tsung- Hui Chang. SymlLO: A symmetry-awar learning framework for integer linear op- timization. In The eighth Annual Conference Neural Information Processing Systems, 2024. URL http://xxxvv.roo orq/ abs 2409.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks, 2022.
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, et al. The scip optimization suite 7.0. 2020.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 competitions and demonstrations track, pp. 220-231. PMLR, 2022.
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, al. Miplib 2017: data- driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443 490, 2021.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang. Ruoyu Sun, and Xi- aodong Luo. A gan-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023.
Gabriele lommazzo, Claudia Ambrosio, Antonio Frangioni, and Leo Liberti. Learning to config- mathematical programming solvers by mathematical programming. In Learning and Intelli- gent Optimization: 14th International Conference, LION 14, Athens, Greece, May 24-28, 2020, Revised Selected Papers 14, pp. 377-389. Springer, 2020.

---

Published as a conference paper at ICLR 2025
Tommi Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical la- beling. In International Conference on Theory and Practice of Algorithms in (Computer) Systems, pp. 151-162. Springer, 2011.
Sékou-Oumar Kaba and Siamak Ravanbakhsh. Symmetry breaking and equivariant neural networks. arXiv preprint arXiv:2312.09016. 2023.
Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guid- ing combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10219-10227, 2022.
Hannah Lawrence, Vasco Portilheiro, Yan Zhang, and Sékou-Oumar Kaba. Improving equivariant networks with probabilistic symmetry breaking. In ICML 2024 Workshop on Geometry-groundee Representation Learning and Generative Modeling, 2024.
Li Liu and Qi Fan. Resource allocation optimization based on mixed integer linear programming in the multi-cloudlet environment. IEEE Access, 222533-245442 2018.
Paramet Luathep, Agachai Sumalee, William HK Lam, Zhi-Chun Li, and Hong K Lo. Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach. Transportation Research Part B: Methodological, 45(5):808 827, 2011 1.
François Margot. Pruning by isomorphism in branch- aranch-add-cut. Mathematical Programming. 94: 71-90, 2002.
François Margot, Exploiting orbits in symmetric ilp. Mathematical Programming. 98:3-21, 2003.
François Margot. Symmetry in integer linear programming. 50 Years of Integer Programming 1958- 2008: From the Early Years to the State-of-the-Art, pp. 647-686, 2009.
Brendan D McKay and Adolfo Piperno. Nauty and traces user's guide (version 2.5). Computer Science Department, Australian National University, Canberra, Australia, 2013.
Matthew Morris, Bernardo Cuenca Grau, and Ian Horrocks. Orbit-equivariant graph neural net- works. In The Twelfth International Conference Learning Representations, 2024. URL
net www.mmidddoae iddGkkoCcaa22
David R Morrison, Sheldon H Jacobson, Jason J Sauppe, and Edward C Sewell. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Opti- mization, 19:79-102, 2016.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint 2rXiv:2012.13349, 2020.
James Ostrowski, Jeff Linderoth, Fabrizio Rossi, and Stefano Smriglio. Constraint orbital branching. In Integer Programming and Combinatorial Optimization: 13th International Conference, IPCO 2008 Bertinoro, Italy, May 26-28, 2008 Proceedings 13, pp. 225-239- Springer, 2008
James Ostrowski, Jeff Linderoth, Fabrizio Rossi, and Stefano Smriglio. Orbital branching. Mathe- matical Programming. 126:147-178, 2011.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference machine learning. pp. 7758--17000 PMLR, 2022.
Yves Pochet and Laurence A Wolsey, Production planning by mixed integer programming, volume
149. Springer, 2006.
Jean-Francois Puget. Symmetry breaking using stabilizers. In International Conference on Princi- ples and Practice of Constraint Programming, pp. 585-599. Springer, 2003.
Jean- Cunn-Fraçços Puget. A comparison of sbds and dynamic lex constraints. Symmetry and Constraint Satisfaction Problems, pp. 56, 2006.
12

---

Published as a conference paper at ICLR 2025
Pierre Schaus, Pascal Van Hentenryck, Jean-Noël Monette, Carleton Coffrin, Laurent Michel, and Yves Deville. Solving steel mill slab problems with constraint-baad based techniques: Cp, Ins, and cbls. Constraints, 16:125-147, 2011.
Anita Schöbel. A model for the delay management problem based mixee-innege--poogamning Electronic notes in theoretical computer science, 50(1):1-10, 2001.
Petra Schwerin and Gerhard Wäscher. The bin bin-packing tin-packing problem: A problem generator and some numerical experiments with ftd packing and mtp. International transactions operational re- search, 4(5-6):377-389, 1997.
Tess E. Smidt, Mario Geiger, and Benjamin Kurt Miller. Finding symmetry breaking order parame- ters with euclidean neural networks. Physical Review Research, 3(1):L012002, 2021.
Jean-Paul Watson and David L Woodruff. Progressive hedging innovations for class of stochastic mixed-integer resource allocation problems. Computational Management Science, 8(4):355-370, 2011.
YuQing Xie and Tess Smidt. Equivariant symmetry breaking sets. arXiv preprint arXiv:240.006681, 2024.
Yan Zhang, David Zhang, Simon Lacoste-Julien, Gertjan Burghouts, and Cees GM Snoek. Multiset-quuivariant set prediction with approximate implicit differentiation. arXiv preprint arXiv:211..11193, 2021.
13

---

A'' and 77" (2) z²). As points on the ground truth Published as a conference paper at ICLR 2025
A APPENDIX
A.1 EXAMPLE OF CONNECTIONS BETWEEN ORBITS
Example 1. Consider a bin-packing problem with 3 items of sizes {1.3.5, 5) and up to 3 bins, each with capacity of The objective to minimize the number of bins used while ensuring the total size of items in each bin does not exceed its capacity. Let Tij be binary variable where Fig 1 if item is placed in bin j. and Yj be binary variable where Yj = if bin j is used. Then this problem can be formulated as:
min 31 + 1/2 + 1/3 249:911
s.t. + 222 + 23 = 1,1 1, = 1,2
(4a)
10ı, + 302j + 523z S 5y.. 1,2,3
(4b)
Faj Uj E {0,1)
(4c)
The formulation symmetries of this problem are arbitrary permutations acting the indices j.
Ø11
012
T13
namely, permutations acting on the columns of matrix X
22
T22
T23
There are orbits,
231
T32
T33
31
1/2
V/
each corresponding to a row of X. In the basic orbit-based feature augmentation approach described in Algorithm ! the augmented features added the variables in each column of can be distinct. However, due to the symmetries inherent in this problem, each column should be treated as an indi- visible unit. Consequently, the features added different variables within the same column should be identical. Specifically, following Orbit+, we only need to sample zk, h = 1, from {1, 2,3 for the variables in the first row of and applics 21 = [21, 22, 23] to the variables the other rows. The attained augmented feature associated with the variables
[X1,:: N...X2.. X3, X will be Zot = = 2 2T IT]T. In comparison, following Orbit, the attained augmented feature No = [ X2 23 21 where the elements of each Z,, 1...., are individually sampled from (1.2.3). Obviously, the cardinality of the space of 2,- is smaller.
A.2 MORE EXPLANATION OF ISOMORPHIC CONSISTENCY IN SECTION 41
Let f* denote the ground truth function for the learning task described in Section key motiva- tion for using GNNs to approximate f is that f" exhibits permutation invariance and permutation equivariance, i.e., VT E Su, (T) = x² (fo(-)), and Vo E fo = f.).). However, introducing additional features may disrupt these properties.
To prevent this from happening, we examine the conditions that need to satisfied under these two properties. Specifically, let (A, σ) and (A'', x') be two training samples with (a'(AA) = A' for some и S, and Sm (i.e., ("" function /", these two training samples equivalent I' (*()) and ("²' ø'. Due the permutation equivariance and invariance of 1", we obtain
お' = I" 1 (" (A))) = x("(( = म. -.))
In summary, if 3m E S, and a E Sm such that N (A)() = A', then T²) z' = x'(x)= x' should hold.
A.3 EXAMPLES FOR THE PRINCIPLE OF ISOMORPHIC CONSISTENCY
Consider two isomorphic instances as follows:
min
3i + T2 + 323
(5)
s.t. 31 + 32
T2, T3 E {0.1)
14

---

Published as a conference paper at ICLR 2025
min R1:82193
321 + 22 + 23
(6)
s.t. 22 + I3 21, 22,32,13 {0,
Let A represent the first instance and A' represent the second one, then x (A'( A' with
: (1) = 3, (3) (2) 2 and o (11 1. The label of A is x 0.1.0] and that of
A' is a' = 10,0,1] Assume the augmented features are z = [,,2,0] for and = [0,2, 1]
1
17
T 1
17
for A'. Correspondingly, Ā
1 3
and A'
3
1
0
It can be easily verified
1 2
0
0_
that the property of distinguishability is satisfied by both A and A'. However, is evident that T" (z) z' but TT" (x) + ø', so that the property of isomorphic consistency is violated. From the perspective of GNN, A and A'' are equivalent since (=) z'. However, the two instances (A, æ) and (A', æ') have different labels as =*()) * æ'. This will result in 'conflict' samples, which will mislead the prediction of GNNs to diverge from the correct solutions.
A.4 PROOF OF PROPOSITION I
Without loss of generality, assume the loss function E(-) 2 O permutation-invariin (i.e., (a), (b)) E(a, b)) and possesses the identity property (i.e., l(a, b) 0 = = b. examples of such loss functions include mean mean-squared loss and cross-entropy loss.).
Since E Sn is formulation symmetry, there exists E Sm such that N (o' (A)) A. Besides, fo has permutation equivariance and invariance properties, so we have fo(A) = fo( (A))) x" r=(f(o"(AA)) (A))) л" T' (A)) ie., fo(A), fo(A)=(1)- Further, Vi,j O, there exists E G such that (i). so [e(A), = So(A)
Proof:
A.5 PROOF OF COROLLARY
Proof: (counter example) Consider an ILP s = min {xa 11 + = 11,
E {0,1));
it has permutation symmetry (11 2, (2) 13x(3) 3) and two optimal solutions (0, 1), (1.0). Since indices and 2 can be permuted, thus and 2 are in the same orbit, and fo(s): fo())2. However, both the two optimal solutions (0, 1, 0) and 01,0, have distinct values for 1j and x2. Therefore, fa cannot predict any optimal solution of s.
A.6 PROOF OF PROPOSITION 2
Proof: Consider two samples (A, and (A', a') where 3ा Sn, such that ('A) A', and (2) z'. Accordingly, (A)) A'. After adding augmented features, the total loss of these two samples is (A), ((fo x'). For the second term, it will hold true (A)( Ø') = E(T (fo(). first equality holds since A and A'' two isomorphic instances. The second equality holds as fo is permutation-invarian
that ((fo(A)),
= L(fo(A), (z')) where the
and the third equality holds as E(-) is vermutation-invariann and m bijection. If the principle of isomorphic consistency violated, then π T'(x) * x', namely I * (z") In this case, given either term in L being O, the other term will be positive due to the identity property of f()). Correspondingly. L = (A), σ) ((fo(A), (Λ²) - > 0.
A.7 ADDITIONAL NUMERICAL RESULTS
we expand our analysis to incorporate two additional evaluation metrics beyond Top-m% errors as follows.
Objective values (L) comparing to the ILP solver Instead of directly using the rounded solutions for calculations-ssie since they often infeasible- leverage these predictions initial points to expedite the solving process of ILP solvers(Nair et al.) 2020; Khalil et al.) [022] Han et al.) 2023). Consistent with established practices, we integrate predictions from the trained models enhance
15

---

Published as a conference paper at ICLR 2025
the ILP solver CPLEX, following the methodology outlined in Nair al. 2020 shown in Table 3 and Table 4 for datasets BIP and SMSP, respectively. Note that the dataset BPP excluded, as its instances can be solved in matter of seconds.
The results
Table 3: Objective values v.s. solving time BIP
100s
200s
300s
400s
500s
600s
CPLEX
16.9
16.2
15.8
15.5
15.3
13.2
CPLEX "Orbit+"
15.5
15.1
14.9
14.8
14.7
14.6
Table Objective values v.s. solving time on SMSP
100s
200s
300s
400s
500s
600s
CPLEX
37.8
25.2
13.6
12.1
11.3
11.0
CPLEX "Orbit+"
13.7
13.1
12.3
11.6
11.1
10.7
From these results, we observe that our augmentation scheme yields better objective values while requiring less computational time.
Constraint violations ()) We also report the total violation of model prediction & with respect to the constraint Ab < b, i... the summation of positive elements Ab b. The violation of predictions from different models is summarized in Table
Table Constrain violations.
BIP
SMSP
Uniform
27.84
852.23
Position
22.12
933.76
Orbit
12.89
453.87
Orbit+
3.68
329.74
From the results, we find that our methods (Orbit, Orbit+) produce predictions with significantly less constraint violation, further demonstrating the effectiveness of our approach.
A.8 SYMMETRY DETECTION
Detecting symmetry group G for ILP is complex and can be computationally intensive. Fortu- nately, over the years, well-established methods and software tools such as Bliss(Junttila & Kaski 2011) and Nauty(McKay & Piperno 2013) have been developed for efficiently detecting the sym- metries of ILPs, as well as their orbits. In our experiments, the orbits of all instances have been detected. In Table 6 report the average time taken detect symmetry groups in the considered datasets using Bliss, with the size of the detected subgroup G represented by its logarithmic value logıo [G].
Table 6: Average time of symmetry detection.
BPP
BIP
SMSP
# of Var.
420
1083
23000
log |G]
6.9
6.6
213.1
time(s)
0.05
0.06
6.11
From the results, we observe that for smaller problems like BPP and BIP, symmetry detection re- quires negligible computational time. Even for larger problems, such SMSP, symmetry group detection is still accomplished within few seconds, demonstrating the feasibility of our approach for complex instances.
16


Reviews:
[{"review_id": "XURSoABc04", "reviewer": "Reviewer_zedB", "summary": "The authors study the problem of solving Integer Linear Programs (ILPs) with symmetry among variables. They first show that if a permutation from the set of all variable permutations is a formulation symmetry of the ILP, then under an assumption of permutation equivalence and invariance for the GNN, the network cannot predict the optimal solution of the ILP.\n\nTo address this, they propose a feature augmentation algorithm that assigns unique augmented features to each orbit, sampling a distinct feature value within an orbit without replacement. They compare their methods against previously proposed augmentation schemes empirically and based on some principles for three ILP benchmark problems.", "questions": "Could the authors comment on the computational complexity of detecting symmetries and how the established methods help handle it?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Their method appears to perform better in terms of their proposed metric than existing methods on certain tasks. They also introduce the problem clearly, making it easily understandable for someone outside the field, while establishing a good motivation through negative results about GNNs and formulation symmetries.", "weaknesses": "They don't discuss any limitation of their orbit-based augmentation, making their method's application scope appear narrow restricting to ILPs with formulation symmetry. \n\nAdditionally, the approach relies on detecting symmetry groups and orbits, which as they note may be computationally expensive.  It would also be interesting to see how their method performs for different evaluation metrics (maybe beyond $\\ell_1$ distances). \n\nAs this area is new to me, their contributions do not seem sufficiently novel in terms of the algorithm, and the experiments provided also seem limited and hence I recommend a reject but with a confidence score of 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mx90whQXLr", "reviewer": "Reviewer_GLPM", "summary": "This paper improves a weakness of graph network approaches for predicting the solutions of integer linear programs (ILPs) with symmetric variables. Because graph networks are permutation equivariant, they cannot distinguish between exchangeable variables in the ILPs (or more concretely, variables such that, when permuted, the cost constraint is still satisfied and the objective is unchanged). The authors use feature augmentation to break the symmetries between these equivalent variables, specifically emphasizing distinguishability, “isomorphic consistency”, and “augmentation parsimony”. Past works have used feature augmentation to break these symmetries, but without adhering to these principles. They demonstrate the effectiveness of their techniques relative to alternatives on solving synthetic ILPs, with training data generated by a classical solver.", "questions": "Questions:\n1. *Value of ML versus classical ILP method*: The authors motivate the use of GNNs for ILPs by referencing recent works which use GNNs as part of the solution process, e.g. as an oracle in branch-and-bound algorithms or predicting initial solutions. However, the experiments they run directly output solutions of the input ILPs, and there is no comparison to classical ILP solvers (eg int terms of accuracy), because the training data itself is generated by the ILP solver SCIP. Thus, my question is: what value does machine learning add to these problems? For example, are the trained models’ forward passes on test data supposed to be faster than the solver? (If so, does this take into account the time to detect the symmetry of the input ILP?) Does the noted symmetry-breaking problem arise when ML is used to predict branching decisions or node selections?\n2. *Choice of loss function in experiments*: why use a loss function that tries to learn the exact solution instance, when there are several degenerate, “equally good” solutions? It seems far more natural to use the objective function $c^Tx$ of the ILP itself, or the fraction of instances that satisfy the constraint $Ax\\leq b$, over $x$ from the test set.\n3. *Motivation for “isomorphic consistency” principle*: The isomorphic consistency principle (which is dataset-dependent) strikes me as odd — the whole problem explored in this paper is that it is not even **possible** to satisfy while outputting optimal solutions, except for on certain training sets. Can the authors elaborate on this? IN particular, if one uses a loss function like the one suggested above, I can’t tell what the value of isomorphic consistency is.\n4. *Practicalities of the experiments*: Line 468 states that multiple augmentations need to be drawn per sample. Is this done for baselines too? Also, is there an ablation result for the importance of using SymILO to enforce isomorphic consistency? Does this remain under the choice of loss function suggested above?\n5. *Minor clarification about formulation symmetry definition*: As defined around line 118, a formulation symmetry “retains the description $Ax \\leq b$”. One way of achieving this is if $Ag(x)=Ax$, indeed this is what I would have expected as the definition. Is this more accurate?\nIn the methodology paragraph, around lines 228-230, the paper says “…the approach did not exploit the underlying symmetry properties, leading to suboptimal performance on ILPs with strong symmetries”. What does this mean? The paper would be improved by making this claim precise, and including references to evidence (eg a specific result in the cited paper).\n6. Why not use MIPLIB, the dataset cited in the first paragraph of the paper, in the experiments? For the datasets used in experiments, what fraction of inputs exhibit no symmetric variables at all?\n\nTypos:\nAs I read through the paper, I noticed some minor typos. These did not affect my evaluation of the paper, but I’m noting them here in case it’s useful to the authors.\n* line 74: “fully use of” —> “full use of”\n* Subtitle on line 191: “issues occur”, not “occurred”\n* Line 207: “correspond”, not “corresponds”\n* Line 218: “oribit”\n* Line 219: “have distinct values”, not “has distinct values”\n* Line 445: “cloest”\n\nMinor notation/writing notes:\n* Definition 3 should define that $I \\in I^n$ and should also define $\\mathcal{O}_i$. \n* The standard term for Assumption 1 is permutation equivariance, not equivalence\n* It would be good to explain lines 322-323 (“Accordingly…other orbits”) in mathematically precise language\n\nOn the writing side, I would also recommend making the “Motivations” paragraph more concrete.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper addresses a meaningful issue (symmetry-breaking in integer linear programs) in a new way (using inputs to GNNs that break only the required orbit symmetries, in accordance with the three defined desiderata). Although I believe these two pieces are individually not new (see “weaknesses”), their combination is. The “Orbit+” approach is also a novel way of enhancing “augmentation parsimony”. The paper is generally clear, and the writing style and notations are both enjoyable to read. Their experimental results on the chosen tasks beat the chosen ML baselines. Although I am not convinced by the necessity of isomorphic consistency for most applications, in which a logical loss function can be chosen (which is unaffected by swapping equivalent nodes), the use of SymILO to enforce it by adjusting training labels is also new.", "weaknesses": "I think the biggest weakness of this paper is that, in short, many of its central ideas have already been introduced and (in some cases) thoroughly explored in papers of which the authors seem unaware. (This is understandable, given that they do not appear in the ILP literature and use different terminology to describe the problem, but nonetheless they exist — I hope the authors may be inspired by the perspectives of these papers, and can also articulate the novelty of their work relative to them.) This line of work (see the references below; although not the earliest, [2] or [4] may be the most accessible starting points) goes by the name “symmetry-breaking”, and articulates the precise issue that the authors encounter for ILPs, but in a much more general way, for all group equivariant networks. The principles of distinguishability and augmentation parsimony are explored under different names, e.g. in [3]. There is a related line of work on breaking symmetries of sets, termed “multiset equivariance” [5]. Works such as these and [4] make clear subtleties of the problem that aren’t discussed in this paper, such as the difference between the graph automorphism group and the node orbits, and articulate methods for addressing the equivalent nodes of ILPs in ways that subsume the method presented here.\n\nI believe that orbit-equivariant graph neural networks [6] are also a slightly more fleshed out version of the “Orbit” approach. \n\nAs noted under questions, I also find the discussion of isomorphic consistency confusing, as it is (assuming I understand correctly) not well-motivated under orbit-invariant loss functions, and importantly, not necessarily even possible to achieve. Is “relaxed equivariance” [2] more suitable? \n\nFinally, as also noted under questions, there seem to be weaknesses with the experiments — namely, the choice of loss function, and the premise/lack of comparison to non-ML baselines. \n\nReferences:\n1. Smidt, T. E., Geiger, M., and Miller, B. K. Finding symmetry breaking order parameters with euclidean neural networks. Phys. Rev. Research, 3: L012002, Jan 2021. doi: 10.1103/PhysRevResearch\n2. Kaba, S.-O. and Ravanbakhsh, S. Symmetry breaking and equivariant neural networks. In Symmetry and Geometry in Neural Representations Workshop, NeurIPS, 2023.\n3. Xie, Y. and Smidt, T. Equivariant symmetry breaking sets. TMLR 2024.\n4. Hannah Lawrence, Vasco Portilheiro, Yan Zhang, and Sekou-Oumar Kaba. Improving equivariant networks with probabilistic symmetry breaking. In ICML 2024 Workshop on Geometry-grounded Representation Learning and Generative Modeling, 2024.\n5. Zhang, Y., Zhang, D. W., Lacoste-Julien, S., Burghouts, G. J., and Snoek, C. G. M. Multiset-equivariant set prediction with approximate implicit differentiation. In International Conference on Learning Representations, 2022.\n6. Morris, M., Grau, B. C., & Horrocks, I. (2024). Orbit-equivariant graph neural networks. ICLR 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J2fZqm3ZzM", "reviewer": "Reviewer_feSQ", "summary": "This paper proposes to augment the vertice features in ILP graph representation based on orbit of the symmetry group. Some theory is provided and numerical results are conducted with the comparison with the random feature technique (Chen et al. 2022) and the positional ID technique (Han et al. 2023).", "questions": "None", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is in general well-written and is easy to follow.\n\n2. The idea of augmenting features based on orbits is reasonable. I agree with the authors that only vertices in the same orbit need to be separated with augmented features, and the cardinality of the augmented feature space is much smaller than $n!$ if the number of orbits is much larger than one.\n\n3. The reported numerical results look better than baseline methods.", "weaknesses": "1. There is no comparison with conventional methods based on symmetry group and orbits, such as Ostrowski et al. (2011) cited by the authors. In addition to Ostrowski et al. (2011), there should actually be a much richer literature in this direction.\n\n2. There is no report on the cost of computing the symmetry group. I expect to see a trade-off between the size of the symmetry group and the improvement from \"no augmentation\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sg6vg2sBqv", "reviewer": "Reviewer_EWnQ", "summary": "The authors propose a novel feature augmentation method for ILP's with symmetries that are described by bipartite graphs for solving with GNN's. The augmentations obey some important symmetry properties but are also more parsimonious than existing methods. Empirical results suggest that these augmentations help the GNN's break the symmetry better than competing methods.", "questions": "Figure 1 appears too soon, before the map between ILP and graphs...\nI don't think you need to define a permutation.\nI don't understand the h_i^v definitions in 2.3, and how they're related to c, b, and A in the original problem? Isn't c_i a scalar? How is this a feature vector? Can you please clarify the entries of \\mathcal{A} and how they relate to the bipartite graph? (Are you using the columns and rows of \\mathcal{A} as the feature vectors for the nodes V and W? If this is true, I think it should be explicitly stated somewhere.) \nI think you mean {V,W,E} as the bipartite graph? (You have C in one place and W in another)\nIn figure 1, I don't yet understand why the GNN must make x1 and x2 equal? How was the integer constraint enforced?\nThe notation in proposition 1 seems a bit overkill - this seems like a simple & intuitive result, so perhaps this proof can be made simpler. \nAm I missing an additional assumption of Proposition 1 that the initial feature embedding of points in the same orbit are equal? (Otherwise this proposition extends to the proposal in section 4?)\nCorollary 1 seems overly general (and not quite correct). I think you mean that it cannot ALWAYS predict the optimal solution. Of course there are instances that it can solve correctly (like min 0 s.t. [no constraints])\nThe number of instances in the problems 5.1 is quite low, isn't it?\nHow is the GNN enforcing integer constraints?\nDo you have any other metrics of comparison? Don't you also care if the rounded solution is any good? (It's OK if it's not -- I'm just curious.)\nMinor: \"By some mathematical derivations\" is an awkward phrase; typo \"cloest\" on page 9.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main idea in Section 4.2 is explained well. The numerical results are decent and convey the practical benefits of the method. The introduction is also nicely written.", "weaknesses": "While the numerical results do suggest that the method helps break symmetries better than others, it is hard to tell if this makes a difference in the end result (objective of rounded solution). I think such a comparison should be added (either way). A more complete description or explanation of the augmentation procedure in general could be useful for those not in the field. Some minor improvement for minor writing weaknesses are suggested below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)