Principled data augmentation for learning to solve quadratic programming problems

Chendi Qian, Christopher Morris · 2025

Read Principled data augmentation for learning to solve quadratic programming problems by Chendi Qian, Christopher Morris (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01728.txt.

Introduction

Chendi Qian and Christopher Morris improve machine learning solvers for quadratic programming in a 2025 paper. Quadratic programs sit inside many tasks, from training models to planning. Neural networks that pass messages on graphs can learn to solve them fast, but training data are scarce, above all for hard cases.

The pair design data augmentation that creates new training problems while keeping the best answer unchanged. Theory backs the safety of these changes. They fold the trick into a self-supervised method that pre-trains the network by contrast. Tests show better accuracy on held-out problems in supervised use. The pre-training also carried over to related problem types. The authors say principled augmentation is the key step for data-poor solver learning.

Catalog record

CREATORChendi Qian, Christopher Morris
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01728

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Principled data augmentation for learning to solve quadratic programming problems Chendi Qian, Christopher Morris Abstract Linear and quadratic optimization are crucial in numerous real-world applications, from training machine learning models to integer-linear optimization. Recently, learning-to-optimize methods (L2O) for linear (LPs) or quadratic programs (QPs) using message-passing graph neural networks (MPNNs) have gained traction, promising lightweight, data-driven proxies for solving such optimization problems. For example, they replace the costly computation of strong branching scores in branch-and-bound solvers, requiring solving many such optimization problems. However, robust L2O MPNNs remain challenging in data-scarce settings, especially when addressing complex optimization problems such as QPs. This work introduces a principled approach to data augmentation tailored for QPs via MPNNs. Our method leverages theoretically justified data augmentation techniques to generate diverse yet optimality-preserving instances. Furthermore, we integrate these augmentations into a self-supervised learning framework based on contrastive learning, thereby pretraining MPNNs for enhanced performance on L2O tasks. Extensive experiments demonstrate that our approach improves generalization in supervised scenarios and facilitates effective transfer learning to related optimization problems. 1 Introduction Linear and quadratic optimization problems are fundamental problems in machine learning, operations research, and scientific computing ( Boyd and Vandenberghe 2004 ; Nocedal and Wright 1999 ) . Many real-world applications, such as resource allocation, logistics, and training machine learning models, rely on efficiently solving large-scale linear programming (LPs) and quadratic programming (QPs). In addition, they play a key role in state-of-the-art integer-linear optimization solvers, allowing the computation of lower bounds, and are the basis for crucial heuristics such as strong branching for variable selection ( Achterberg et al. 2005 ) . Recently, machine learning techniques, particularly message-passing graph neural networks (MPNNs) ( Gilmer et al. 2017 ; Scarselli et al. 2008 ) have been explored for learning-to-optimize (L2O) approaches, aiming to learn to solve LPs and QPs in a data-driven fashion ( Bengio et al. 2021 ; Cappart et al. 2023 ) , enhancing solver efficiency and improving generalization across different problem instances. For example, Gasse et al. 2019 used MPNNs to imitate the costly strong branching score for variable selection in integer-linear optimization solvers, which requires solving many LPs during the solving process. However, training robust models for L2O remains challenging due to the scarcity of labeled data, especially for complex optimization formulations such as QPs. In response to this challenge, self-supervised learning (SSL) has emerged as a powerful paradigm for pretraining models on large, unlabeled datasets ( Liu et al. 2021 ) . Contrastive learning , a key approach in SSL, has demonstrated significant success in graph-based tasks by leveraging data augmentation techniques to create diverse training examples You et al. 2020 . Despite advances in contrastive learning and L2O with MPNNs, a gap exists in integrating these two paradigms for LPs and QPs. Additionally, designing effective and principled data augmentation strategies for LPs and QPs remains non-trivial due to the structural constraints and optimality conditions inherent in these problems. Present work In this work, we propose a principled approach to data augmentation for LPs and QPs, specifically designed to enhance the performance of MPNN-based L2O methods for such problems; see Fig. 1 for a high-level overview. Concretely, our contributions are as follows: 1. We introduce a set of novel and theoretically grounded augmentation techniques for LPs and QPs that preserve optimality while generating diverse training instances; 2. We apply these augmentations in both supervised and self-supervised settings, including contrastive pretraining of MPNNs to enhance downstream performance; 3. We empirically evaluate our approach on synthetic and benchmark datasets, showing that pretraining with our augmentations improves generalization and transferability across problem classes. By bridging the gap between data augmentation and L2O for LPs and QPs, our work offers a new perspective on enhancing neural solvers through supervised learning and self-supervised pretraining. The proposed augmentations improve generalization in data-scarce settings, enabling more efficient and robust learning-based optimization methods. 1.1 Related work This section reviews relevant literature on L2O, graph data augmentation, graph contrastive learning, and synthetic instance generation for LP and MILP problems. MPNN and L2O Message Passing Neural Networks (MPNNs) ( Gilmer et al. 2017 ; Scarselli et al. 2008 ) have been extensively studied and are broadly categorized into spatial and spectral variants. Spatial MPNNs ( Bresson and Laurent 2017 ; Duvenaud et al. 2015 ; Hamilton et al. 2017 ; Veličković et al. 2017 ; Xu et al. 2018 ) follow the message-passing paradigm introduced by Gilmer et al. 2017 . MPNNs have shown strong potential in learning to optimize (L2O). A widely adopted approach represents MILPs using constraint-variable bipartite graphs ( Chen et al. 2022 ; Ding et al. 2020 ; Gasse et al. 2019 ; Khalil et al. 2022 ; Qian et al. 2024a ) . Recent work has also aligned MPNNs with various optimization algorithms, including interior-point methods (IPMs) ( Qian et al. 2024a ; Qian and Morris 2025 ) , primal-dual hybrid gradient (PDHG) ( Li et al. 2024a ) , and distributed algorithms ( Li et al. 2024b ; Li et al. 2025 ) . From a theoretical perspective, several studies have analyzed the expressiveness of MPNNs in approximating solutions to linear and quadratic programming ( Chen et al. 2022 ; Chen et al. 2023 ; Chen et al. 2024b ; Chen et al. 2024a ; Wu et al. 2024 ) . Graph data augmentation Graph data augmentation is central to learning-based optimization, especially under data scarcity. Common strategies include feature-wise perturbations ( You et al. 2020 ; Zhu et al. 2020 ; Suresh et al. 2021 ; Zhu et al. 2021 ; Thakoor et al. 2021 ; Bielak et al. 2022 ; Hu et al. 2023 ) , structure-wise modifications such as node dropping and edge perturbation ( Rong et al. 2019 ; Hassani and Khasahmadi 2020 ; Zhu et al. 2020 ; Qiu et al. 2020 ; Papp et al. 2021 ; Zhu et al. 2021 ; Bielak et al. 2022 ; Hu et al. 2023 ) , and spectral-domain augmentations ( Yang et al. 2024a ; Liu et al. 2022a ; Lin et al. 2022 ; Wan et al. 2024 ) , the latter aligning with recent works like S3GCL. Learning-based approaches ( Yang et al. 2020 ; Zhao et al. 2021 ; Liu et al. 2022b ; Yin et al. 2022 ; You et al. 2021 ; Wu et al. 2023 ) further enable adaptive augmentation via trainable modules. Complementary perspectives include graph rewiring ( Topping et al. 2021 ; Karhadkar et al. 2022 ; Arnaiz-Rodríguez et al. 2022 ; Qian et al. 2023 ; Gutteridge et al. 2023 ; Barbero et al. 2023 ; Qian et al. 2024b ) and structure learning ( Jin et al. 2020 ; Liu et al. 2022c ; Zou et al. 2023 ; Zhou et al. 2023 ; Fatemi et al. 2023 ) , both of which can be viewed as task-specific augmentation techniques, for a broader overview, including robustness and self-supervised settings, see ( Zhao et al. 2022 ; Ding et al. 2022 ) . Graph data augmentation is central to contrastive learning, generating diverse and informative views; see also Appendix C . While general-purpose augmentations are well-studied, few works target L2O problems. Duan et al. 2022

Read the complete text