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 $\textbf{ SurCo}$ that learns linear $\underline{ \text{ Sur}}$rogate costs which can be used in existing $\underline{ \text{ Co}}$mbinatorial 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 $\texttt{ SurCo}$ variants: $\texttt{ SurCo}-\texttt{ zero}$ for individual nonlinear problems, $\texttt{ SurCo}-\texttt{ prior}$ for problem distributions, and $\texttt{ SurCo}-\texttt{ hybrid}$ to combine both distribution and problem-specific information. We give theoretical intuition motivating $\texttt{ SurCo}$, and evaluate it empirically. Experiments show that $\texttt{ SurCo}$ 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.
Categories: cs.LG cs.AI math.OC