Optimization problems with expensive nonlinear cost functions and
combinatorial constraints appear in many real-world applications, but remain
challenging to solve efficiently. Existing combinatorial solvers like Mixed
Integer Linear Programming can be fast in practice but cannot readily optimize
nonlinear cost functions, while general nonlinear optimizers like gradient
descent often do not handle complex combinatorial structures, may require many
queries of the cost function, and are prone to local optima. To bridge this
gap, we propose SurCo that learns linear Surrogate costs which can be used by
existing Combinatorial solvers to output good solutions to the original
nonlinear combinatorial optimization problem, combining the flexibility of
gradient-based methods with the structure of linear combinatorial optimization.
We learn these linear surrogates end-to-end with the nonlinear loss by
differentiating through the linear surrogate solver. Three variants of SurCo
are proposed: SurCo-zero operates on individual nonlinear problems, SurCo-prior
trains a linear surrogate predictor on distributions of problems, and
SurCo-hybrid uses a model trained offline to warm start online solving for
SurCo-zero. We analyze our method theoretically and empirically, showing smooth
convergence and improved performance. Experiments show that compared to
state-of-the-art approaches and expert-designed heuristics, SurCo obtains lower
cost solutions with comparable or faster solve time for two realworld
industry-level applications: embedding table sharding and inverse photonic
design.

提出一种通过学习线性代理成本来优化实际应用中的组合优化问题的方法，该方法结合了基于梯度的方法的灵活性和线性组合优化的结构，通过 SurCo-hybrid、SurCo-prior 和 SurCo-zero 三种变体的实验结果表明，该方法能够产生低成本的解决方案，具有可比或更快的求解时间。