Emir Demirović: An Interactive journey through combinatorial optimization: resilient solutions, multiple objectives, and logic-based approaches for timetabling

Hi all,

Please join us for a TCS seminar on Tuesday May 16 at 10:15 in 4523 with Emir Demirović from Technische Universität Wien.

The first part of this seminar will be a standard 45-50-minute self-contained presentation accessible to a general CS audience. After a break, those who so wish can stay for a second part of roughly two hours with a more technical presentation and discussions. See the title and abstract below for more details.

Those who register in advance at this doodle  will be offered a light lunch (salad, wrap, or similar) around noon. Please register with your full name, and please do so at the latest on Sunday evening May 14. Spontaneous visitors are still very welcome, but there will be no extra food.

ABSTRACT

In this presentation, a range of combinatorial optimization topics will be covered, where the audience will dictate the flow according to their interest. Therefore, it is meant to be an interactive presentation. The topics are as follows:

1) Solving the general high school timetabling (XHSTT) problem using logic-based approaches: maxSAT, SMT-bitvector theory, and a hybrid algorithm which combines maxSAT with large neighborhood search (metaheuristic algorithm). These approaches are state-of-the-art for XHSTT, outperforming the competition on numerous benchmarks.

2) Computing the "representative" subset of all Pareto optimal solutions for multi-objective optimization problems is known to be \(\sigma^{P_2}\)-hard. We will see a shift in complexity to NP-hardness when considering an approximation using the notion of egalitarian solutions, and discuss algorithms for its computation.

3) For practical applications, it is important to compute solutions that remain "stable" after unexpected changes to the problem happen (e.g. new constraints are added post-solving). We will formally define the problem for set covering and set partitioning, prove \(\sigma^{P_3}\)- and \(\sigma^{P_2}\)-hardness (respectively), and analyze algorithms for computing such "resilient" solutions.