`min_conflicts`

to
`local_search`

by simply replacing the `guess`

predicate by the
predicate `move`

:
local_search(Vars) :- conflict_constraints(cs,List), ( List = [] -> set_to_tent(Vars) ; List = [Constraint|_] -> term_variables(Constraint,[Var|_]), move(Var), local_search(Vars) ). move(Var) :- Var tent_get Value, NewValue is (1-Value), Var tent_set NewValue. |

`local_search`

with the predicate
`hill_climb`

:
hill_climb(Vars) :- conflict_constraints(cs,List), length(List,Count), ( Count = 0 -> set_to_tent(Vars) ; try_move(List,NewCount), NewCount < Count -> hill_climb(Vars) ; write('local optimum: '), writeln(Count) ). try_move(List,NewCount) :- select_var(List,Var), move(Var), conflict_constraints(cs,NewList), length(NewList,NewCount). select_var(List,Var) :- member(Constraint,List), term_variables(Constraint,Vars), member(Var,Vars). |

- Constraint satisfaction is recognised by finding that the conflict constraint set is empty.
- The move operation and the acceptance test are within the condition part of the if-then-else construct. As a consequence, if the acceptance test fails (the move does not improve the objective) the move is automatically undone by backtracking.

`try_move`

is very inefficient, because it
repeatedly goes through the whole list of conflict constraints to
count the number of constraints in conflict.
The facility to propagate tentative values supports more efficient
maintenance of the number constraints in conflict.
This technique is known as maintenance of `BSum`

records for any tentative
assignment of the propositional variables, the number of satisfied
clauses.
This speeds up hill climbing because, after each move, its effect on
the number of satisfied clauses is automatically computed by the
propagation of tentative values.
prop_sat_2(Vars) :- Vars = [X1,X2,X3], tent_init(Vars), clause_cons(X1 or neg X2 or X3,B1), clause_cons(neg X1 or neg X2,B2), clause_cons(X2 or neg X3,B3), BSum tent_is B1+B2+B3, hill_climb_2(Vars,BSum). clause_cons(Clause,B) :- Clause $= 1 r_conflict cs, B tent_is Clause. hill_climb_2(Vars,BSum) :- conflict_constraints(cs,List), BSum tent_get Satisfied, ( List=[] -> set_to_tent(Vars) ; select_var(List,Var), move(Var), tent_get(BSum) > Satisfied -> hill_climb_2(Vars,BSum) ; write('local optimum: '), writeln(Count) ). |

`BSum`

before and after the move is done.
Remember that, since the move operator changes the tentative values of
some variable, the `tent_is`

primitive will automatically
update the `BSum`

variable.
This code can be made more efficent by recording more
invariants, as described in [28].

Local search can be implemented in ECL ^{i}PS^{e}with therepairlibrary. Invariants can be implemented by tentative value propagation usingtent_is/2.

Figure 13.4: Local Search and Invariants