A synchronized sweep algorithm for the \(k\)-dimensional cumulative constraint. (English) Zbl 1382.68225

Letort, Arnaud; Carlsson, Mats; Beldiceanu, Nicolas

Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 144-159 (2013).

Summary: This paper presents a sweep based algorithm for the \(k\)-dimensional cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given \(n\) tasks and \(k\) resources, this algorithm has a worst-case time complexity of \(O(kn ^{2})\) but scales well in practice. In greedy assignment mode, it handles up to 1 million tasks with 64 resources in one single constraint in SICStus. In filtering mode, on our benchmarks, it yields a speed-up of about \(k ^{0.75}\) when compared to its decomposition into \(k\) independent cumulative constraints.
For the entire collection see [Zbl 1263.68017].

MSC:

68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27	Combinatorial optimization

Software:

PSPLIB