A general optimization solver based on OP-to-MaxSAT reduction

• URL: http://arxiv.org/abs/2604.21961v1
• Date: Thu, 23 Apr 2026 16:03:12 GMT
• Title: A general optimization solver based on OP-to-MaxSAT reduction
• Abstract summary: We propose an automated reduction method named OP-to-MaxSAT reduction and a general optimization solver based on OP-to-MaxSAT reduction.<n>GORED unifies the solving of multiple types of optimization problems by reducing the problems from optimization problems to MaxSAT instances in time.<n>GORED not only successfully solves a wide range of optimization problems but also yields solutions comparable to those from existing methods, with no statistically significant differences observed.
• Score: 34.58535273116843
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization problems are fundamental in diverse fields, such as engineering, economics, and scientific computing. However, current algorithms are mostly designed for specific problem types and exhibit limited generality in solving multiple types of optimization problems. To enhance generality, we propose an automated reduction method named OP-to-MaxSAT reduction and a general optimization solver based on OP-to-MaxSAT reduction (GORED). GORED unifies the solving of multiple types of optimization problems by reducing the problems from optimization problems to MaxSAT instances in polynomial time and solving them using the state-of-the-art MaxSAT solver. The generality and solution quality of GORED are validated through experiments on 136 instances across 11 types of optimization problems. Experimental results demonstrate that GORED not only successfully solves a wide range of optimization problems but also yields solutions comparable in quality to those from existing methods, with no statistically significant differences observed. By introducing automated reduction, this work shifts the paradigm of optimization solvers from designing specialized algorithms for each problem type to employing a single algorithm for diverse problems. As a result, advances in this single algorithm can now drive progress in a wide range of optimization problems across various domains.

Related papers

• Optimizing Optimizers for Fast Gradient-Based Learning [53.81268610971847]
  We lay the theoretical foundation for automating design in gradient-based learning.<n>By treating gradient loss signals as a function that translates to parameter motions, the problem reduces to a family of convex optimization problems.
  arXiv  Detail & Related papers  (2025-12-06T09:50:41Z)
• Feature-based Evolutionary Diversity Optimization of Discriminating Instances for Chance-constrained Optimization Problems [9.617143859697322]
  We evolve benchmarking instances for chance-constrained optimization problems that contain components characterized by their expected values and variances.<n>Our method successfully generates diverse instances based on different features while effectively distinguishing the performance between a pair of algorithms.
  arXiv  Detail & Related papers  (2025-01-24T06:55:54Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications.<n>We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance.<n>We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• 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)
• BMR and BWR: Two simple metaphor-free optimization algorithms for solving real-life non-convex constrained and unconstrained problems [0.5755004576310334]
  Two simple yet powerful optimization algorithms, named the Best-MeanRandom (BMR) and Best-Worst-Random (BWR) algorithms, are developed and presented in this paper.
  arXiv  Detail & Related papers  (2024-07-15T18:11:47Z)
• 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)
• Enhanced Opposition Differential Evolution Algorithm for Multimodal Optimization [0.2538209532048866]
  Most of the real-world problems are multimodal in nature that consists of multiple optimum values. Classical gradient-based methods fail for optimization problems in which the objective functions are either discontinuous or non-differentiable. We have proposed an algorithm known as Enhanced Opposition Differential Evolution (EODE) algorithm to solve the MMOPs.
  arXiv  Detail & Related papers  (2022-08-23T16:18:27Z)
• 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)
• PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems [0.0]
  The proposed algorithm is based on solving a set of surrogate problems defined by models of the real one. Our algorithm also performs a meta-search for optimal surrogate models and navigation strategies for the optimization landscape.
  arXiv  Detail & Related papers  (2021-03-19T11:18:03Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs [5.486093983007419]
  We propose a simple, fast, and general algorithm framework based on advanced automatic differentiation technique empowered by deep learning frameworks. High-quality solutions can be obtained with much less time consuming compared to traditional approaches.
  arXiv  Detail & Related papers  (2020-04-14T14:11:00Z)

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.