Improving linear constraint propagation by changing constraint representation

Warwick Harvey, Peter J. Stuckey

    Research output: Contribution to journalArticleResearchpeer-review

    26 Citations (Scopus)

    Abstract

    Propagation based finite domain solvers provide a general mechanism for solving combinatorial problems. Different propagation methods can be used in conjunction by communicating through the domains of shared variables. The flexibility that this entails has been an important factor in the success of propagation based solving for solving hard combinatorial problems. In this paper we investigate how linear integer constraints should be represented in order that propagation can determine strong domain information. We identify two kinds of substitution which can improve propagation solvers, and can never weaken the domain information. This leads us to an alternate approach to propagation based solving where the form of constraints is modified by substitution as computation progresses. We compare and contrast a solver using substitution against an indexical based solver, the current method of choice for implementing propagation based constraint solvers, identifying the relative advantages and disadvantages of the two approaches. In doing so, we investigate a number of choices in propagation solvers and their effects on a suite of benchmarks.

    Original languageEnglish
    Pages (from-to)173-207
    Number of pages35
    JournalConstraints
    Volume8
    Issue number2
    DOIs
    Publication statusPublished - 1 Apr 2003

    Keywords

    • Finite domain constraint solving
    • Linear integer constraints
    • Propagation methods

    Cite this