# SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 97 references that are in the map.
- First posted on arXiv 22 Oct 2022.

## Builds on (most cited first, 30 of 47)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [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)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Meta-Learning with Differentiable Convex Optimization](https://mlsanity.com/paper/1904.03758/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Deep Learning Recommendation Model for Personalization and Recommendation Systems](https://mlsanity.com/paper/1906.00091/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [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)
- [DC3: A learning method for optimization with hard constraints](https://mlsanity.com/paper/2104.12225/) (2021)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems](https://mlsanity.com/paper/1911.10092/) (2019)
- [Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search](https://mlsanity.com/paper/2007.00708/) (2020)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)
- [Theseus: A Library for Differentiable Nonlinear Optimization](https://mlsanity.com/paper/2207.09442/) (2022)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Optimizing Rank-based Metrics with Blackbox Differentiation](https://mlsanity.com/paper/1912.03500/) (2019)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)

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

- [AdvPrompter: Fast Adaptive Adversarial Prompting for LLMs](https://mlsanity.com/paper/2404.16873/) (2024)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information](https://mlsanity.com/paper/2307.08964/) (2023)
- [TaskMet: Task-Driven Metric Learning for Model Learning](https://mlsanity.com/paper/2312.05250/) (2023)
- [BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning](https://mlsanity.com/paper/2411.19285/) (2024)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)
- [CaVE: A Cone-Aligned Approach for Fast Predict-then-optimize with Binary Linear Programs](https://mlsanity.com/paper/2312.07718/) (2023)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [AI4OPT: AI Institute for Advances in Optimization](https://mlsanity.com/paper/2307.02671/) (2023)
- [Pre-train and Search: Efficient Embedding Table Sharding with Pre-trained Neural Cost Models](https://mlsanity.com/paper/2305.01868/) (2023)
- [Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods](https://mlsanity.com/paper/2405.14273/) (2024)
- [Learning Lagrangian Multipliers for the Travelling Salesman Problem](https://mlsanity.com/paper/2312.14836/) (2023)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [Constraint-Aware Flow Matching: Decision Aligned End-to-End Training for Constrained Sampling](https://mlsanity.com/paper/2605.12754/) (2026)
- [Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs](https://mlsanity.com/paper/2607.22263/) (2026)
- [Learning Deterministic Surrogates for Robust Convex QCQPs](https://mlsanity.com/paper/2312.12485/) (2023)
- [DistrictNet: Decision-aware learning for geographical districting](https://mlsanity.com/paper/2412.08287/) (2024)
- [Quantum End-to-End Learning for Contextual Combinatorial Optimization](https://mlsanity.com/paper/2605.20222/) (2026)
- [Self-Supervised Penalty-Based Learning for Robust Constrained Optimization](https://mlsanity.com/paper/2503.05175/) (2025)
- [Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks](https://mlsanity.com/paper/2603.19318/) (2026)
- [PruneShift: A Framework for Evaluating Decision Reliability in Structured Pruning](https://mlsanity.com/paper/2608.29765/) (2026)

## Abstract (arXiv)

Optimization problems with nonlinear cost functions and combinatorial constraints appear in many real-world applications but remain challenging to solve efficiently compared to their linear counterparts. To bridge this gap, we propose SurCo that learns linear underlineSurrogate costs which can be used in existing underlineCombinatorial solvers to output good solutions to the original nonlinear combinatorial optimization problem. The surrogate costs are learned end-to-end with nonlinear loss by differentiating through the linear surrogate solver, combining the flexibility of gradient-based methods with the structure of linear combinatorial optimization. We propose three textttSurCo variants: textttSurCo-textttzero for individual nonlinear problems, textttSurCo-textttprior for problem distributions, and textttSurCo-texttthybrid to combine both distribution and problem-specific information. We give theoretical intuition motivating textttSurCo, and evaluate it empirically. Experiments show that textttSurCo finds better solutions faster than state-of-the-art and domain expert approaches in real-world optimization problems such as embedding table sharding, inverse photonic design, and nonlinear route planning.