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

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.