Conjunctive width heuristics for maximal constraint satisfaction

A constraint satisfaction problem may not admit a complete solution; in this case a good partial solution may be acceptable. This paper presents new techniques for organizing search with branch and bound algorithms so that maximal partial solutions (those having the maximum possible number of satisfied constraints) can be obtained in reasonable time for moderately sized problems. The key feature is a type of variable-ordering heuristic that combines width at a node of the constraint graph (number of constraints shared with variables already chosen) with factors such as small domain size that lead to inconsistencies in values of adjacent variables. Ordering based on these heuristics leads to a rapid rise in branch and bound's cost function together with local estimates of future cost, which greatly enhances lower bound calculations. Both retrospective and prospective algorithms based on these heuristics are dramatically superior to earlier branch and bound algorithms developed for this domain.