Friday, 10:30 - 10:55 h, Room: H 3005


Jens Schulz
Explanation algorithms in cumulative scheduling

Coauthor: Stefan Heinz


In cumulative scheduling, conflict analysis is one of the key ingredients to solve these problems efficiently. Thereby, the computational complexity of explanation algorithms that explain infeasibilities or bound changes plays an important role. Their role is even more substantial when we are faced with a backtracking system where explanations need to be constructed on the fly. In this talk we present complexity results for computing minimum-size explanations for the propagation algorithms time-tabling, edge-finding, and energetic reasoning. We show that it is possible to compute in polynomial time minimum-size explanations for bound changes which result from energetic reasoning and edge-finding. In case of time-tabling, we prove that an important special case is already weakly NP-hard. In the context of bound-widening, the problems all become NP-hard. To this end, we establish a relation to unsplittable flow problems on the path. We evaluate different heuristic approaches and exact approaches to explain bound changes derived by these algorithms. Using these minimum-size explanations pays off in total compared to using faster but weaker explanation algorithms.


Talk 1 of the invited session Fri.1.H 3005
"Combinatorial optimization in logistics" [...]
Cluster 2
"Combinatorial optimization" [...]


  The deal is that Indiana Loans Online online can save your time, nerves and make a solution of all your financial problems. Female Cialis is prescribed to improve the quality of sexual life, to enhance the sensual reaction. It is also prescribedin case of frigidity and anorgasmia, decreased libido and hormonal changes that cause sexual dysfunction.