Área: Engenharia Informática e de Computadores

Despacho de nomeação de Júri

Título da Tese: An Over-constrained Approach for Multi-Objective Combinatorial Optimization

Local da Prova: Sala de Reuniões do Departamento de Engenharia Informática (0.19), Pavilhão de Informática II do IST do IST

Data: 26/06/2025

Hora: 14h00
Abstract: Multi-objective optimization generalizes single-objective optimization. Applications range from the Package Upgradability (PU) problem, assignment of Development Assurance Levels (DAL), and the Flying Tourist Problem (FTP), where a tourist wants to schedule an effective plan to visit a number of cities. The hardness of the problem warrants the need for a large range of algorithms that may prove effective for some domains. In particular, Multi-Objective Combinatorial Optimization (MOCO) is amenable to Satisfiability (SAT) based techniques. Incremental approaches have improved the performance of applications based on SAT oracles. In this work, we focus on the development of four incremental, core-guided MOCO solvers. The first three are based on UNSAT-SAT MAxSAT solvers. Core-Guided and Core-Guided-List iteratively expand the search region, starting at the origin, and HittingSets iteratively tightens a relaxation of the original formula, approaching the Pareto front from below. The last of the four, Slide&Drill, follows a SAT-UNSAT approach where the focus of the search moves downward from the maximal point, in a non-greedy way. We also describe a mechanism that coordinates any two solvers, particularly well suited for combining UNSAT-SAT with SAT-UNSAT solvers. We supply empirical validation of the performance of the developed algorithms when pitted against other SAT-based MOCO solvers.