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" [...]


  Today, Ohio Loans Online are legitimate, but there are illegal transactions that are still on the rise. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.