ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization

• URL: http://arxiv.org/abs/2407.21729v1
• Date: Wed, 31 Jul 2024 16:30:04 GMT
• Title: ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization
• Authors: Zhihan Chen, Peng Lin, Hao Hu, Shaowei Cai,
• Abstract summary: A representative local search solver for PBO is LSPBO. We improve LSPBO by a dynamic scoring mechanism, which dynamically strikes a balance between score on hard constraints and score on the objective function. On top of this improved LSPBO, we develop the first parallel local search PBO solver.
• Score: 14.371138535749036
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative local search solver for PBO is LSPBO. In this paper, firstly, we improve LSPBO by a dynamic scoring mechanism, which dynamically strikes a balance between score on hard constraints and score on the objective function. Moreover, on top of this improved LSPBO , we develop the first parallel local search PBO solver. The main idea is to share good solutions among different threads to guide the search, by maintaining a pool of feasible solutions. For evaluating solutions when updating the pool, we propose a function that considers both the solution quality and the diversity of the pool. Furthermore, we calculate the polarity density in the pool to enhance the scoring function of local search. Our empirical experiments show clear benefits of the proposed parallel approach, making it competitive with the parallel version of the famous commercial solver Gurobi.

Related papers

• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  The Random-Key hubs (RKO) is a versatile and efficient local search method tailored for optimization problems. Using the random-key concept, RKO encodes solutions as vectors of random keys that are subsequently decoded into feasible solutions via problem-specific decoders. The RKO framework is able to combine a plethora of classic metaheuristics, each capable of operating independently or in parallel, with solution sharing facilitated through an elite solution pool.
  arXiv  Detail & Related papers  (2024-11-06T22:23:29Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. 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)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming [3.759879849096294]
  We propose Large Neighborhood Prioritized Search (LNPS) for solving optimization problems in Answer Set Programming (ASP) LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization.
  arXiv  Detail & Related papers  (2024-05-18T14:37:43Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO) Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
  arXiv  Detail & Related papers  (2024-02-05T02:54:50Z)
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA [4.670374869377859]
  A core step in solving optimization problems with quantum algorithms is the problem formulation. Recent studies show that many problems can be solved more efficiently in their native Polynomial Unconstrained Optimization forms. Our evaluation on suitable benchmark functions, shows that PUBO formulations generally yield better results, while requiring less qubits.
  arXiv  Detail & Related papers  (2023-05-05T09:37:48Z)
• DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
  We find two ways to improve the local search algorithms in solving Pseudo-Boolean Optimization (PBO) Our algorithm DeciLS-PBO has a promising performance compared to the state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-01-28T17:03:56Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions [18.570591025615453]
  This paper develops a multimodal BO framework to find a set of local/global solutions for expensive-to-evaluate multimodal objective functions. We analytically derive the joint distribution of the objective function and its first-order derivatives. We introduce variants of the well-known BO acquisition functions to the multimodal setting and demonstrate the performance of the proposed framework.
  arXiv  Detail & Related papers  (2022-10-13T00:10:13Z)
• 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)

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.