acceptodds
Under review as a conference paper at ICLR 2027

Rescaling Matters: Beyond Permutation Equivariance in Graph Neural Networks for Linear Programs

Abstract

Graph neural networks (GNNs) have proven efficient for solving optimization problems, particularly linear programming (LP), largely because they respect a fundamental symmetry: LPs are equivariant to permutations of their variables and constraints, and GNNs are permutation-equivariant by design. However, permutation symmetry represents only one class of important LP symmetries. LPs also remain equivalent under positive rescaling of the objective, constraint rows, and variables-a structure largely ignored by existing GNN-based solvers. We show this omission is structural: any traditional GNN that is exactly rescaling-equivariant must entirely discard the affected LP coefficients, which carry information essential for prediction. To overcome this limitation, we introduce canonicalization for LP, a model-agnostic pipeline that maps each instance to a single canonical representative of its rescaling-equivalent formulations, applies a permutation-equivariant GNN, and transforms the prediction back to the original coordinates. The resulting model is equivariant to both permutations and rescalings, without sacrificing the expressive power of the backbone. We prove that every LP admits such a canonicalization, and compute it via a unified energy-based objective, solved by smooth, unconstrained optimization with per-iteration cost linear in the number of nonzero coefficients. Finally, experiments across LP distributions and GNN backbones confirm our symmetry guarantees, and show that canonicalization generally improves in-distribution accuracy and consistently improves robustness to coefficient ranges unseen during training, at modest overhead.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
equivariance and invariance, canonicalization, graph neural network, learning with symmetries, linear program, geometric deep learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_jBu8OpenReview ↗
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
  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?
  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?
  3. 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
AuthorsOpenReview ↗

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.

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.

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×\mathbf{10 \times} 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 →\rightarrow 0.0283) and by 63.8% for the implicit GNN (0.2891 →\rightarrow 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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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, Lsup+Lfeas+0.1Lobj\mathcal{L}{\mathrm{sup}}+\mathcal{L}{\mathrm{feas}}+0.1\mathcal{L}{\mathrm{obj}}, which combines normalized squared measures of solution error, constraint violation, and objective gap in the original LP coordinates. We report Lsup\mathcal{L}{\mathrm{sup}} 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.

DatasetLP-GNNImplicit GNN
CA0.0166 → 0.0088 (47.0%)0.0044 → 0.0037 (15.9%)
SC0.0282 → 0.0127 (55.0%)0.0049 → 0.0043 (12.2%)
OPF-570.0191 → 0.0057 (70.2%)0.0070 → 0.0016 (77.1%)
OPF-1180.0848 → 0.0712 (16.0%)0.0683 → 0.0570 (16.5%)
OPF-3000.1654 → 0.1239 (25.1%)0.1108 → 0.0935 (15.6%)
MCF0.0432 → 0.0403 (6.7%)0.0199 → 0.0187 (6.0%)
CFLP0.0078 → 0.0071 (9.0%)0.0151 → 0.0022 (85.4%)
IS0.2447 → 0.0799 (67.3%)0.0734 → 0.0732 (0.3%)
NETLIB0.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 β\beta-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.

Reviewer_x6VCOpenReview ↗
Rating
1
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a symmetry that ordinary permutation-equivariant GNNs do not explicitly enforce when predicting linear programming solutions: rescaling of objectives, constraints, and variables.

It proves degeneracy results for specified neural architectures under exact rescaling symmetry. It then proposes mapping each LP to a canonical representative, predicting in that representation, and transforming the prediction back. The theory covers compatibility with permutations and the existence and regularity of canonical representatives. It also provides a mask that resolves ambiguity in restoring predictions and an approximation guarantee for a canonicalization-induced optimal-solution selector.

Experiments compare seven preprocessing choices across nine LP distributions and two GNN backbones. The proposed methods generally improve prediction error and show substantial gains under the tested numerical distribution shifts.

Critical strengths
  1. The paper addresses mathematical obstacles beyond normalizing coefficients. Canonicalization with an unconstrained backbone is an established approach, including for noncompact groups. The contribution here is its LP-specific development: maintaining permutation compatibility, remaining within the original rescaling orbit, and resolving restoration ambiguity when different transformations leave the LP unchanged. Existing canonicalization frameworks provide the relevant context for assessing this contribution.

The rescaling mask and its optimality-preservation argument are the most valuable part. They address a case in which choosing a deterministic transformation would not establish the desired equivariance. The method therefore has a stronger foundation than a heuristic preprocessing rule.

  1. The reported gains under numerical distribution shifts are substantial and hold across backbones and LP families. The evaluation includes two backbones, conventional prescaling methods, data augmentation, and multiple LP families. In Table 4, FullB-cano reduces OPF-57 OOD-3 loss from 0.7552 without preprocessing to 0.0654; the augmentation baseline obtains 0.2864. The implicit-backbone results also show consistent OOD improvements.

These results provide credible evidence that the proposed preprocessing helps prediction under the particular shifts studied. The fixed canonicalization weights across datasets also strengthen the empirical case.

Critical weaknesses
  1. The evaluation does not establish whether the predictions are better LP solutions, and its supervised target differs from the theoretical target. Appendix G.3 stores one optimal primal solution returned by HiGHS as the label, and the experiments mainly measure distance to this vector. An LP can have multiple optimal solutions, however. Two predictions can therefore have the same optimal objective value and satisfy every constraint while receiving very different prediction errors.

This matters because Theorem 7.1 and Appendix F establish approximation to the solution selected through canonicalization. They do not establish approximation to an arbitrary HiGHS-selected solution. Section 3 correctly notes that even the minimum-norm solution in the original coordinates is not generally equivariant under diagonal variable rescaling.

Lower label error therefore does not by itself show better feasibility or optimality, and a different but valid optimal prediction could be penalized. The paper does not report constraint violations, feasible-prediction rates, objective gaps for feasible predictions, or an analysis of label ambiguity.

Why this affects my recommendation: The theoretical guarantee and the principal experimental metric concern different targets. Without task-based evaluation, the practical meaning of the reported improvements remains uncertain.

  1. The experiments do not isolate the mechanism claimed to explain the gains, and the implemented method only approximately realizes the central guarantee. Section 8.2 interprets superiority over Ruiz equilibration as showing that the gains arise from symmetry rather than numerical conditioning. This comparison does not establish that conclusion. FullB-cano changes the treatment of the objective, right-hand sides, bounds, and matrix coefficients simultaneously. Its advantages could reflect these different normalization choices, exact symmetry, or a combination.

Higher training loss also does not establish the statement that augmentation sometimes weakens expressive power. Augmentation changes the training problem; it does not change the backbone’s representable function class. The impossibility results concern exact symmetry under specified assumptions and do not quantify the approximation tradeoff over the finite scale range used in training.

There is also a material gap between exact canonicalization and its implementation. Appendix G.1 uses identity initialization and at most 50 L-BFGS-B iterations. The rescaling mask resolves ambiguity between transformations mapping to the same canonical representative; it does not correct discrepancies between incompletely optimized representatives. Table 2 reports FullB-cano consistency losses around 10^{-4} to 10^{-3}. A loss of 8.83\times10^{-4} corresponds to approximately 3% normalized root-mean-square discrepancy under the stated squared metric.

Why this affects my recommendation: The results show that the preprocessing is useful, but they do not yet establish the paper’s stronger explanation of why it works or the practical accuracy–cost tradeoff for enforcing the claimed symmetry.

Questions for authors
  1. Evaluation: How often are the labeled LP solutions non-unique, and do the rankings persist under normalized constraint violations, feasible-prediction rates, and objective gaps? This would show whether the improvements reflect better optimization solutions rather than closer imitation of one solver-selected vector.
  2. Numerical guarantee: What fraction of canonicalization runs reach the convergence criterion before the 50-iteration cap? How do representative consistency, prediction consistency, and runtime change with tighter tolerances and larger iteration budgets? Please distinguish optimization error from floating-point error.
  3. Mechanism validation: Can an ablation separate symmetry enforcement from the particular energy design? A canonicalization that uses only positive quadratic log-magnitude penalties would retain the symmetry construction while removing the exponential equilibration term. This would help identify which part of the method produces the gains.
  4. Theorem applicability: Appendix G.4 adds LayerNorm to the evaluated architectures, whereas the ReLU variable-rescaling proof relies on the stated piecewise-polynomial message-passing structure. Which degeneracy results apply to the implemented architectures, and which are intended only as motivation?
11 comments
AuthorsOpenReview ↗

Our response to reviewer x6VC

Thank you for your detailed and valuable feedback and for recognizing the strength of our simple but expressive canonicalization framework (canonicalization, rescaling mask,...) in the context of learning-to-optimize. Below, we would like to clear up your confusion in this paper and discuss about your insightful questions.

Question 1. Evaluation clarification: How often are the labeled LP solutions nonunique, and do the rankings persist when evaluated using normalized constraint violations, feasible-prediction rates, and objective gaps? This would determine whether the improvements reflect better optimization solutions rather than closer imitation of one solver-selected vector.

We thank the reviewer for this insightful question concerning the bridge between theory and practice. We agree that distance to a solver-generated label alone does not establish feasibility or optimality. To assess feasibility and objective quality directly, we extended our evaluation to include normalized constraint violations and normalized squared objective gaps. The gains from canonicalization carry over to these metrics. Canonicalization generally reduces constraint violations and yields smaller objective gaps beyond lower distance to the reference solution. Below, we address your two questions in turn.

How often are the labeled LP solutions nonunique:

  • Theory: Regarding theoretical uniqueness, a classical result states that, for fixed constraint data, an attained LP optimum is unique for Lebesgue-almost every objective vector; see [1]. If the objective vector has an absolutely continuous conditional distribution given the constraint data and LP dimensions, the tower property extends this conclusion to random LPs. Under this assumption, any exact solver selection, the minimum-norm optimal-solution selector studied in prior GNN theory, and the restored canonicalization-selected optimum coincide almost surely whenever an optimum exists.
  • Practice: Standard benchmark LPs are generated from hand-designed models, so their objective vectors are often structured rather than continuously distributed (e.g., unit weights in IS). The assumption above can therefore fail, and multiple optima can occur. We ran an exact audit on the full ID collection of 9,000 instances. It found 7,807 instances with a unique optimum and 1,193 with multiple optima. The nonunique instances are concentrated in IS and part of NETLIB-derived. For all methods, labels are generated once by HiGHS and shared, without recomputing them to match either the minimum-norm or the canonicalization-selected solution. This is the standard solver-generated supervision protocol [2] and gives every method the same targets.

Whether the advantage of canonicalization persists under more practical evaluation metrics:

  • New experiments: Following your suggestion, we report constraint violation and objective gap alongside supervised solution error. Let x^\widehat{x} be the restored prediction and x⋆∈Rnx^\star\in\mathbb R^n a reference optimum, both in the original LP coordinates. Set s=max⁡1,∣x⋆∣2/ns=\max\\{1,\\|x^\star\\|_2/\sqrt n\\} and ε=10−8\varepsilon=10^{-8}. The supervised error and normalized squared objective gap are

    =\frac{\\|\widehat{x}-x^\star\\|_2^2}{ns^2}, \qquad \mathcal L_{\mathrm{obj}} =\left( \frac{c^\top(\widehat{x}-x^\star)} {\max\\{\varepsilon,s\\|c\\|_2,|c^\top x^\star|\\}} \right)^2.$$ For feasibility, we divide each equality residual $a_i^\top\widehat{x}-b_i$ and inequality violation (assume constraint is $a_i^\top x \leq b_i$) $[a_i^\top\widehat{x}-b_i]_+$ by $d_i=\max\\{\varepsilon,s\\|a_i\\|_2,|b_i|\\}$, where $[t]_+=\max\\{t,0\\}$. For finite lower and upper bounds, the normalized violations are $[\ell_j-\widehat{x}_j]_+/\max\\{s,|\ell_j|\\}$ and $[\widehat{x}_j-u_j]_+/\max\\{s,|u_j|\\}$, respectively. We compute $\mathcal L_{\mathrm{feas}}$ by taking the mean squared normalized residual within each group (equalities, inequalities, and bounds) and averaging the group means. We report $\mathcal L_{\mathrm{sup}},\mathcal L_{\mathrm{feas}},\mathcal L_{\mathrm{obj}}$ for raw predictions and for predictions projected onto the feasible polyhedron. After projection, every method is feasible to machine precision: normalized violations are on the order of $10^{-20}$ (Table 1, middle block). The feasible-prediction rate is therefore 100% for all methods and does not distinguish them. To show feasibility differences, we report raw (pre-projection) violations instead (Tables 10–11, page 58-59.).
AuthorsOpenReview ↗

Our response to reviewer x6VC

  • Task-aware training: Because the evaluation now targets feasibility and optimality as well as solution distance, we also aligned the training objective with these criteria. We retrained all models in the nine-dataset comparison with the composite loss: L=Lsup+Lfeas+0.1,Lobj,L = L_{sup} + L_{feas} + 0.1\\, L_{obj}, and used the same criterion for validation-based checkpoint selection. Each component is reported separately at test time. The results can be seen in the following and Table 3,5, 10-13 in our manuscripts.

    Table 1. Post-projection ID test metrics for the LP-GNN backbone.

    Post-projection supervised loss

    \textbf{Dataset} & \textbf{None} & \substack{\textbf{Data}\\\\\textbf{Augmentation}} & \textbf{HiGHS} & \substack{\textbf{Ruiz}\\\\\textbf{Equilibration}} & \substack{\textbf{(α,R)-}\\\\\textbf{Normalization}} & \textbf{FullB-cano} & \textbf{β-cano}\cr \hline \text{CA}&0.0158{±}5.40{×}10^{-5}&0.0223{±}3.68{×}10^{-4}&0.0162{±}2.48{×}10^{-4}&0.0158{±}1.78{×}10^{-4}&0.0101{±}1.07{×}10^{-4}&\mathbf{0.0086}{±}4.80{×}10^{-5}&0.0094{±}1.13{×}10^{-4}\cr \text{SC}&0.0274{±}2.26{×}10^{-4}&0.0378{±}4.17{×}10^{-5}&0.0314{±}0.0035&0.0286{±}2.01{×}10^{-4}&0.0222{±}1.82{×}10^{-4}&\mathbf{0.0124}{±}2.21{×}10^{-5}&0.0205{±}5.89{×}10^{-5}\cr \text{OPF-57}&0.0055{±}4.06{×}10^{-4}&0.0056{±}2.53{×}10^{-4}&0.0056{±}1.36{×}10^{-4}&0.0029{±}1.08{×}10^{-4}&0.0041{±}2.39{×}10^{-4}&\mathbf{0.0019}{±}2.30{×}10^{-4}&0.0024{±}2.29{×}10^{-4}\cr \text{OPF-118}&0.0511{±}9.36{×}10^{-4}&0.0527{±}2.92{×}10^{-4}&0.0547{±}0.0015&0.0491{±}3.06{×}10^{-4}&0.0531{±}4.55{×}10^{-4}&\mathbf{0.0433}{±}0.0010&0.0479{±}7.52{×}10^{-4}\cr \text{OPF-300}&0.1268{±}8.47{×}10^{-4}&0.1256{±}9.36{×}10^{-4}&0.1370{±}0.0013&0.1148{±}0.0039&0.1205{±}9.11{×}10^{-4}&\mathbf{0.0942}{±}5.24{×}10^{-5}&0.1109{±}4.25{×}10^{-4}\cr \text{MCF}&0.0380{±}4.56{×}10^{-4}&0.0413{±}3.15{×}10^{-4}&0.0377{±}1.41{×}10^{-4}&0.0385{±}5.35{×}10^{-5}&0.0361{±}1.89{×}10^{-5}&0.0355{±}2.79{×}10^{-4}&\mathbf{0.0354}{±}3.37{×}10^{-4}\cr \text{CFLP}&0.0075{±}7.69{×}10^{-5}&0.0122{±}3.86{×}10^{-4}&0.0083{±}2.10{×}10^{-4}&0.0071{±}9.14{×}10^{-5}&0.0123{±}0.0013&\mathbf{0.0068}{±}1.47{×}10^{-4}&0.0073{±}5.45{×}10^{-5}\cr \text{IS}&0.2428{±}4.21{×}10^{-5}&0.2428{±}5.42{×}10^{-5}&0.2427{±}2.51{×}10^{-5}&0.2428{±}1.96{×}10^{-5}&0.2427{±}2.30{×}10^{-5}&\mathbf{0.0794}{±}3.55{×}10^{-5}&0.2427{±}2.37{×}10^{-5}\cr \text{NETLIB}&0.1381{±}0.0013&0.1312{±}0.0013&0.1367{±}0.0012&0.1323{±}0.0022&0.1216{±}0.0044&\mathbf{0.0937}{±}0.0019&0.1044{±}0.0086\cr \hline \end{array}$$
AuthorsOpenReview ↗

Our response to reviewer x6VC

Post-projection constraint violation

\textbf{Dataset} & \textbf{None} & \substack{\textbf{Data}\\\\\textbf{Augmentation}} & \textbf{HiGHS} & \substack{\textbf{Ruiz}\\\\\textbf{Equilibration}} & \substack{\textbf{(α,R)-}\\\\\textbf{Normalization}} & \textbf{FullB-cano} & \textbf{β-cano}\cr \hline \text{CA}&3.69{×}10^{-20}{±}9.11{×}10^{-22}&\mathbf{2.91{×}10^{-20}}{±}8.88{×}10^{-22}&4.01{×}10^{-20}{±}9.30{×}10^{-22}&3.43{×}10^{-20}{±}1.19{×}10^{-21}&4.82{×}10^{-20}{±}2.59{×}10^{-21}&5.76{×}10^{-20}{±}1.40{×}10^{-21}&4.93{×}10^{-20}{±}1.63{×}10^{-21}\cr \text{SC}&5.41{×}10^{-20}{±}1.99{×}10^{-21}&4.07{×}10^{-20}{±}1.16{×}10^{-20}&4.06{×}10^{-20}{±}1.26{×}10^{-20}&5.27{×}10^{-20}{±}2.34{×}10^{-21}&5.48{×}10^{-20}{±}4.97{×}10^{-21}&\mathbf{3.81{×}10^{-20}}{±}7.41{×}10^{-21}&3.93{×}10^{-20}{±}3.87{×}10^{-21}\cr \text{OPF-57}&2.12{×}10^{-19}{±}5.50{×}10^{-22}&2.12{×}10^{-19}{±}1.18{×}10^{-22}&2.09{×}10^{-19}{±}1.90{×}10^{-22}&2.04{×}10^{-19}{±}6.24{×}10^{-22}&2.07{×}10^{-19}{±}9.32{×}10^{-22}&\mathbf{2.00{×}10^{-19}}{±}8.88{×}10^{-22}&2.10{×}10^{-19}{±}1.05{×}10^{-21}\cr \text{OPF-118}&1.96{×}10^{-19}{±}1.33{×}10^{-21}&1.95{×}10^{-19}{±}3.97{×}10^{-22}&1.94{×}10^{-19}{±}1.23{×}10^{-21}&1.93{×}10^{-19}{±}1.05{×}10^{-21}&1.98{×}10^{-19}{±}4.09{×}10^{-22}&\mathbf{1.91{×}10^{-19}}{±}8.74{×}10^{-22}&1.96{×}10^{-19}{±}9.89{×}10^{-22}\cr \text{OPF-300}&1.66{×}10^{-20}{±}1.91{×}10^{-22}&1.68{×}10^{-20}{±}3.57{×}10^{-22}&1.64{×}10^{-20}{±}1.07{×}10^{-22}&1.64{×}10^{-20}{±}7.90{×}10^{-23}&1.69{×}10^{-20}{±}2.21{×}10^{-22}&\mathbf{1.61{×}10^{-20}}{±}1.51{×}10^{-22}&1.71{×}10^{-20}{±}1.06{×}10^{-22}\cr \text{MCF}&9.99{×}10^{-20}{±}1.13{×}10^{-21}&\mathbf{9.66{×}10^{-20}}{±}9.73{×}10^{-22}&1.01{×}10^{-19}{±}1.43{×}10^{-21}&9.83{×}10^{-20}{±}2.45{×}10^{-21}&1.02{×}10^{-19}{±}3.95{×}10^{-22}&1.02{×}10^{-19}{±}2.49{×}10^{-21}&1.00{×}10^{-19}{±}2.54{×}10^{-21}\cr \text{CFLP}&\mathbf{1.21{×}10^{-19}}{±}5.44{×}10^{-21}&1.23{×}10^{-19}{±}5.89{×}10^{-21}&1.24{×}10^{-19}{±}3.18{×}10^{-21}&1.32{×}10^{-19}{±}3.28{×}10^{-21}&1.23{×}10^{-19}{±}1.06{×}10^{-20}&1.35{×}10^{-19}{±}2.67{×}10^{-21}&1.26{×}10^{-19}{±}1.34{×}10^{-21}\cr \text{IS}&9.09{×}10^{-20}{±}6.71{×}10^{-23}&9.09{×}10^{-20}{±}9.04{×}10^{-23}&9.10{×}10^{-20}{±}4.32{×}10^{-23}&9.09{×}10^{-20}{±}3.12{×}10^{-23}&9.10{×}10^{-20}{±}4.08{×}10^{-23}&\mathbf{2.14{×}10^{-20}}{±}6.92{×}10^{-21}&9.10{×}10^{-20}{±}4.22{×}10^{-23}\cr \text{NETLIB}&\mathbf{8.85{×}10^{-24}}{±}5.15{×}10^{-25}&1.83{×}10^{-23}{±}1.98{×}10^{-24}&1.79{×}10^{-23}{±}2.70{×}10^{-24}&1.31{×}10^{-23}{±}7.33{×}10^{-25}&9.70{×}10^{-24}{±}5.61{×}10^{-25}&1.66{×}10^{-23}{±}1.70{×}10^{-24}&1.73{×}10^{-23}{±}6.19{×}10^{-24}\cr \hline \end{array}$$ **Post-projection objective gap** $$\scriptsize\begin{array}{lrrrrrrr} \textbf{Dataset} & \textbf{None} & \substack{\textbf{Data}\\\\\textbf{Augmentation}} & \textbf{HiGHS} & \substack{\textbf{Ruiz}\\\\\textbf{Equilibration}} & \substack{\textbf{(α,R)-}\\\\\textbf{Normalization}} & \textbf{FullB-cano} & \textbf{β-cano}\cr \hline \text{CA}&0.0236{±}3.03{×}10^{-4}&0.0469{±}7.70{×}10^{-4}&0.0239{±}4.74{×}10^{-4}&0.0247{±}5.93{×}10^{-4}&0.0071{±}2.82{×}10^{-4}&\mathbf{0.0062}{±}1.86{×}10^{-4}&0.0071{±}5.49{×}10^{-4}\cr \text{SC}&0.0283{±}0.0014&0.0705{±}0.0030&0.0427{±}0.0096&0.0311{±}5.65{×}10^{-4}&0.0138{±}7.11{×}10^{-4}&\mathbf{0.0078}{±}2.27{×}10^{-4}&0.0137{±}3.75{×}10^{-4}\cr \text{OPF-57}&6.45{×}10^{-4}{±}9.04{×}10^{-5}&8.53{×}10^{-4}{±}5.38{×}10^{-5}&8.75{×}10^{-4}{±}6.66{×}10^{-5}&3.11{×}10^{-4}{±}3.30{×}10^{-5}&5.26{×}10^{-4}{±}1.90{×}10^{-5}&\mathbf{1.77{×}10^{-4}}{±}3.21{×}10^{-5}&4.23{×}10^{-4}{±}5.16{×}10^{-5}\cr \text{OPF-118}&0.0062{±}6.17{×}10^{-4}&0.0061{±}5.26{×}10^{-5}&0.0053{±}2.44{×}10^{-4}&0.0046{±}2.68{×}10^{-4}&0.0068{±}3.92{×}10^{-4}&\mathbf{0.0041}{±}1.39{×}10^{-4}&0.0054{±}5.20{×}10^{-4}\cr \text{OPF-300}&0.0207{±}0.0013&0.0223{±}4.84{×}10^{-4}&0.0251{±}0.0029&0.0123{±}0.0017&0.0181{±}9.18{×}10^{-4}&\mathbf{0.0109}{±}6.09{×}10^{-4}&0.0146{±}5.95{×}10^{-4}\cr \text{MCF}&0.0063{±}1.32{×}10^{-4}&0.0084{±}3.59{×}10^{-4}&0.0065{±}3.74{×}10^{-4}&0.0072{±}3.63{×}10^{-4}&0.0057{±}3.70{×}10^{-5}&\mathbf{0.0053}{±}2.93{×}10^{-4}&0.0057{±}2.66{×}10^{-4}\cr \text{CFLP}&0.0091{±}6.10{×}10^{-4}&0.0197{±}0.0018&0.0100{±}5.59{×}10^{-4}&\mathbf{0.0071}{±}4.86{×}10^{-4}&0.0214{±}0.0035&0.0081{±}6.20{×}10^{-4}&0.0078{±}2.73{×}10^{-4}\cr \text{IS}&0.0179{±}5.40{×}10^{-6}&0.0179{±}6.94{×}10^{-6}&0.0179{±}3.22{×}10^{-6}&0.0179{±}2.51{×}10^{-6}&0.0179{±}2.95{×}10^{-6}&\mathbf{2.41{×}10^{-4}}{±}4.61{×}10^{-5}&0.0179{±}3.04{×}10^{-6}\cr \text{NETLIB}&0.0191{±}0.0015&0.0288{±}0.0014&0.0395{±}0.0021&0.0241{±}0.0038&0.0277{±}0.0041&0.0141{±}9.25{×}10^{-4}&\mathbf{0.0140}{±}0.0013\cr \hline \end{array}$$
Reviewer_1yRKOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The authors investigate notions of equivariance of GNNs in the context of linear programs and learning to optimize. They focus on certain linear transformations applied to constraints and linear objectives. They are motivated by the application of such transformations which are used in practice to better condition an LP and to make it more suitable numerically for classical algorithms. This is an important standard in practice when solving LPs. Recently, neural network (GNN)-based methods have been applied to augment classical algorithms. These methods ingest graph-based representations of these programs and are applied to make useful predictions to improve performance of classical algorithms or replace them entirely. As imposing certain invariances or equivariances on GNNs has demonstrable positive effect in other applications, it is of interest to investigate this in the L2O context as well.

One of the key results of this paper is that improperly enforcing equivariance to linear transformations of Linear Program can result in certain degeneracies. In particular, "predictors must ignore essential LP coefficients, such as the objective vector or the constraint system". However, the authors demonstrate that this limitation can be avoided via model-agnostic "canonicalization" to induce scaling invariance. Canonicalization is performed by first carefully selecting a program from the set of rescaled Linear Programs via energy minimization and using these instances for training and inference. The authors provide results that this framework does not degrade the expressiveness of the resulting GNN.

Extensive experiments are conducted on nine different datasets of linear programs and in comparison to popular equilibriation (rescaling) and other state-of-the-art (HIGHS) baselines. The results indicate that the proposed framework generally achieve much lower final training and validation selected ID test losses at much lower variance.

Critical strengths

I read this paper carefully, and I believe it is a strong submission for this conference. The problem is novel and of both practical and theoretical interest. The paper is well-written and clear. I believe the empirical and theoretical analysis is sufficiently comprehensive and straightforward to understand. The experimental results I believe are intuitive and naturally follow from the analysis provided by the authors.

Critical weaknesses

I do not have many comments for the authors or suggestions to improve the manuscript. Gurobi released a new tool that is highly relevant to this work and may of interest: https://github.com/Gurobi/gurobi-modelanalyzer

Questions for authors

I imagine for simple quadratic problems with equality constraints, this framework could be applied ad-hoc. Have the authors pursued this direction for quadratic problems?

3 comments
AuthorsOpenReview ↗

Our response to reviewer 1yRK

We sincerely thank the time and effort you devoted to thoroughly reviewing our paper. Your insightful and constructive comments are greatly appreciated, and we are very glad to share our thoughts with you.

I do not have many comments for the authors or suggestions to improve the manuscript. Gurobi released a new tool that is highly relevant to this work and may of interest: https://github.com/Gurobi/gurobi-modelanalyzer

Thank you for bringing this relevant and interesting work to our attention. Its model-scaling module is closely related to our work, providing practical equilibration, geometric-mean, and arithmetic-mean scaling methods together with recovery of solutions in the original coordinates. We cite this tool and discuss the connection in the numerical-prescaling paragraph of Section 2 and the related sections in the Appendix. See the highlighted paragraphs in line 114-115(page 3) and line 1122-1123(page 21).

I imagine for simple quadratic problems with equality constraints, this framework could be applied ad-hoc. Have the authors pursued this direction for quadratic problems?

Thank you for the insightful question. Yes, we have explored how our canonicalization extends to quadratic programs. Consider the equality-constrained problem

\qquad \text{subject to } Ax=b.$$ Under the change of variables $x=Dy$, with $D$ positive diagonal, a positive objective scaling $\alpha$ and a positive diagonal row scaling $R$ transform the coefficient tuple as $$(Q,c,A,b)\longmapsto(\alpha DQD,\\ \alpha Dc,\\ RAD,\\ Rb).$$ For example, the log-magnitude of a nonzero Hessian entry $Q_{jk}$ shifts by $\log\alpha+\log D_{jj}+\log D_{kk}$. As in the LP case, the rescaling orbit is therefore affine in the log-magnitudes of the nonzero coefficients. Minimizing a permutation-invariant strongly convex energy over this affine space selects a unique representative. Rescaling leaves the affine space unchanged, while relabeling permutes its coordinates, so the representative is rescaling-invariant and permutation-equivariant. The same construction applies to quadratic inequality constraints, whose Hessian entries acquire an additional log row-scale term. The mask $P$ retains precisely the variable coordinates fixed by every rescaling that leaves the canonical instance unchanged. Applying the mask before mapping a prediction back, as in $DP\hat y$, makes the result independent of the rescaling used to reach the canonical instance. With a permutation-equivariant backbone, the resulting model is equivariant under both permutations and rescalings. These symmetry properties hold for general quadratic instances. For the universality guarantee, we restrict attention to convex instances. Positive diagonal rescaling and positive scalar multiplication preserve positive semidefiniteness of the objective and constraint Hessians; hence, rescaling keeps the convexity. In this setting, the mask also preserves feasibility and optimality when applied to an optimizer. For bounded problem dimensions and distributions supported on convex instances with attained optima, the GNN approximation results of [1],[2] yield approximation in probability of the solution map that selects the minimum-norm optimizer in canonical coordinates and maps it back to the original coordinates. ## Reference: [1] Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. *Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs*. ICML, PMLR 267, 7880–7911, 2025. (<https://proceedings.mlr.press/v267/chen25j.html>) [2] Chenyang Wu, Qian Chen, Akang Wang, Tian Ding, Ruoyu Sun, Wenguo Yang, and Qingjiang Shi. *On Representing Convex Quadratically Constrained Quadratic Programs via Graph Neural Networks*. TMLR, November 2025. (<https://openreview.net/forum?id=GC2ZO6Asoa>)

Thank you for your response, I keep my positive score.

Thank you very much for your time and effort in reviewing our paper, and for keeping your score. We sincerely appreciate your careful consideration~

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.