Parameterised bounds on the sum of variables in time-series constraints

Thumbnail Image
paper.pdf(486.72 KB)
Accepted Version
Beldiceanu, Nicolas
Restrepo, Maria I.
Simonis, Helmut
Journal Title
Journal ISSN
Volume Title
Springer Nature Switzerland AG
Research Projects
Organizational Units
Journal Issue
For two families of time-series constraints with the aggregator Sum and features one and width, we provide parameterised sharp lower and upper bounds on the sum of the time-series variables wrt these families of constraints. This is important in many applications, as this sum represents the cost, for example the energy used, or the manpower effort expended. We use these bounds not only to gain a priori knowledge of the overall cost of a problem, we can also use them on increasing prefixes and suffixes of the variables to avoid infeasible partial assignments under a given cost budget. Experiments show that the bounds drastically reduce the effort to find cost limited solutions.
Time-series constraints , Cost , Cost limited solutions
Beldiceanu, N., Restrepo, M. I. and Simonis, H. (2020) 'Parameterised bounds on the sum of variables in time-series constraints', in Hebrard, E. and Musliu, N. (eds.) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2020. Lecture Notes in Computer Science, Vol. 12296. Springer, Cham, pp. 82-98. doi: 10.1007/978-3-030-58942-4_6
© 2020, Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: