ConflictStatistics (Constraint Solver API Documentation -- CPSolver v1.4 build 75)

java.lang.Object
- org.cpsolver.ifs.extension.Extension<V,T>
- - org.cpsolver.ifs.extension.ConflictStatistics<V,T>

Type Parameters:: V - Variable; T - Value

All Implemented Interfaces:: ConstraintListener<V,T>, ModelListener<V,T>

Direct Known Subclasses:: StudentConflictStatistics

public class ConflictStatistics<V extends Variable<V,T>,T extends Value<V,T>>
extends Extension<V,T>
implements ConstraintListener<V,T>

Conflict-based statistics.

The idea behind it is to memorize conflicts and to avoid their potential repetition. When a value v0 is assigned to a variable V0, hard conflicts with previously assigned variables (e.g., V1 = v1, V2 = v2, ... Vm = vm) may occur. These variables V1,...,Vm have to be unassigned before the value v0 is assigned to the variable V0. These unassignments, together with the reason for their unassignment (i.e., the assignment V0 = v0), and a counter tracking how many times such an event occurred in the past, is stored in memory.

Later, if a variable is selected for assignment again, the stored information about repetition of past hard conflicts can be taken into account, e.g., in the value selection heuristics. Assume that the variable V0 is selected for an assignment again (e.g., because it became unassigned as a result of a later assignment), we can weight the number of hard conflicts created in the past for each possible value of this variable. In the above example, the existing assignment V1 = v1 can prohibit the selection of value v0 for variable V0 if there is again a conflict with the assignment V1 = v1.

Conflict-based statistics are a data structure which memorizes the number of hard conflicts that have occurred during the search (e.g., that assignment V0 = v0 resulted c1 times in an unassignment of V1 = v1, c2 times of V2 = v2, . . . and cm times of Vm = vm). More precisely, they form an array


 CBS[Va = va, Vb != vb] = cab,

stating that the assignment Va = va caused the unassignment of Vb = vb a total of cab times in the past. Note that in case of n-ary constraints (where n > 2), this does not imply that the assignments Va = va and Vb = vb cannot be used together. The proposed conflict-based statistics do not actually work with any constraint, they only memorize unassignments and the assignment that caused them. Let us consider a variable Va selected by the VariableSelection.selectVariable(Solution) function and a value va selected by ValueSelection.selectValue(Solution, Variable). Once the assignment Vb = vb is selected by Model.conflictValues(Assignment, Value) to be unassigned, the array cell CBS[Va = va, Vb != vb] is incremented by one.

The data structure is implemented as a hash table, storing information for conflict-based statistics. A counter is maintained for the tuple A = a and B != b. This counter is increased when the value a is assigned to the variable A and b is unassigned from B. The example of this structure


 A = a     →     3 x B != b,   4 x B
 != c,   2 x C != a,   120 x D != a

expresses that variable B lost its assignment b three times and its assignment c four times, variable C lost its assignment a two times, and D lost its assignment a 120 times, all because of later assignments of value a to variable A. This structure is being used in the value selection heuristics to evaluate existing conflicts with the assigned variables. For example, if there is a variable A selected and if the value a is in conflict with the assignment B = b, we know that a similar problem has already occurred 3x in the past, and hence the conflict A = a is weighted with the number 3.

Then, a min-conflict value selection criterion, which selects a value with the minimal number of conflicts with the existing assignments, can be easily adapted to a weighted min-conflict criterion. The value with the smallest sum of the number of conflicts multiplied by their frequencies is selected. Stated in another way, the weighted min-conflict approach helps the value selection heuristics to select a value that might cause more conflicts than another value, but these conflicts occurred less frequently, and therefore they have a lower weighted sum.

The conflict-based statistics has also implemented the following extensions:

If a variable is selected for an assignment, the above presented structure can also tell how many potential conflicts a value can cause in the future. In the above example, we already know that four times a later assignment of A=a caused that value c was unassigned from B. We can try to minimize such future conflicts by selecting a different value of the variable B while A is still unbound.
The memorized conflicts can be aged according to how far they have occurred in the past. For example, a conflict which occurred 1000 iterations ago can have half the weight of a conflict which occurred during the last iteration or it can be forgotten at all.

Furthermore, the presented conflict-based statistics can be used not only inside the solving mechanism. The constructed "implications" together with the information about frequency of their occurrences can be easily accessed by users or by some add-on deductive engine to identify inconsistencies1 and/or hard parts of the input problem. The user can then modify the input requirements in order to eliminate problems found and let the solver continue the search with this modified input problem.

Parameters:

Related Solver Parameters
Parameter	Type	Comment
ConflictStatistics.Ageing	`Double`	Ageing of the conflict-based statistics. Every memorized conflict is aged (multiplited) by this factor for every iteration which passed from the time it was memorized. For instance, if there was a conflict 10 iterations ago, its value is ageing^10 (default is 1.0 -- no ageing).
ConflictStatistics.AgeingHalfTime	`Integer`	Another way how to express ageing: number of iterations to decrease a conflict to 1/2 (default is 0 -- no ageing)

Version:: IFS 1.3 (Iterative Forward Search)
Copyright (C) 2006 - 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.
Author:: Tomáš Müller
See Also:: Solver, Model, ValueSelection, VariableSelection

Constructor Summary

Constructors
Constructor and Description

ConflictStatistics(Solver<V,T> solver, DataProperties properties)

Constructors
Constructor and Description
`ConflictStatistics(Solver<V,T> solver, DataProperties properties)`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`constraintAdded(Constraint<V,T> constraint)` Called when a constraint is added to the model
`void`	`constraintAfterAssigned(Assignment<V,T> assignment, long iteration, Constraint<V,T> constraint, T assigned, Set<T> unassigned)` Increments appropriate counters when there is a value unassigned
`void`	`constraintBeforeAssigned(Assignment<V,T> assignment, long iteration, Constraint<V,T> constraint, T assigned, Set<T> unassigned)` Called by the constraint, before a value is assigned to its variable.
`void`	`constraintRemoved(Constraint<V,T> constraint)` Called when a constraint is removed from the model
`long`	`countAssignments(V variable)` Count the number of past assignments of a variable
`long`	`countPotentialConflicts(Assignment<V,T> assignment, long iteration, T value, int limit)` Counts potential number of unassignments of if the given value is selected.
`double`	`countRemovals(long iteration, Collection<T> conflictValues, T value)` Counts number of unassignments of the given conflicting values caused by the assignment of the given value.
`double`	`countRemovals(long iteration, T conflictValue, T value)` Counts number of unassignments of the given conflicting value caused by the assignment of the given value.
`Map<AssignedValue<T>,List<AssignedValue<T>>>`	`getNoGoods()`
`void`	`register(Model<V,T> model)` Registration of a model.
`void`	`reset()`
`String`	`toString()`
`void`	`unregister(Model<V,T> model)` Unregistration of a model.
`void`	`variableUnassigned(long iteration, T unassignedValue, T assignedValue)`

Methods inherited from class org.cpsolver.ifs.extension.Extension
afterAssigned, afterUnassigned, beforeAssigned, beforeUnassigned, getModel, getProperties, getSolver, init, isRegistered, variableAdded, variableRemoved

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - ConflictStatistics
```
public ConflictStatistics(Solver<V,T> solver,
                          DataProperties properties)
```
- Method Detail
  - register
```
public void register(Model<V,T> model)
```
    Description copied from class: Extension
    
    Registration of a model. This is called by the solver before start.
    
    Overrides:
    
    register in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
    
    Parameters:
    
    model - problem model
  - unregister
```
public void unregister(Model<V,T> model)
```
    Description copied from class: Extension
    
    Unregistration of a model. This is called by the solver when extension is removed.
    
    Overrides:
    
    unregister in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
    
    Parameters:
    
    model - problem model
  - reset
```
public void reset()
```
  - getNoGoods
```
public Map<AssignedValue<T>,List<AssignedValue<T>>> getNoGoods()
```
  - variableUnassigned
```
public void variableUnassigned(long iteration,
                               T unassignedValue,
                               T assignedValue)
```
  - countRemovals
```
public double countRemovals(long iteration,
                            Collection<T> conflictValues,
                            T value)
```
    Counts number of unassignments of the given conflicting values caused by the assignment of the given value.
    
    Parameters:
    
    iteration - current iteration
    
    conflictValues - values conflicting with the given value
    
    value - given value
    
    Returns:
    
    number of unassignments
  - countRemovals
```
public double countRemovals(long iteration,
                            T conflictValue,
                            T value)
```
    Counts number of unassignments of the given conflicting value caused by the assignment of the given value.
    
    Parameters:
    
    iteration - current iteration
    
    conflictValue - value conflicting with the given value
    
    value - given value
    
    Returns:
    
    number of unassignments
  - countPotentialConflicts
```
public long countPotentialConflicts(Assignment<V,T> assignment,
                                    long iteration,
                                    T value,
                                    int limit)
```
    Counts potential number of unassignments of if the given value is selected.
    
    Parameters:
    
    assignment - current assignment
    
    iteration - current iteration
    
    value - given value
    
    limit - conflict limit
    
    Returns:
    
    number of potential unassignments
  - countAssignments
```
public long countAssignments(V variable)
```
    Count the number of past assignments of a variable
    
    Parameters:
    
    variable - given variable
    
    Returns:
    
    total number of past assignments
  - toString
```
public String toString()
```
    Overrides:
    
    toString in class Object
  - constraintBeforeAssigned
```
public void constraintBeforeAssigned(Assignment<V,T> assignment,
                                     long iteration,
                                     Constraint<V,T> constraint,
                                     T assigned,
                                     Set<T> unassigned)
```
    Description copied from interface: ConstraintListener
    
    Called by the constraint, before a value is assigned to its variable.
    
    Specified by:
    
    constraintBeforeAssigned in interface ConstraintListener<V extends Variable<V,T>,T extends Value<V,T>>
    
    Parameters:
    
    assignment - current assignment
    
    iteration - current iteration
    
    constraint - source constraint
    
    assigned - value which will be assigned to its variable ( Value.variable())
    
    unassigned - set of conflicting values which will be unassigned by the constraint before it assigns the given value
  - constraintAfterAssigned
```
public void constraintAfterAssigned(Assignment<V,T> assignment,
                                    long iteration,
                                    Constraint<V,T> constraint,
                                    T assigned,
                                    Set<T> unassigned)
```
    Increments appropriate counters when there is a value unassigned
    
    Specified by:
    
    constraintAfterAssigned in interface ConstraintListener<V extends Variable<V,T>,T extends Value<V,T>>
    
    Parameters:
    
    assignment - current assignment
    
    iteration - current iteration
    
    constraint - source constraint
    
    assigned - value which was assigned to its variable ( Value.variable())
    
    unassigned - set of conflicting values which were unassigned by the constraint before it assigned the given value
  - constraintAdded
```
public void constraintAdded(Constraint<V,T> constraint)
```
    Description copied from class: Extension
    
    Called when a constraint is added to the model
    
    Specified by:
    
    constraintAdded in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
    
    Overrides:
    
    constraintAdded in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
    
    Parameters:
    
    constraint - added constraint
  - constraintRemoved
```
public void constraintRemoved(Constraint<V,T> constraint)
```
    Description copied from class: Extension
    
    Called when a constraint is removed from the model
    
    Specified by:
    
    constraintRemoved in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
    
    Overrides:
    
    constraintRemoved in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
    
    Parameters:
    
    constraint - removed constraint

Class ConflictStatistics<V extends Variable<V,T>,T extends Value<V,T>>

Constructor Summary

Method Summary

Methods inherited from class org.cpsolver.ifs.extension.Extension

Methods inherited from class java.lang.Object

Constructor Detail

ConflictStatistics

Method Detail

register

unregister

reset

getNoGoods

variableUnassigned

countRemovals

countRemovals

countPotentialConflicts

countAssignments

toString

constraintBeforeAssigned

constraintAfterAssigned

constraintAdded

constraintRemoved