Constraint Weighting (CSP)

• Associate a number as the weight of each constraint, measuring the cost of violating this constraint.

• The evaluation function is changed to the weighted version.

• Constraint weighting in Iterative Improvement

  • When a constraint is violated, increase its weight by 1 .

  • The constraints with larger weight should be preferred to be satisfied.

• Constraint weighting in Iterated Local Search

  • At local optima, increase weights of all violated constraints by 1

  • Making a local optimum no longer a local optimum during a period of time.
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    \

Clause Weighting for SAT

• Date back to the Breakout method (1993): increases the weight of each unsatisfied clause by one when reaching local optima.

  • The Breakout method allows unrestricted weight growth during.

• Modern clause weighting usually have a “smoothing” mechanism to decrease clause weights.
  
  
  
  
  \

Clause Weighting for SAT

• discrete Lagrangian method (DLM): DLM follows Breakout’s weight increment scheme, but additionally decrements clause weights by a constant amount after a fixed number of increases;

• scaling and probabilistic smoothing (SAPS): when reaching a local optimum, with a fixed probability p, SAPS performs a random step; with probability 1 − p, the weights of all unsatisfied clauses are multiplied by a factor, and then, with a fixed probability, all clause weights are pulled towards their mean value using the formula $w(c)=\rho w(c)+(1-\rho)\overline w$w(c)=ρw(c)+(1−ρ)w.

• pure additive weighting scheme (PAWS): PAWS updates clause weights in local optima as follows. First, the clause weights of all unsatisfied clauses are increased by one; then, all clause weights are decreased by one after a fixed number of increases.
  
  
  
  
  \

Component Weighting

• Associate a number as the weight of each solution component, measuring the frequency of a solution component being selected.

Vertex Weighting for MaxClique (Pullan 06)

• A GRASP framework: construction + local search

• At the end of each local search phase, increase the penalty values of all vertices in the current clique, by one.

• In the constructive phase, when selecting a vertex to add into the candidate solution, prefer vertices with lower penalty.
  
  
  
  
  \

Scoring Functions

A basic Scoring Function

• Previously, we introduced a scoring function for SAT, which is named ‘score’.

• Under assignment S, score(x) = cost(S)-cost(S‘), where S’ differs from S only in the value of x, cost(S) is the number of unsatisfied clauses under S.

Other Scoring functions

• age(x) = the number of steps since x has changed value

• frequency(x) = a count on how many times x changes its value

• wscore(x) = the weighted version of score, using clause weighting techniques

• Score(x)+age(x)/T, where T is a parameter
  
  
  
  
  \

Scoring Functions

A Scoring Function can be

• a property of the variable, such as score, age, frequency …

• any mathematical expression with one or more properties.

More Scoring functions

• $A^{score(x)}$Ascore(x)

• $score(x)^B$score(x)B
  …

Dynamic Scoring functions

• Change the parameters or the expression of the scoring function during the search

…