00:00/00:00 </>
​7730.mp4
​7730.mp3

Slide&Drill, a new Approach for Multi-Objective Combinatorial Optimization

Full Text
Share
Joao Cortes, from INESC ID, from Lisboa, tells about the successful use of Propositional Satisfiability (SAT) algorithms in Boolean optimization (e.g., Maximum Satisfiability), several SAT-based algorithms have been proposed for Multi-Objective Combinatorial Optimization (MOCO). However, these new algorithms either provide a small subset of the Pareto front or follow a more exploratory search procedure and the solutions found are usually distant from the Pareto front. We extend the state of the art with a new SAT-based MOCO solver, Slide and Drill (Slide&Drill), that hones an upper bound set of the exact solution. Moreover, we show that Slide&Drill neatly complements proposed UNSAT-SAT algorithms for MOCO. These algorithms can work in tandem over the same shared “blackboard” formula, in order to enable a faster convergence. Experimental results in several sets of benchmark instances show that Slide&Drill can outperform other SAT-based algorithms for MOCO, in particular when paired with previously proposed UNSAT-SAT algorithms ​
This document is licensed under a Creative Commons:Attribution – Non commercial – Share alike (by-nc-sa) Creative Commons by-nc-sa4.0