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

Beldiceanu, Nicolas; Restrepo, Maria I.; Simonis, Helmut

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

Files

paper.pdf(486.72 KB)

Accepted Version

Date

2020-09-19

Authors

Beldiceanu, Nicolas

Restrepo, Maria I.

Simonis, Helmut

Publisher

Springer Nature Switzerland AG

Published Version

10.1007/978-3-030-58942-4_6

Abstract

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.

Keywords

Time-series constraints , Cost , Cost limited solutions

Citation

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

Copyright

© 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: https://doi.org/10.1007/978-3-030-58942-4_6

Full item page