Constraint optimization is today a de facto practical approach to efficiently solving various types of NP-hard optimization problems arising from real-world settings. This is primarily due to significant advances in practical algorithms and implementation-level techniques, which have resulted in increasingly efficient and robust constraint optimization solvers for a range of NP-hard declarative languages. However, the need for even more efficient and robust constraint optimization solvers continues to grow, as in several contexts more and more complex optimization problems need to be solved.

In recent years, increasingly effective solvers have been developed for various declarative languages. This development included branch-and-cut approaches successfully applied in the realm of mixed integer-linear programming (MIP) and the optimization approaches developed in the constraint programming (CP) community building on global constraints.

Moreover, complementing these more classical approaches, new optimization techniques emerged that harness automated logical reasoning methods. Building on the incremental use of Boolean satisfiability (SAT) solvers to explain unsatisfiability, there has been rapid progress in developing efficient maximum satisfiability (MaxSAT) solvers – the optimization extension of SAT – which has given rise to diverse unsatisfiability-based optimization techniques. Going beyond the pure propositional approach, algorithms behind MaxSAT solvers are extensible to more expressive declarative paradigms such as optimization modulo theories (MaxSMT and OMT), and pseudo-Boolean optimization (PBO), providing complementary solution approaches to techniques more commonly used in MIP and CP.

Despite the evident interconnections between the scientific communities focusing on the development of increasingly effective constraint optimization systems, there have been surprisingly few interactions between these communities. We believe that significant unexplored potential remains for further advancing the state-of-the-art in practical constraint optimization solvers. This Dagstuhl Seminar aims to provide a platform for exploring and harnessing this potential by gathering together researchers from different constraint optimization paradigms. A key objective is to stimulate an increased exchange of ideas between different research communities focused on constraint optimization as well as those developing crucial practical decision oracles which enable unsatisfiability-based constraint optimization. The planned topics to be discussed in the seminar include the development of hybrid optimization techniques that bridge various algorithmic advances; enabling increasing levels of incremental computations in optimization solvers; gearing decision oracles and interfaces specifically for optimization; and developing a deeper understanding of the interplay between problem structure, declarative language choice and the runtime performance of different solving approaches.

Creative Commons BY 4.0

Katalin Fazekas, Matti Järvisalo, Nina Narodytska, and Peter J. Stuckey