- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper investigates the insufficient consideration of rescaling symmetry in existing GNN-based approaches for solving linear programming problems. To address this limitation, a model-agnostic canonicalization framework is proposed, which maps rescaling-equivalent LP instances to a common canonical representation, applies existing GNNs for prediction, and transforms the predictions back to the original coordinates, thereby ensuring both permutation and rescaling equivariance.
Critical strengths
This work extends existing research on the sensitivity of GNNs for linear programming to numerical rescaling. The theoretical analysis is comprehensive and provides certain guarantees for the proposed method.
Critical weaknesses
The practical significance of rescaling in LP appears somewhat limited. On the one hand, small and medium-sized LP problems are relatively easy to solve. It remains unclear whether the proposed method can be extended to large-scale LP problems or more complex combinatorial optimization problems. On the other hand, it would be valuable to integrate the proposed method into existing GNN-based LP and MILP solving frameworks and evaluate its impact on the performance of state-of-the-art methods.
Questions for authors
- How does the proposed rescaling-based representation differ from, or improve upon, the bipartite graph representations used in seminal works on LP and MILP? Could the issues identified in this paper be addressed through appropriate feature normalization in bipartite graph representations? Can the advantages of the proposed method be demonstrated experimentally?
- Numerous studies have explored GNN-based approaches for solving LP and MILP in recent years, and several representative works are discussed in the related work section. How much performance improvement can these existing methods achieve on their original tasks when incorporating the proposed rescaling technique? Could further experiments demonstrate its practical benefits?
- The current evaluation is limited to linear programming, which is solvable in polynomial time. Is the proposed method applicable to large-scale linear programming problems? Could the proposed framework be extended to NP-hard combinatorial optimization problems, such as MILP or TSP? Additional experiments on these problems would help demonstrate its broader applicability and practical value.
8 comments
Our response to reviewer jBu8
Question 1. How does the proposed rescaling-based representation differ from, or improve upon, the bipartite graph representations used in seminal works on LP and MILP? Could the issues identified in this paper be addressed through appropriate feature normalization in bipartite graph representations? Can the advantages of the proposed method be demonstrated experimentally?
Thank you for this insightful question, and we would like to address it by following parts:
-
Canonicalization and the bipartite representation operate at different levels and are complementary: The bipartite graph representation determines how an LP is encoded for the GNN, i.e., which nodes, edges, and features represent its variables, constraints, and coefficients. Canonicalization determines which LP from the rescaling orbit is encoded. Before encoding, it maps every instance to a single canonical representative, so that all rescaled formulations of the same LP become one identical input. After prediction, it maps the output back to the original coordinates (through additional rescaling masks). Canonicalization is therefore not a replacement for the bipartite representation. It wraps around it, applies at both training and inference time, and leaves the graph construction and the backbone unchanged. In our experiments, the backbones process the standard bipartite graph of the canonicalized LP. When the backbone is permutation equivariant to the graph representation and the graph representation is permutation equivariant to the LPs (which is ensured by the bipartite graph representation), the resulting model is equivariant to both permutations and the rescalings considered in our framework by our design. Thus, a prediction learned for one instance automatically transfers to its equivalent rescaled and permuted instances, which makes generalization better. So the improvement comes from leveraging more prior information to make the learning smarter, which is the central topic of invariant and equivariant learning.
-
Numerical normalization alone couldn't fully exploit the inductive bias:
-
On the one hand, traditional solver preprocessing techniques on LPs (hence on the corresponding bipartite graph representations) cannot enforce the desired symmetry. This is because the target of solver preprocessing is to get better numerical conditions: even if two input LPs are rescaling-equivariant, their ending LPs after the preprocessing could usually be different, with both better numerical conditions. Other naive normalization also fails to enforce the full rescaling symmetries, like just simply normalizing each row or each column.
-
On the other hand, as proved by our newly presented theorem, neither input-feature normalizing like z-score nor normalizations in the network (RMSNorm, LayerNorm, BatchNorm) could enforce exact rescaling equivalence without the cost of degeneracy. These results show that rescaling symmetry could not be fully exploited by existing normalization techniques, which highlights the need for canonicalization techniques.
-
-
Our original experiments are done based on existing bipartite graph representations over the representative architectures: original LP-GNN[3] and recent implicit-model[6]. As seen in the following response, the canonicalization generally achieves better prediction accuracy, lower constraint violations, and better objective gaps, compared with the original baseline or typical preprocessing. Moreover, when meeting the unseen problems with different numerical scales, our canonicalization could also predict better solutions with high quality.
Our response to reviewer jBu8
Question 2. Numerous studies have explored GNN-based approaches for solving LP and MILP in recent years, and several representative works are discussed in the related work section. How much performance improvement can these existing methods achieve on their original tasks when incorporating the proposed rescaling technique? Could further experiments demonstrate its practical benefits?
The original task of the GNN-based LP solvers discussed in our related work is to predict an optimal solution from the bipartite graph of an LP. We evaluate canonicalization on exactly this task, with two backbones chosen to cover both the foundation of this line of work and its recent developments. The first is the standard bipartite message-passing GNN [3][7]. Most subsequent GNN-based LP and MILP methods build on this architecture, so improvements on it are indicative of improvements for the broader family. The second is the implicit GNN of [6] (ICLR 2026), one of the recent architectures for LP solution prediction. Instead of stacking a fixed number of layers, it iterates a weight-tied message-passing operator to an equilibrium.
As demonstrated in the discussions above, we evaluate the proposed rescaling on direct LP solution prediction using LP-GNN and an implicit GNN. We train each variant using the same composite loss, , which combines normalized squared measures of solution error, constraint violation, and objective gap in the original LP coordinates. We report before feasibility projection here to quantify how closely the model predicts a reference optimum, as this is the original task of the two baselines. FullB-cano reduced this loss on all nine distributions for both backbones compared with no preprocessing, as seen in the following table. (In the table, each pair shows the three-seed mean without preprocessing followed by the mean with FullB-cano.) Among the seven preprocessing methods in Tables 10 and 11 of the manuscript, it achieved the lowest mean supervised loss on eight of nine distributions for LP-GNN and seven of nine for the implicit GNN. Same trends appear on raw constraint violation and objective gap as well, which further validate our method's practical benefits.
| Dataset | LP-GNN | Implicit GNN |
|---|---|---|
| CA | 0.0166 → 0.0088 (47.0%) | 0.0044 → 0.0037 (15.9%) |
| SC | 0.0282 → 0.0127 (55.0%) | 0.0049 → 0.0043 (12.2%) |
| OPF-57 | 0.0191 → 0.0057 (70.2%) | 0.0070 → 0.0016 (77.1%) |
| OPF-118 | 0.0848 → 0.0712 (16.0%) | 0.0683 → 0.0570 (16.5%) |
| OPF-300 | 0.1654 → 0.1239 (25.1%) | 0.1108 → 0.0935 (15.6%) |
| MCF | 0.0432 → 0.0403 (6.7%) | 0.0199 → 0.0187 (6.0%) |
| CFLP | 0.0078 → 0.0071 (9.0%) | 0.0151 → 0.0022 (85.4%) |
| IS | 0.2447 → 0.0799 (67.3%) | 0.0734 → 0.0732 (0.3%) |
| NETLIB | 0.1694 → 0.1288 (24.0%) | 0.2389 → 0.1105 (53.7%) |
Meanwhile, under shifts in the ranges used to sample LP coefficients, FullB-cano or -cano achieved the lowest mean post-projection composite loss in all 15 dataset–shift combinations for each backbone (Tables 3 and 13). All these results confirming our canonicalization helps both ID and OOD performance of existing works.
Our response to reviewer jBu8
We thank the reviewer for the careful reading and for recognizing the comprehensiveness of our theoretical analysis. We also appreciate the suggestions to clarify the relationship to existing graph representations and strengthen the evidence for practical applicability.
We understand your concerns, and we are happy to discuss about it. First, we would like to emphasize the significance of LPs, which remain a cornerstone of mathematical optimization and a fundamental building block for more complex optimization problems. Developing efficient methods for solving LPs continues to be an active research area in both traditional optimization and learning to optimize. Moreover, LPs have historically served as a starting point for techniques and theories that were subsequently extended to broader problem classes. A prominent example is the modern theory of polynomial-time interior-point methods: following Karmarkar's breakthrough [1] for LPs, these methods were extended to broader classes of convex optimization through the framework of Nesterov and Nemirovskii [2]. Similarly, within GNN-based learning to optimize, the LP-GNN representability analysis of [3] was subsequently extended to convex and mixed-integer QPs by [4][5].
Regarding practical applicability, we would like to clarify that our canonicalization framework is model-agnostic and can be directly incorporated into existing GNN-based LP solvers. In fact, our experiments already evaluate its integration with both the famous LP-GNN backbone of [3] and the recent implicit GNN backbone of [6], both of which adopt the standard variable–constraint bipartite graph representation. Across nine LP distributions, we systematically compare canonicalization against the original backbones, data augmentation, coefficient normalization, and numerical prescaling, demonstrating substantial improvements in predicting high-quality solutions and robustness to numerical-scale shifts. Moreover, to further address your concern, this revision adds a larger benchmark: continuous electricity–hydrogen planning LPs from the energy-system modeling framework FINE. Each instance has 10,538 variables, 19,619 constraints (excluding variable bounds), and 54,796 nonzero matrix entries, which is roughly 10× larger than the largest instances in our original benchmarks in each of these three measures. At this scale the benefit of canonicalization grows rather than fades. FullB-cano reduces the in-distribution loss by 73.5% for LP-GNN (0.1069 → 0.0283) and by 63.8% for the implicit GNN (0.2891 → 0.1047). Under the strongest scale shift (OOD-3), FullB-cano reduces the LP-GNN loss from 0.6345 to 0.3284. For both backbones, a canonicalizer (FullB-cano, or the quadratic variant introduced in Section 8.4 of the manuscript) achieves the lowest loss on the ID test set and on all three OOD splits.