Solve Your Problem Faster - by changing the model

Abstract

Suppose we are solving a finite domain constraint satisfaction or optimization problem with a constraint programming toolkit that provides as standard a systematic search algorithm combined with constraint propagation. Even with the solution method prescribed in this way, there are very many choices to be made, in representing the underlying problem as a CSP and in solving it. Changing from one not obviously bad set of choices to a better set can make orders of magnitude difference in the time to solve the problem. In this talk I consider several different aspects of modelling, including:

• symmetry breaking;
• choosing the variables;
• adding constraints;
• search strategies for optimization problems;