1995 · 63 citations · 12 references
ComputingComputer ScienceAlgorithmsMarkov Decision ProcessesOptimizationConstrained OptimizationConstraint SatisfactionConstraint SolvingOptimization TheoryStochastic OptimizationStochastic ProgrammingConstraint Optimization ProblemsConstraintsCsp SolvingSoft Constraint Satisfaction
Stochastic local search is an effective technique for solving certain classes of large, hard propositional satisfiability problems, including propositional encodings of problems such as circuit synthesis and graph coloring (Selman, Levesque, and Mitchell 1992; Selman, Kautz, and Cohen 1994). Many problems of interest to AI and operations research cannot be conveniently encoded as simple satisfiability, because they involve both hard and soft constraints -- that is, any solution may have to violate some of the less important constraints. We show how both kinds of constraints can be handled by encoding problems as instances of weighted MAX-SAT (finding a model that maximizes the sum of the weights of the satisfied clauses that make up a problem instance). We generalize our local-search algorithm for satisfiability (GSAT) to handle weighted MAX-SAT, and present experimental results on encodings of the Steiner tree problem, which is a well-studied hard combinatorial search problem. On many problems this approach turns out to be competitive with the best current specialized Steiner tree algorithms developed in operations research. Our positive results demonstrate that it is practical to use domain-independent logical representations with a general search procedure to solve interesting classes of hard combinatorial search problems.
12
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text
A new method for solving hard satisfiability problems
Bart Selman, Hector J. Levesque, David G. M. Mitchell · 1992 · 1.2K citations
Henry Kautz, Bart Selman · 1992 · 828 citations
Algorithms for the maximum satisfiability problem
Pierre Hansen, Brigitte Jaumard · Computing · 1990 · 345 citations