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

Abstract

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