Savile Row constraint modelling assistant

submited by
Style Pass
2022-01-12 19:30:10

Constraint Programming (CP) is a flexible approach to combinatorial optimization that has been applied to a wide range of important problems. In recent CP conferences we have seen many diverse applications: design problems (design of cryptographic S-boxes, carpet cutting to minimize waste), scheduling (nurse rostering with real-world constraints, resource allocation for datacentres), planning (contingency planning for air traffic control, route finding for international container shipping, assigning service professionals to tasks).

Savile Row is a modelling assistant for CP. It provides a high-level language for the user to specify their constraint problem, and automatically translates that language to the input language of a constraint solver. It is a research tool, so it is designed to be flexible. It is very easy to add new rules and program new translation pipelines.

During the translation process, Savile Row applies some reformulations to improve the model. One interesting class of reformulations is common subexpression elimination (CSE). If the same (or equivalent) expression appears in different parts of a model, CSE replaces the expression with a single variable everywhere it appears. In this way it connects together different expressions in the model. This often improves constraint propagation, and even when it does not do that it can improve the efficiency of a solver by reducing the number of constraints. Savile Row implements several types of CSE, including Associative-Commutative CSE where common sets of terms are factored out of associative-commutative operators such as sums.

Leave a Comment