SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems

• URL: http://arxiv.org/abs/2210.12547v2
• Date: Wed, 19 Jul 2023 16:16:50 GMT
• Title: SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems
• Abstract summary: We show that $textbfSurCo$ learns linear $underlinetextSur$rogate costs which can be used in existing $underlinetextCo$mbinatorial solvers. Experiments show that $textttSurCo$ finds better solutions faster than state-of-the-art and domain expert approaches.
• Score: 43.95592587141054
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions [52.031993908548294]
  We introduce and $$-weakly $$-up-concavity, a novel first-orderizing condition that characterizes a broad approximation of such functions.<n>Our framework recovers the optimal coefficient for DR-submodular class and significantly improves existing approximation coefficients.
  arXiv  Detail & Related papers  (2026-02-13T22:34:44Z)
• LinearizeLLM: An Agent-Based Framework for LLM-Driven Exact Linear Reformulation of Nonlinear Optimization Problems [1.3854111346209868]
  Reformulating nonlinear optimization problems is largely manual and expertise-intensive.<n>We introduce textitLinearizeLLM, an agent-based framework that solves this task by leveraging Large Language Models (LLMs)<n>The framework assigns each nonlinear pattern to a textitreformulation agent that is explicitly instructed to derive an exact linear reformulation for its nonlinearity pattern.<n>Agents then coordinate to assemble a solver-ready linear model equivalent to the original problem.
  arXiv  Detail & Related papers  (2025-10-12T16:43:21Z)
• Data Selection for ERMs [67.57726352698933]
  We study how well can $mathcalA$ perform when trained on at most $nll N$ data points selected from a population of $N$ points.<n>Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression.
  arXiv  Detail & Related papers  (2025-04-20T11:26:01Z)
• Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
  We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this problem, after selecting a feasible action from the convex decision set $X,$ a convex constraint function is revealed alongside the cost function in each round. We propose a *projection-free* online policy which makes a single call to a Linear Program (LP) solver per round.
  arXiv  Detail & Related papers  (2025-01-28T13:04:32Z)
• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  This paper approaches the problem of $textitautoformulation$: the automated creation of solver-ready optimization models from natural language problem descriptions.<n>We identify three core challenges of autoformulation: $textit(1)$ the vast, problem-dependent hypothesis space, and $textit(2)$ efficient and diverse exploration of this space under uncertainty.<n>We present a novel method leveraging $textitLarge Language Models$ with $textitMonte-Carlo Tree Search$, exploiting the hierarchical nature of optimization modeling to generate and systematically explore possible formulations
  arXiv  Detail & Related papers  (2024-11-03T20:41:38Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify.<n>We consider a fine-grained notion of complexity for solving linear systems, which is motivated by applications where the data exhibits low-dimensional structure.<n>We give a algorithm based on the Sketch-and-Project paradigm, that solves the linear system $Ax = b$, that is, finds $barx$ such that $|Abarx - b| le epsilon |b|$, in time
  arXiv  Detail & Related papers  (2024-05-09T14:56:49Z)
• Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approach [4.422315636150272]
  We investigate the problem of learning an $epsilon$-approximate solution for the discrete-time Linear Quadratic Regulator (LQR) problem. Our method combines both one-point and two-point estimations in a dual-loop variance-reduced algorithm.
  arXiv  Detail & Related papers  (2023-09-19T15:03:18Z)
• Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information [48.784330281177446]
  Recent works in learning-integrated optimization have shown promise in settings where the optimization is only partially observed or where general-purposes perform poorly without expert tuning. We propose using a smooth and learnable Landscape Surrogate as a replacement for $fcirc mathbfg$. This surrogate, learnable by neural networks, can be computed faster than the $mathbfg$ solver, provides dense and smooth gradients during training, can generalize to unseen optimization problems, and is efficiently learned via alternating optimization.
  arXiv  Detail & Related papers  (2023-07-18T04:29:16Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  We present new algorithms for optimizing non-known, non-smooth objectives based on a novel analysis technique. For deterministic second-order smooth objectives, applying advanced optimistic online learning techniques enables a new $O(delta0.5) all$ to recover optimal or best-known results.
  arXiv  Detail & Related papers  (2023-02-07T22:09:20Z)
• Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting [5.199570417938866]
  We study the case where the problem in question is an Linear Program (ILP) We prove that the resulting scheme is compatible with the recently introduced Jacobian-free backpropagation (JFB) Our experiments on two representative ILPs, the shortest path problem and the knapsack problem, demonstrate that this combination-DYS on the forward pass, JFB on the backward pass-yields a scheme which scales more effectively to high-dimensional problems than existing schemes.
  arXiv  Detail & Related papers  (2023-01-31T04:03:28Z)
• Polynomial Optimization: Enhancing RLT relaxations with Conic Constraints [0.0]
  Conic optimization has emerged as a powerful tool for designing tractable and guaranteed algorithms for non-scale problems. We investigate the strengthening of the RLT relaxations of optimization problems through the addition of nine different types of constraints. We show how to design these variants and their performance with respect to each other and with respect to the standard RLT relaxations.
  arXiv  Detail & Related papers  (2022-08-11T02:13:04Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• Efficient Optimization Methods for Extreme Similarity Learning with Nonlinear Embeddings [12.119973339250848]
  We study the problem of learning similarity by using nonlinear embedding models from all possible pairs. This paper aims to extend results for general nonlinear embeddings.
  arXiv  Detail & Related papers  (2020-10-26T12:09:09Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq. We show that an $epsilon$-optimistic controller can be computed efficiently by solving at most $Obig(log (1/epsilon)big)$ Riccati equations.
  arXiv  Detail & Related papers  (2020-07-13T16:30:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.