Hybrid Algorithms For The Constraint Satisfaction Problem

Computational Intelligence, Volume 9 , Number 3 , 1993

HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION
PROBLEM
PATRICK
PROSSER
Department of Computer Science
Universio of Strarhclyde, Livingstone Tower
Glasgow GI I X H , Scotland

e-mail: pat@cs.strath.ac.uk
It might be said that there are five basic tree search algorithms for the constraint satisfaction
problem (csp), namely,naive backtracking (BT), backjumping (BJ), conflict-directed backjumping
(CBJ), backmarking (BM), and forward checking (FC). In broad terms, BT, BJ, and CBJ describe
different styles of backward move (backtracking), whereas BT, BM, and FC describe different styles
of forward move (labeling of variables). This paper presents an approach that allows base algorithms
to be combined, giving us newhybrids. The base algorithms are described explicitly, in terms of a
forward move and a backward move. It is then shown that the forward move of one algorithm may be
combined with the backward move of another, giving a new hybrid. In total, four hybrids are presented:
backmarking with backjumping (BMJ), backmarking with conflict-directed backjumping (BM-CBJ),
forward checking with backjumping(FC-BJ), and forward checking with conflict-directed backjumping
(FC-CBJ). The performances of the nine algorithms (BT, BJ, CBJ, BM, B MJ, BM-CBJ, FC, FC-BJ,
FC-CBJ) are compared empirically, using 450 instances of the ZEBRA problem, and it is s hown that
FC-CBJ is by far the best of the algorithms examined.
K ey words: constraint satisfaction problem, tree search algorithms, backtracking,backjumping,
backmarking, forward checking.

1.

INTRODUCTION

T he work reported in this paper was motivated by the following questions posed by
Nadei (1989):
Something to think about would be a synthesis of BM and BJ, into an algorithm called,
say, BMJ (BackMarkJump). . . . Is it possible to combine both approaches while retaining
all, or most, of the power of each?
and further:Combiningj-consistency with Backjump or Backmark should be possible, as suggested b y
Gaschnig. And Backmark and Backjump may themselves perhaps be combined. . . . Such
algorithms deserve attention.
This paper presents four "hybrid" tree search algorithms (algorithms created by combining
the forward move of one algorithm with the backward move of another) for the constraint
satisfaction problem (csp),one of these being BMJ. In addition, an algorithm which
combines 2-consistency with backjumping is also presented. The technique of combining
algorithms is presented, along with an empirical analysis of nine tree search algorithms.
There appear to be five basic tree search algorithms for the constraint satisfaction
problem, namely naive backtracking (BT) (Golomb and Baumert 1 963, backjumping(BJ)
(Gaschnig 1979), conflict-directed backjumping (CBJ, a new algorithm described later o n),
b ackmarking (BM) (Gaschnig 1977, 1979), and forward checking (FC) (Haralick and Elliott
1980). I n b road terms these algorithms might be classified as follows: BT, B M, and FC
D 1 993, Blackwell Publishers, 238 Main Street, Cambridge, M A 02142, U SA, and 108 Cowley Road, Oxford, OX4 IJF, U K.H YBRID ALGORITHh4S FOR T HE CONSTRAINT S ATISFACTION P ROBLEM

2 69

GO
Back

BT

BJ

CBJ

Go
Forward

F IGURE. The five base algorithms.
1

chronologically backtrack, wherleas BJ and CBJ are informed backtrackers. BT, BM, BJ,
and CBJ check backwards, from the current variable against the past variable, whereas
FC checks forward, from the current variable against the futurevariables.
The algorithms may be viewed from a different perspective. When we move from
BT 3 BJ -+ C BJ we move progressively toward more informed styles of backtracking.
However, BT, BJ, and CBJ all use the same style of forward move (labeling of variables).
When we move from BT + BM + F C we traverse across different styles of forward
move, but again each of these algorithms use the same...