Modelling a Permutation Problem

Research Report 2000.18, School of Computer Studies, University of Leeds, June 2000.
Barbara M Smith

Abstract

A problem is presented which can be formulated as a constraint satisfaction problem, and in particular as a permutation problem, i.e. it has the same number of values as variables, all variables have the same domain and each variable must be assigned a different value. Different ways of modelling the problem and finding all solutions are investigated. Permutation problems have a dual representation in which the roles of the variables and values are interchanged. It is shown that adding the dual variables to the original model, together with linking constraints, can lead to a much smaller search tree being explored, with little additional overhead. Moreover, the linking constraints remove the need for an allDifferent constraint. Best results are found by using both the original variables and their duals as the search variables, choosing next the variable with smallest domain. It is demonstrated that the order in which values are assigned to a variable can affect the search effort even when finding all solutions using a search algorithm that backtracks chronologically. In this case, choosing the value corresponding to the dual variable with smallest domain can give good results.

Back to "Barbara Smith - Publications on Constraint Programming"