Research map / Learning theory and algorithms / Combinatorial and search optimization
SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SymILO, a symmetry-aware training framework that jointly optimizes GNN weights and solution permutations (alternating minimization) to predict optimal ILP solutions, improving downstream primal gaps on four symmetric benchmarks.
Problem
Supervised learning for predicting optimal solutions of integer linear programs is hurt when instances are symmetric, because the label (one of many equivalent optimal solutions) is chosen arbitrarily, producing noisy training targets.
Approach
Treat the permutation mapping each training label to an equivalent optimal solution as a learnable variable, and alternate between optimizing these permutations (exact via enumeration for small cyclic/dihedral groups, or LP relaxation for symmetric groups) and gradient steps on the GNN weights.
Key results
- Symmetry-aware training yields average primal-gap gains of 50.3% (fix-and-optimize with ND), 66.5% (local branching with PS), and 45.4% (node selection with MIP-GNN) at 800 seconds.
- Top-10% error on PESP drops from 7.5 to 0.1 and on SMSP from 0.6 to 0.0 for the symmetry-aware model versus the classic model.
- On PESPD local branching, the primal gap falls from 3.442 to 0.127 with SymILO, a 96.3% gain.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train with symmetry-aware risk instead of classic empirical risk | GNN solution prediction · IP | Top-10% error: 0.8 ±0.8 -> 0.4 ±0.6 | Helped |
| train with symmetry-aware risk instead of classic empirical risk | GNN solution prediction · SMSP | Top-30% error: 5.3± 2.6 -> 0.1 ± 0.1 | Helped |
| train with symmetry-aware risk instead of classic empirical risk | GNN solution prediction · PESP | Top-90% error: 1.6k±30 -> 212±23 | Helped |
| train with symmetry-aware risk instead of classic empirical risk | GNN solution prediction · PESPD | Top-10% error: 87.4±41 -> 12.7±4.8 | Helped |
| use symmetry-aware training rather than the classic baseline | fix and optimize · IP | relative primal gap: 0.201 -> 0.124 | Helped |
| use symmetry-aware training rather than the classic baseline | local branching · IP | relative primal gap: 0.168 -> 0.102 | Helped |
| use symmetry-aware training rather than the classic baseline | node selection · IP | relative primal gap: 0.312 -> 0.190 | Helped |
| use symmetry-aware training rather than the classic baseline | fix and optimize · SMSP | relative primal gap: 0.300 -> 0.180 | Helped |
| use symmetry-aware training rather than the classic baseline | local branching · PESP | relative primal gap: 0.306 -> 0.000 | Helped |
| use symmetry-aware training rather than the classic baseline | node selection · PESPD | relative primal gap: 3.755 -> 3.006 | Helped |
| use symmetry-aware training rather than the classic baseline | fix and optimize · PESPD | relative primal gap: 2.389 -> 0.404 | Helped |
| use symmetry-aware training rather than the classic baseline | local branching · PESPD | relative primal gap: 3.442 -> 0.127 | Helped |
Surprising findings
- Node selection shows modest gains because its callback interaction with CPLEX slows the solver, according to the authors.
- The symmetric-group permutation subproblem relaxed to an LP yields integral optimal solutions (total unimodularity), so it is exact for squared-error and BCE losses.
Limitations
- Requires problem-specific formulations for permutation optimization, so it does not directly apply to other symmetry groups.
- For large instances with complex symmetry groups, the permutation subproblems can significantly slow training.
Experimental setup
Datasets: IP (NeurIPS ML4CO 2021 generator) SMSP (steel mill slab) PESPlib (perturbed for PESP and PESPD)
Benchmarks: IP SMSP PESP PESPD
Metrics: Top-m% error relative primal gap gain over baseline paired t-test p-value
Baselines: Neural Diving (ND) predict-and-search (PS) MIP-GNN Tuned CPLEX
Builds on: Neural Diving predict-and-search MIP-GNN bipartite graph representation of MILP
Closest papers by meaning
- When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach (ICLR 2025 · similarity 0.89)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.86)
- BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks (NeurIPS 2025 · similarity 0.86)
- Contrastive Predict-and-Search for Mixed Integer Linear Programs (ICML 2024 · similarity 0.85)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.85)
- Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.