Principled data augmentation for learning to solve quadratic programming problems

• URL: http://arxiv.org/abs/2506.01728v1
• Date: Mon, 02 Jun 2025 14:40:18 GMT
• Title: Principled data augmentation for learning to solve quadratic programming problems
• Authors: Chendi Qian, Christopher Morris,
• Abstract summary: Learning-to-optimize methods (L2O) for linear (LPs) or quadratic programs (QPs) have gained traction.<n>MPNNs promise lightweight, data-driven proxies for solving such optimization problems.<n>However, robust MPNNs remain challenging in data-scarce settings.<n>This work introduces a principled approach to data augmentation tailored for QPs via MPNNs.
• Score: 5.966097889241178
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Optimizers Qualitatively Alter Solutions And We Should Leverage This [62.662640460717476]
  Deep Neural Networks (DNNs) can not guarantee convergence to a unique global minimum of the loss when using only local information, such as SGD.<n>We argue that the community should aim at understanding the biases of already existing methods, as well as aim to build new DNNs with the explicit intent of inducing certain properties of the solution.
  arXiv  Detail & Related papers  (2025-07-16T13:33:31Z)
• Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach [5.84228364962637]
  We present a meta-optimization method that learns efficient algorithms to approximate optimization problems.<n>We prove exponential convergence, approximation guarantees, and generalization bounds for our learning method.<n>This method offers superior computational efficiency, producing high-quality approximations faster and scaling better with problem size compared to existing techniques.
  arXiv  Detail & Related papers  (2025-05-16T15:27:50Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• Teaching Networks to Solve Optimization Problems [13.803078209630444]
  We propose to replace the iterative solvers altogether with a trainable parametric set function. We show the feasibility of learning such parametric (set) functions to solve various classic optimization problems.
  arXiv  Detail & Related papers  (2022-02-08T19:13:13Z)
• Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
  Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods. This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization.
  arXiv  Detail & Related papers  (2021-03-23T20:46:20Z)
• Learning to Optimize Under Constraints with Unsupervised Deep Neural Networks [0.0]
  We propose a machine learning (ML) method to learn how to solve a generic constrained continuous optimization problem. In this paper, we propose an unsupervised deep learning (DL) solution for solving constrained optimization problems in real-time.
  arXiv  Detail & Related papers  (2021-01-04T02:58:37Z)
• Optimization-driven Machine Learning for Intelligent Reflecting Surfaces Assisted Wireless Networks [82.33619654835348]
  Intelligent surface (IRS) has been employed to reshape the wireless channels by controlling individual scattering elements' phase shifts. Due to the large size of scattering elements, the passive beamforming is typically challenged by the high computational complexity. In this article, we focus on machine learning (ML) approaches for performance in IRS-assisted wireless networks.
  arXiv  Detail & Related papers  (2020-08-29T08:39:43Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11:54Z)
• Unsupervised Deep Learning for Optimizing Wireless Systems with Instantaneous and Statistic Constraints [29.823814915538463]
  We establish a unified framework of using unsupervised deep learning to solve both kinds of problems with both instantaneous and statistic constraints. We show that unsupervised learning outperforms supervised learning in terms of violation probability and approximation accuracy of the optimal policy.
  arXiv  Detail & Related papers  (2020-05-30T13:37:14Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  Self-directed Online Learning Optimization integrates Deep Neural Network (DNN) with Finite Element Method (FEM) calculations. Our algorithm was tested by four types of problems including compliance minimization, fluid-structure optimization, heat transfer enhancement and truss optimization. It reduced the computational time by 2 5 orders of magnitude compared with directly using methods, and outperformed all state-of-the-art algorithms tested in our experiments.
  arXiv  Detail & Related papers  (2020-02-04T20:00:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.