Incomplete dynamic backtracking for linear pseudo-Boolean problems

Incomplete dynamic backtracking for linear pseudo-Boolean problems

0.00 Avg rating0 Votes
Article ID: iaor2005734
Country: Netherlands
Volume: 130
Issue: 1
Start Page Number: 57
End Page Number: 73
Publication Date: Aug 2004
Journal: Annals of Operations Research
Authors:
Abstract:

Many combinatorial problems can be modeled as 0/1 integer linear programs. Problems expressed in this form are usually solved by Operations Research algorithms, but good results have also been obtained using generalised SAT algorithms based on backtracking or local search, after transformation to pseudo-Boolean form. A third class of SAT algorithm uses non-systematic backtracking to combine constraint propagation with local search-like scalability, at the cost of completeness. This paper describes such an algorithm for pseudo-Boolean models. Experimental results on a variety of problems are encouraging, in some cases yielding improved solutions or performance compared to previous algorithms.

Reviews

Required fields are marked *. Your email address will not be published.