Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization

• URL: http://arxiv.org/abs/2504.08315v1
• Date: Fri, 11 Apr 2025 07:36:43 GMT
• Title: Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization
• Authors: Kyo Kuroki, Thiem Van Chu, Masato Motomura, Kazushi Kawamura,
• Abstract summary: This paper theoretically analyzes Mean Field Annealing (MFA) and its variants.<n>It proposes a novel method, the Annealed Mean Field Descent (AMFD), which is designed to address this limitation.<n>AMFD exhibits superior performance in many cases and reduced problem dependence compared to state-of-the-art QUBO solvers and Gurobi.
• Score: 2.2070611256611627
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, formulating various combinatorial optimization problems as Quadratic Unconstrained Binary Optimization (QUBO) has gained significant attention as a promising approach for efficiently obtaining optimal or near-optimal solutions. While QUBO offers a general-purpose framework, existing solvers often struggle with performance variability across different problems. This paper (i) theoretically analyzes Mean Field Annealing (MFA) and its variants--which are representative QUBO solvers, and reveals that their underlying self-consistent equations do not necessarily represent the minimum condition of the Kullback-Leibler divergence between the mean-field approximated distribution and the exact distribution, and (ii) proposes a novel method, the Annealed Mean Field Descent (AMFD), which is designed to address this limitation by directly minimizing the divergence. Through extensive experiments on five benchmark combinatorial optimization problems (Maximum Cut Problem, Maximum Independent Set Problem, Traveling Salesman Problem, Quadratic Assignment Problem, and Graph Coloring Problem), we demonstrate that AMFD exhibits superior performance in many cases and reduced problem dependence compared to state-of-the-art QUBO solvers and Gurobi--a state-of-the-art versatile mathematical optimization solver not limited to QUBO.

Related papers

• The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA [0.3774866290142281]
  The quantum approximate optimization algorithm (QAOA) is designed to determine optimum and near optimum solutions of quadratic (and higher order) unconstrained binary optimization problems.<n>We introduce our innovative profit-relaxation framework to solve constrained optimization problems.
  arXiv  Detail & Related papers  (2025-03-13T05:57:40Z)
• Non-Myopic Multi-Objective Bayesian Optimization [64.31753000439514]
  We consider the problem of finite-horizon sequential experimental design to solve multi-objective optimization problems. This problem arises in many real-world applications, including materials design. We propose the first set of non-myopic methods for MOO problems.
  arXiv  Detail & Related papers  (2024-12-11T04:05:29Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  We show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario. We follow by submitting instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios.
  arXiv  Detail & Related papers  (2024-06-11T19:59:05Z)
• Deriving Compact QUBO Models via Multilevel Constraint Transformation [0.8192907805418583]
  We propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables. For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.
  arXiv  Detail & Related papers  (2024-04-04T17:34:08Z)
• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  We tackle the problem of computing a sequence of rankings with the guarantee of the Pareto-optimal balance between consumers and producers of items. We introduce a novel approach to the above problem by using the Expohedron - a permutahedron whose points represent all exposures of items. We further propose an efficient method by relaxing our optimization problem on the Expohedron's circumscribed $n$-sphere, which significantly improve the running time.
  arXiv  Detail & Related papers  (2024-02-22T05:48:54Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) is a conceptually simple, deterministic approach that avoids constraint approximations. We show that CUQB significantly outperforms traditional Bayesian optimization in both constrained and unconstrained cases.
  arXiv  Detail & Related papers  (2023-05-05T19:57:36Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

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.