CP 2024 Presentation (ParLS-PBO)
Image credit: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 LS-PBO. In this paper, firstly, we improve LS-PBO 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 LS-PBO, 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.
Date
Sep 3, 2024 12:00 AM — 12:00 AM
Event
Location
Girona, Catalonia, Spain
Girona
Click on the Slides button above to view the built-in slides feature.
Slides can be added in a few ways:
- Create slides using Hugo Blox Builder’s Slides feature and link using
slidesparameter in the front matter of the talk file - Upload an existing slide deck to
static/and link usingurl_slidesparameter in the front matter of the talk file - Embed your slides (e.g. Google Slides) or presentation video on this page using shortcodes.
Further event details, including page elements such as image galleries, can be added to the body of this page.
