Local search (constraint satisfaction)

Last updated November 03, 2020

In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name local search.

All local search algorithms use a function that evaluates the quality of assignment, for example the number of constraints violated by the assignment. This amount is called the cost of the assignment. The aim of local search is that of finding an assignment of minimal cost, which is a solution if any exists.

Point A is not a solution, but no local move from there decreases cost. However, a solution exists at point B. Local-search-plateau.svg — Point A is not a solution, but no local move from there decreases cost. However, a solution exists at point B.

Two classes of local search algorithms exist. The first one is that of greedy or non-randomized algorithms. These algorithms proceed by changing the current assignment by always trying to decrease (or at least, non-increase) its cost. The main problem of these algorithms is the possible presence of plateaus, which are regions of the space of assignments where no local move decreases cost. The second class of local search algorithm have been invented to solve this problem. They escape these plateaus by doing random moves, and are called randomized local search algorithms.

Greedy algorithms

Hill climbing

The most basic form of local search is based on choosing the change that maximally decreases the cost of the solution. This method, called hill climbing, proceeds as follows: first, a random assignment is chosen; then, a value is changed so as to maximally improve the quality of the resulting assignment. If no solution has been found after a given number of changes, a new random assignment is selected. Hill climbing algorithms can only escape a plateau by doing changes that do not change the quality of the assignment. As a result, they can be stuck in a plateau where the quality of assignment has a local maxima.

GSAT (greedy sat) was the first local search algorithm for satisfiability, and is a form of hill climbing.

Constraint weighting or breakout method

A method for escaping from a local minimum is that of using a weighted sum of violated constraints as a measure of cost, and changing some weights when no improving move is available. More precisely, if no change reduces the cost of the assignment, the algorithm increases the weight of constraints violated by the current assignment.

This way, every move that would not otherwise change the cost of the solution decreases it. Moreover, the weight of constraints that remain violated for a large number of moves keeps increasing. Therefore, during a number of moves not satisfying a constraint, the cost of moves to assignments satisfying that constraint keeps increasing.

Tabu search

A drawback of hill climbing with moves that do not decrease cost is that it may cycle over assignments of the same cost. Tabu search^[1]^[2]^[3] overcomes this problem by maintaining a list of "forbidden" assignments, called the tabu list. In particular, the tabu list typically contains only the most recent changes. More precisely, it contains the last variable-value pair such that the variable has been recently assigned to the value.

This list is updated every time the assignment is changed. If a variable is assigned to a value, the variable-value pair is added to the list, and the oldest pair is removed from it. This way, the list only contains the most recent assignments to a variable. If a variable-value pair is in the tabu list, then changing the current assignment by setting the variable to the value is forbidden. The algorithm can only choose the best move among the ones that are not forbidden. This way, it cannot cycle over the same solution unless the number of moves in this cycle is larger than the length of the tabu list.

Random walk

A random walk algorithm sometimes moves like a greedy algorithm but sometimes moves randomly. It depends on a parameter $p$ , which is a real number between 0 and 1. At every move, with probability $p$ the algorithm proceeds like a greedy algorithm, trying to maximally decrease the cost of the assignment. With probability $1-p$ , however, the solution is changed in some other way, which involves some degree of randomness.

WalkSAT

The random move of WalkSAT is changing the value of a random variable of a random violated constraint. For propositional satisfiability of conjunctive normal form formulae, which is the original settings of this algorithm, every such a move changes the value of the variable from true to false or vice versa, and produce the satisfiability of the violated constraint. As for all random walk strategies, a random move is only done with a given probability, and a move maximally decreasing the cost is done otherwise.

Simulated annealing

The technique of simulated annealing is based on changing the probability of doing a random move over one that maximally decreasing the cost. In particular, the name originates from the strategy of decreasing the probability of doing random moves during the execution of the algorithm, thus virtually "freezing" the space of search.

In particular, if the improvement of cost $d$ of a move is negative (the move increases cost), this move is done with probability $e^{-d\cdot T}$ , where $T$ is a real number. Since the probability of doing this move increases with $T$ , this parameter is called the temperature. Simulated annealing decreases this temperature over time, thus allowing more random moves at the beginning and less after time.

Local search on a cycle cutset

Local search usually works on all variables, improving a complete assignment to them. However, local search can also be run on a subset of variables, using some other mechanism for the other variables. A proposed algorithm works on a cycle cutset, which is a set of variables that, if removed from the problem, makes it acyclic.

For any assignment of the variables of the cutset, the remaining problem has a forest as primal graph. As a result, it can be solved efficiently. In order to guide local search, an algorithm detecting the minimal number of constraints that can be violated is used in place of a satisfiability algorithm on the for forest part of the problem.

This minimal number is found by determining the cost of each variable assignment. This cost is the minimal number of constraints violated by an assignment of the variables in the subtree rooted at the variable, when the variable takes the given value. This cost can be calculated as follows. If $Cost(x=a)$ denotes the cost of the assignment $x=a$ and $y_{1},\ldots ,y_{n}$ are the children of $x$ , the following formula holds. In this formula, $Violates(x=a,y_{i}=b)$ is the 0 or 1 depending on whether the assignment $x=a,y_{i}=b$ violates the constraint between $x$ and $y$ .

Cost(x=a)=\sum _{i=1,\ldots ,n}\min _{y_{i}=b}(Cost(y_{i}=b)+Violates(x=a,y_{i}=b))

The cost for variables in the cutset is zero, and these variables are assumed to be allowed to take only their given value. With these assumptions, the above formula allows computing the cost of all variable evaluations by iteratively proceeding bottom-up from the leaves to the root(s) of the forest.

The cost of variable evaluations can be used by local search for computing the cost of a solution. The cost of values of the roots of the forest is indeed the minimal number of violated constraints in the forest for these given values. These costs can therefore used to evaluate the cost of the assignment to the cutset variables and to estimate the cost of similar assignments on the cutset variables.

External links

Forced Satisfiable CSP and SAT Benchmarks of Model RB

Related Research Articles

In logic and computer science, the Boolean satisfiability problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It is often used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent, Branch and Bound.

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In additions to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem specific branching heuristic.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint Programming (CP) is the field of research that specifically focuses on tackling with this kind of problems. Additionally, boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

In computer science, the min conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems (CSP).

In computer science, GSAT and WalkSAT are local search algorithms to solve Boolean satisfiability problems.

In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula in conjunctive normal form, that can be made true by an assignment of truth values to the variables of the formula. It is a generalization of the Boolean satisfiability problem, which asks whether there exists a truth assignment that makes all clauses true.

In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency.

In backtracking algorithms, look ahead is the generic term for a subprocedure that attempts to foresee the effects of choosing a branching variable to evaluate one of its values. The two main aims of look-ahead are to choose a variable to evaluate next and the order of values to assign to it.

In backtracking algorithms, backjumping is a technique that reduces search space, therefore increasing efficiency. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables $is used, but the same considerations apply to a dynamic order of evaluation.$

In constraint satisfaction backtracking algorithms, constraint learning is a technique for improving efficiency. It works by recording new constraints whenever an inconsistency is found. This new constraint may reduce the search space, as future partial evaluations may be found inconsistent without further search. Clause learning is the name of this technique when applied to propositional satisfiability.

In mathematical optimization, constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.

Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is A(X,Y):-X+Y>0,B(X),C(Y). In this clause, X+Y>0 is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.

In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem.

Guided Local Search is a metaheuristic search method. A meta-heuristic method is a method that sits on top of a local search algorithm to change its behavior.

In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence.

MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem 3SAT. In MAXEkSAT, each clause has exactly k literals, each with distinct variables, and is in conjunctive normal form. These are called k-CNF formulas. The problem is to determine the maximum number of clauses that can be satisfied by a truth assignment to the variables in the clauses.

References

↑ Glover, Fred (January 1986). "Future paths for integer programming and links to artificial intelligence". Computers & Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.
↑ Glover, Fred (August 1989). "Tabu Search—Part I". ORSA Journal on Computing. 1 (3): 190–206. doi:10.1287/ijoc.1.3.190. ISSN 0899-1499.
↑ Glover, Fred (February 1990). "Tabu Search—Part II". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4. ISSN 0899-1499.

Dechter, Rina (2003). Constraint Processing . Morgan Kaufmann. ISBN 978-1-55860-890-0.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Glover, Fred (January 1986). "Future paths for integer programming and links to artificial intelligence". Computers & Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.

[2] Glover, Fred (August 1989). "Tabu Search—Part I". ORSA Journal on Computing. 1 (3): 190–206. doi:10.1287/ijoc.1.3.190. ISSN 0899-1499.

[3] Glover, Fred (February 1990). "Tabu Search—Part II". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4. ISSN 0899-1499.