Title :
Extended analysis of intelligent backtracking algorithms for the maximal constraint satisfaction problem
Author :
Padmanabhuni, Srinivas
Author_Institution :
Dept. of Comput. Sci., Alberta Univ., Edmonton, Alta., Canada
Abstract :
Overconstrained systems refer to sets of soft constraints which do not permit a solution satisfying all the constraints. The overconstrainedness in such soft-constraint systems can be manifested in a wide variety of structures, including weighted constraints, partially ordered constraints, constraint hierarchies and references. The simplest among these formalisms is the maximal constraint satisfaction problem (CSP), where a solution is sought which satisfies the maximum number of constraints. In this paper, backtracking algorithms and their intelligent versions used in the ordinary CSP context, are studied in context of the maximal CSP. The algorithms of E.C. Freuder and R.J. Wallace (1995) for depth-first branch-and-bound and backjumping are extended to conflict-directed backjumping. A theoretical analysis of the problem of application of intelligent backtracking algorithms for maximal CSP is provided.
Keywords :
artificial intelligence; backtracking; constraint theory; operations research; optimisation; tree searching; conflict-directed backjumping; constraint hierarchies; depth-first branch-and-bound technique; intelligent backtracking algorithms; maximal constraint satisfaction problem; maximum constraint number; overconstrained systems; partially ordered constraints; references; soft constraints; weighted constraints; Algorithm design and analysis; Constraint theory; Educational institutions;
Conference_Titel :
Electrical and Computer Engineering, 1999 IEEE Canadian Conference on
Conference_Location :
Edmonton, Alberta, Canada
Print_ISBN :
0-7803-5579-2
DOI :
10.1109/CCECE.1999.804975