# Learning Hard Optimization Problems: A Data Generation Perspective

arXiv: https://arxiv.org/abs/2106.02601 · HTML: https://mlsanity.com/paper/2106.02601/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 20 of 20)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods](https://mlsanity.com/paper/1909.10461/) (2019)
- [Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems](https://mlsanity.com/paper/1911.10092/) (2019)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Lagrangian Duality for Constrained Deep Learning](https://mlsanity.com/paper/2001.09394/) (2020)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach](https://mlsanity.com/paper/2009.12562/) (2020)
- [PowerModels.jl: An Open-Source Framework for Exploring Power Flow Formulations](https://mlsanity.com/paper/1711.01728/) (2017)
- [Teaching the Old Dog New Tricks: Supervised Learning with Constraints](https://mlsanity.com/paper/2002.10766/) (2020)
- [NESTA, The NICTA Energy System Test Case Archive](https://mlsanity.com/paper/1411.0359/) (2014)
- [A closer look at the approximation capabilities of neural networks](https://mlsanity.com/paper/2002.06505/) (2020)
- [Combining Learning and Optimization for Transprecision Computing](https://mlsanity.com/paper/2002.10890/) (2020)

## Built on by (most cited first, 21 of 21)

- [Self-Supervised Primal-Dual Learning for Constrained Optimization](https://mlsanity.com/paper/2208.09046/) (2022)
- [Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method](https://mlsanity.com/paper/2110.06365/) (2021)
- [A New Computationally Simple Approach for Implementing Neural Networks with Output Hard Constraints](https://mlsanity.com/paper/2307.10459/) (2023)
- [Learning To Dive In Branch And Bound](https://mlsanity.com/paper/2301.09943/) (2023)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Ensuring DNN Solution Feasibility for Optimization Problems with Convex Constraints and Its Application to DC Optimal Power Flow Problems](https://mlsanity.com/paper/2112.08091/) (2021)
- [Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning](https://mlsanity.com/paper/2205.00897/) (2022)
- [Metric Learning to Accelerate Convergence of Operator Splitting Methods for Differentiable Parametric Programming](https://mlsanity.com/paper/2404.00882/) (2024)
- [Two-Stage Learning For the Flexible Job Shop Scheduling Problem](https://mlsanity.com/paper/2301.09703/) (2023)
- [Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization](https://mlsanity.com/paper/2311.13087/) (2023)
- [Quantum Extremal Learning](https://mlsanity.com/paper/2205.02807/) (2022)
- [Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks](https://mlsanity.com/paper/2307.04050/) (2023)
- [Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models](https://mlsanity.com/paper/2404.11606/) (2024)
- [Deep Learning for Two-Stage Robust Integer Optimization](https://mlsanity.com/paper/2310.04345/) (2023)
- [Compact Optimality Verification for Optimization Proxies](https://mlsanity.com/paper/2405.21023/) (2024)
- [DeepOPF-AL: Augmented Learning for Solving AC-OPF Problems with Multiple Load-Solution Mappings](https://mlsanity.com/paper/2206.03365/) (2022)
- [Towards Understanding the Unreasonable Effectiveness of Learning AC-OPF Solutions](https://mlsanity.com/paper/2111.11168/) (2021)
- [Neural Quantile Optimization for Edge-Cloud Networking](https://mlsanity.com/paper/2307.05170/) (2023)
- [Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework](https://mlsanity.com/paper/2312.03413/) (2023)
- [SOMTP: Self-Supervised Learning-Based Optimizer for MPC-Based Safe Trajectory Planning Problems in Robotics](https://mlsanity.com/paper/2405.09212/) (2024)
- [Homotopy-Guided Self-Supervised Learning of Parametric Solutions for AC Optimal Power Flow](https://mlsanity.com/paper/2511.11677/) (2025)

## Abstract (arXiv)

Optimization problems are ubiquitous in our societies and are present in almost every segment of the economy. Most of these optimization problems are NP-hard and computationally demanding, often requiring approximate solutions for large-scale instances. Machine learning frameworks that learn to approximate solutions to such hard optimization problems are a potentially promising avenue to address these difficulties, particularly when many closely related problem instances must be solved repeatedly. Supervised learning frameworks can train a model using the outputs of pre-solved instances. However, when the outputs are themselves approximations, when the optimization problem has symmetric solutions, and/or when the solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task can become inherently more difficult. This paper demonstrates this critical challenge, connects the volatility of the training data to the ability of a model to approximate it, and proposes a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks. The effectiveness of the method is tested on hard non-linear nonconvex and discrete combinatorial problems.