Solving Linear Pseudo-Boolean Constraint Problems with Local Search

Joachim P. Walser

Stochastic local search is one of the most successful methods for model finding in propositional satisfiability. However, many combinatorial problems have no concise propositional encoding. In this paper, we show that domain-independent local search for satisfiability (Walksat) can be generalized to handle systems of linear pseudo-Boolean (O-1 integer) constraints, a representation that is widely used in operations research. We introduce the algorithm WSAT (Rb) and demonstrate its potential in two case studies. The first application is an optimization problem from radar surveillance. Experiments on problems of realistic size show that WSAT (Pb) is an efficient heuristic to find good approximate solutions. For most of the test problems, it found provably optimal solutions. In the second case study, we show that pseudo-Boolean local search can efficiently solve the progressive party problem, a problem that is hard for constraint programming with chronological backtracking, and whose O-1 encoding is beyond the size limitations of integer linear programming.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.