Why cumulative decomposition is not as bad as it sounds

Schutt, A., Feydy, T., Stuckey, P. J. & Wallace, M. G. (2009). Why cumulative decomposition is not as bad as it sounds. Gent, IP (Ed.) Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, 5732 LNCS, pp.746-761. SPRINGER-VERLAG BERLIN. https://doi.org/10.1007/978-3-642-04244-7_58.

Access Status

This item is currently not available from this repository

URI

https://hdl.handle.net/11343/26738

DOI

10.1007/978-3-642-04244-7_58

Description

International Conference on Principles and Practice of Constraint Programming (CP)

Abstract

The global cumulative constraint was proposed for modelling cumulative resources in scheduling problems for finite domain (FD) propagation. Since that time a great deal of research has investigated new stronger and faster filtering techniques for cumulative, but still most of these techniques only pay off in limited cases or are not scalable. Recently, the “lazy clause generation” hybrid solving approach has been devised which allows a finite domain propagation engine possible to take advantage of advanced SAT technology, by “lazily” creating a SAT model of an FD problem as computation progresses. This allows the solver to make use of SAT nogood learning and autonomous search capabilities. In this paper we show that using lazy clause generation where we model cumulative constraint by decomposition gives a very competitive implementation of cumulative resource problems. We are able to close a number of open problems from the well-established PSPlib benchmark library of resource-constrained project scheduling problems.

Keywords

Computer Software not elsewhere classified; Computer Software and Services not elsewhere classified

Publisher URL

https://doi.org/10.1007/978-3-642-04244-7_58

Collections

Computing and Information Systems - Research Publications
Minerva Elements Records