Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization

• URL: http://arxiv.org/abs/2502.19377v2
• Date: Mon, 26 May 2025 15:09:44 GMT
• Title: Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization
• Authors: Arman Mielke, Uwe Bauknecht, Thilo Strauss, Mathias Niepert,
• Abstract summary: Combinatorial optimization (CO) problems arise across a broad spectrum of domains, including medicine, logistics, and manufacturing.<n>We propose a learning-based approach that enhances existing non-learned approximation algorithms for CO.<n>Our method is trained end-to-end in a self-supervised fashion, using a novel gradient estimation scheme that treats the approximation algorithm as a black box.
• Score: 15.102119312523696
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Combinatorial optimization (CO) problems arise across a broad spectrum of domains, including medicine, logistics, and manufacturing. While exact solutions are often computationally infeasible, many practical applications require high-quality solutions within a given time budget. To address this, we propose a learning-based approach that enhances existing non-learned approximation algorithms for CO. Specifically, we parameterize these approximation algorithms and train graph neural networks (GNNs) to predict parameter values that yield near-optimal solutions. Our method is trained end-to-end in a self-supervised fashion, using a novel gradient estimation scheme that treats the approximation algorithm as a black box. This approach combines the strengths of learning and traditional algorithms: the GNN learns from data to guide the algorithm toward better solutions, while the approximation algorithm ensures feasibility. We validate our method on two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the minimum k-cut problem. Our results demonstrate that the proposed approach is competitive with state-of-the-art learned CO solvers.

Related papers

• Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach [5.84228364962637]
  We present a meta-optimization method that learns efficient algorithms to approximate optimization problems.<n>We prove exponential convergence, approximation guarantees, and generalization bounds for our learning method.<n>This method offers superior computational efficiency, producing high-quality approximations faster and scaling better with problem size compared to existing techniques.
  arXiv  Detail & Related papers  (2025-05-16T15:27:50Z)
• Primal-dual algorithm for contextual stochastic combinatorial optimization [1.4999444543328293]
  This paper introduces a novel approach to contextual optimization, integrating operations research and machine learning to address decision-making under uncertainty.<n>Our goal is to minimize the empirical risk, which is estimated from past data on uncertain parameters and contexts.
  arXiv  Detail & Related papers  (2025-05-07T19:37:12Z)
• Learning based convex approximation for constrained parametric optimization [11.379408842026981]
  We propose an input neural network (ICNN)-based self-supervised learning framework to solve constrained optimization problems.<n>We provide rigorous convergence analysis, showing that the framework converges to a Karush-Kuhn-Tucker (KKT) approximation point of the original problem.<n>Our approach achieves a superior balance among accuracy, feasibility, and computational efficiency.
  arXiv  Detail & Related papers  (2025-05-07T00:33:14Z)
• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  We use predictions to improve over approximation guarantees of classic algorithms. Our algorithms produce optimal solutions when provided with perfect predictions. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds.
  arXiv  Detail & Related papers  (2024-11-25T17:31:34Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm [0.589889361990138]
  We propose a new metarounding algorithm under a natural assumption that a relax-based approximation algorithm exists for the class. Our algorithm is much more efficient in both theoretical and practical aspects.
  arXiv  Detail & Related papers  (2023-10-19T10:22:03Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• AskewSGD : An Annealed interval-constrained Optimisation method to train Quantized Neural Networks [12.229154524476405]
  We develop a new algorithm, Annealed Skewed SGD - AskewSGD - for training deep neural networks (DNNs) with quantized weights. Unlike algorithms with active sets and feasible directions, AskewSGD avoids projections or optimization under the entire feasible set. Experimental results show that the AskewSGD algorithm performs better than or on par with state of the art methods in classical benchmarks.
  arXiv  Detail & Related papers  (2022-11-07T18:13:44Z)
• The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
  Un differentiation approximates the solution using an iterative solver and differentiates it through the computational path. We show that we can either 1) choose a large learning rate leading to a fast convergence but accept that the algorithm may have an arbitrarily long burn-in phase or 2) choose a smaller learning rate leading to an immediate but slower convergence.
  arXiv  Detail & Related papers  (2022-09-27T09:27:29Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• Consistent Approximations in Composite Optimization [0.0]
  We develop a framework for consistent approximations of optimization problems. The framework is developed for a broad class of optimizations. A programming analysis method illustrates extended nonlinear programming solutions.
  arXiv  Detail & Related papers  (2022-01-13T23:57:08Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• 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)
• Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
  We use a Noise Contrastive approach to motivate a family of surrogate loss functions. We address a major bottleneck of all predict-and-optimize approaches. We show that even a very slow growth rate is enough to match the quality of state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-11-10T19:09:12Z)

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.