SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems

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.