Constraint satisfaction problem using modified branch and bound algorithm

Abstract

A constraint satisfaction problem (CSP) involves assigning possible values to a set of variables without defying any constraints. There are various techniques available to solve or give partial solution to CSP. This paper presents a modification of branch and bound algorithm, which is used to solve a constraint satisfaction problem in map colouring problem. There are two constraints involved which are only three colours are allowed to be used and adjacent regions in the map must not be of the same colour. The modified branch and bound algorithm uses back jumping when it encounters a dead-end in the search. Static variable ordering was also applied to aid the searching process. The modified branch and bound algorithm shows a better result in terms of the number of nodes instantiated and the reduced number of backtracking at dead ends. The result illustrated that the modified branch and bound algorithm with the use of variable ordering technique is better if compared to backjumping. Thus, it is concluded that the modified branch and bound algorithm would improve constraint satisfaction problem.