Local search (constraint satisfaction)

<h2 id="greedy-algorithms">Greedy algorithms</h2>
<h3>Hill climbing</h3>
<p class="note">Main article: <a href="/facts/Hill_climbing/CMtyufA5">Hill climbing</a></p>
<p>The most basic form of local search is based on choosing the change that maximally decreases the cost of the solution. This method, called <i>hill climbing</i>, 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.
</p><p><a href="/facts/WalkSAT/A6N5C7WQ">GSAT</a> (greedy sat) was the first local search algorithm for satisfiability, and is a form of hill climbing.
</p>
<h3>Constraint weighting or breakout method</h3>
<p>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.
</p><p>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.
</p>
<h3>Tabu search</h3>
<p class="note">Main article: <a href="/facts/Tabu_search/olw8qTSl">Tabu search</a></p>
<p>A drawback of hill climbing with moves that do not decrease cost is that it may cycle over assignments of the same cost. <i>Tabu search</i><a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> overcomes this problem by maintaining a list of "forbidden" assignments, called the <i>tabu list</i>. 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.
</p><p>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.
</p>
<h2 id="random-walk">Random walk</h2>
<p>A <a href="/facts/Random_walk/08v0jmfv">random walk</a> algorithm sometimes moves like a greedy algorithm but sometimes moves randomly. It depends on a parameter 
  
    
      
        p
      
    
    {\displaystyle p}
  
, which is a real number between 0 and 1. At every move, with probability 
  
    
      
        p
      
    
    {\displaystyle p}
  
 the algorithm proceeds like a greedy algorithm, trying to maximally decrease the cost of the assignment. With probability 
  
    
      
        1
        −
        p
      
    
    {\displaystyle 1-p}
  
, however, the solution is changed in some other way, which involves some degree of randomness.
</p>
<h3>WalkSAT</h3>
<p class="note">Main article: <a href="/facts/WalkSAT/A6N5C7WQ">WalkSAT</a></p>
<p>The random move of WalkSAT is changing the value of a random variable of a random violated constraint. For <a href="/facts/Propositional_satisfiability/wBVRjWoy">propositional satisfiability</a> of <a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive normal form</a> 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.
</p>
<h3>Simulated annealing</h3>
<p class="note">Main article: <a href="/facts/Simulated_annealing/JCmHqd3t">Simulated annealing</a></p>
<p>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.
</p><p>In particular, if the improvement of cost 
  
    
      
        d
      
    
    {\displaystyle d}
  
 of a move is negative (the move increases cost), this move is done with probability 
  
    
      
        
          e
          
            −
            d
            ⋅
            T
          
        
      
    
    {\displaystyle e^{-d\cdot T}}
  
, where 
  
    
      
        T
      
    
    {\displaystyle T}
  
 is a real number. Since the probability of doing this move increases with 
  
    
      
        T
      
    
    {\displaystyle T}
  
, this parameter is called the <i>temperature</i>. Simulated annealing decreases this temperature over time, thus allowing more random moves at the beginning and less after time.
</p>
<h2 id="local-search-on-a-cycle-cutset">Local search on a cycle cutset</h2>
<p>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 <i>cycle cutset</i>, which is a set of variables that, if removed from the problem, makes it acyclic.
</p><p>For any assignment of the variables of the cutset, the remaining problem has a <a href="/facts/Forest_(graph_theory)/TCWk4Joy">forest</a> 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.
</p><p>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 
  
    
      
        C
        o
        s
        t
        (
        x
        =
        a
        )
      
    
    {\displaystyle Cost(x=a)}
  
 denotes the cost of the assignment 
  
    
      
        x
        =
        a
      
    
    {\displaystyle x=a}
  
 and 
  
    
      
        
          y
          
            1
          
        
        ,
        …
        ,
        
          y
          
            n
          
        
      
    
    {\displaystyle y_{1},\ldots ,y_{n}}
  
 are the children of 
  
    
      
        x
      
    
    {\displaystyle x}
  
, the following formula holds. In this formula, 
  
    
      
        V
        i
        o
        l
        a
        t
        e
        s
        (
        x
        =
        a
        ,
        
          y
          
            i
          
        
        =
        b
        )
      
    
    {\displaystyle Violates(x=a,y_{i}=b)}
  
 is the 0 or 1 depending on whether the assignment 
  
    
      
        x
        =
        a
        ,
        
          y
          
            i
          
        
        =
        b
      
    
    {\displaystyle x=a,y_{i}=b}
  
 violates the constraint between 
  
    
      
        x
      
    
    {\displaystyle x}
  
 and 
  
    
      
        y
      
    
    {\displaystyle y}
  
.
</p>

C
        o
        s
        t
        (
        x
        =
        a
        )
        =
        
          ∑
          
            i
            =
            1
            ,
            …
            ,
            n
          
        
        
          min
          
            
              y
              
                i
              
            
            =
            b
          
        
        (
        C
        o
        s
        t
        (
        
          y
          
            i
          
        
        =
        b
        )
        +
        V
        i
        o
        l
        a
        t
        e
        s
        (
        x
        =
        a
        ,
        
          y
          
            i
          
        
        =
        b
        )
        )
      
    
    {\displaystyle Cost(x=a)=\sum _{i=1,\ldots ,n}\min _{y_{i}=b}(Cost(y_{i}=b)+Violates(x=a,y_{i}=b))}

<p>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.
</p><p>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.
</p>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm">Forced Satisfiable CSP and SAT Benchmarks of Model RB</a></li></ul>

<ul><li>Dechter, Rina (2003). <a href="https://archive.org/details/constraintproces00rina"><i>Constraint Processing</i></a>. Morgan Kaufmann. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-55860-890-0.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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. <a href="https://linkinghub.elsevier.com/retrieve/pii/0305054886900481" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/0305054886900481</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>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. <a href="http://pubsonline.informs.org/doi/abs/10.1287/ijoc.1.3.190" target="_blank">http://pubsonline.informs.org/doi/abs/10.1287/ijoc.1.3.190</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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. <a href="http://pubsonline.informs.org/doi/abs/10.1287/ijoc.2.1.4" target="_blank">http://pubsonline.informs.org/doi/abs/10.1287/ijoc.2.1.4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Local search (constraint satisfaction) open-in-new

Local search (constraint satisfaction)