Partial Constraint Satisfaction Problems and Guided Local Search

Abstract

A largely unexplored aspect of Constraint Satisfaction Problem (CSP) is that of overconstrained instances for which no solution exists that satisfies all the constraints. In these problems, mentioned in the literature as Partial Constraint Satisfaction Problems (PCSPs), we are often looking for solutions which violate the minimum number of constraints. In more realistic settings, constraints violations incur different costs and solutions are sought that minimize the total cost from constraint violations and possibly other criteria. Problems in this category present enormous difficulty to complete search algorithms. In practical terms, complete search has more or less to resemble the traditional Branch and Bound taking no advantage of the efficient pruning techniques recently developed for CSPs. In this report, we examine how the stochastic search method of Guided Local Search (GLS) can be applied to these problems. The effectiveness of the method is demonstrated on instances of the Radio Link Frequency Assignment Problem (RLFAP), which is a real-world Partial CSP. Guided Local Search holds the best known solutions for many of the publicly available instances of RLFAP.