Exact and approximate determination of the Pareto set using minimal correction subsets - Andreia Guerreiro, INESC-ID, Portugal

10 mai 22
Room A411 13h45-15h15

Logic-based algorithms relying on the enumeration of Minimal Correction Subsets (MCSs) have been recently used for solving multiobjective Boolean optimization (MOBO) problems. The effectiveness of this approach relies on how the MOBO problem is encoded as a MaxSAT problem. This talk discusses the connection of Pareto-optimal solutions of a MOBO problem and MCSs. In particular, two approximation versions of the encoding of the objective functions to MaxSAT are discussed, for which enumerating all MCSs results in finding an approximation of the Pareto front with a priori guarantee.