An Overconstrained Approach for Multi-Objective Combinatorial Optimization

access_time January 29, 2020 at 03:00PM until January 29, 2020 at 04:00PM
place Room E2 (Piso -1), Torre Norte, IST, Alameda

Complete methods for solving Multi-Objective Combinatorial Optimization (MOCO) problems are usually based in the classic branch and bound techniques. More recently, new constraint-based algorithms have been proposed based on the enumeration of $P$-minimal models or the enumeration of Minimal Correction Subsets (MCSs). In single-objective optimization problems such as Maximum Satisfiability (MaxSAT), several state of the art algorithms are based on over-constrained formulas that are iteratively relaxed until an optimal solution is found. In this work, we propose the first algorithm for MOCO based on over-constrained formulas. Moreover, our algorithm naturally takes advantage of incrementality commonly used in unsatisfiability-based MaxSAT algorithms.

local_offer Research topics
person Candidate: João O'Neill Cortes
supervisor_account Advisor: Prof. Vasco Manquinho / Prof.ª Inês Lynce