Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## ifs.extension
Class ConflictStatistics

    java.lang.Object
      ifs.extension.Extension
          ifs.extension.ConflictStatistics

All Implemented Interfaces:
  ConstraintListener, ModelListener, SolutionListener

    public class ConflictStatistics

extends Extension
implements ConstraintListener, SolutionListener

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(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:

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)

Conflict-based statistics also allows printing to HTML files during the search, after each given number of iterations. Example of such file:
Conflict-based statistics allows two modes of printing:

- variable based: tree selected variable → selected value → constraint → conflicting assignment is printed
- constraint based: tree constraint → selected variable → selected value → conflicting assignment is printed

Where constraint is the constraint involved in the unassignment of the conflicting assignmend when selected value is assigned to the selected variable. HTML files are written in the output directory, named stat1.html, stat2.html, ...
Printing parameters:

Parameter | Type | Comment
--- | --- | ---
ConflictStatistics.Print | `Boolean` | If true, conflict-based statistics is being printed to an HTML file during the search.
ConflictStatistics.PrintInterval | `Integer` | Interval (expressed in the number of iterations) for printing CBS
ConflictStatistics.Type | `Integer` | 0 for variable based, 1 from constraint based
ConflictStatistics.MaxLines | `Integer` | Maximal number of lines in the first level of CBS
ConflictStatistics.MaxBranchingLev1 | `Integer` | Maximal number of lines in the second level of CBS
ConflictStatistics.MaxBranchingLev2 | `Integer` | Maximal number of lines in the third level of CBS
ConflictStatistics.ImageBase | `String` | Directory with images collapse.gif, expand.gif and end.gif relative to output directory

Version:
  1.0
Author:
  Tomáš Müller
See Also:
  `Solver`, `Model`, `ValueSelection`, `VariableSelection`

Constructor Summary
`ConflictStatistics(Solver solver, DataProperties properties)`

Method Summary
`void` | `bestCleared(Solution solution)` Called by the solution when method `Solution.clearBest()` is called.
`void` | `bestRestored(Solution solution)` Called by the solution when method `Solution.restoreBest()` is called.
`void` | `bestSaved(Solution solution)` Called by the solution when method `Solution.saveBest()` is called.
`void` | `constraintAdded(Constraint constraint)` Called when a constraint is added to the model
`void` | `constraintAfterAssigned(long iteration, Constraint constraint, Value assigned, Set unassigned)` Increments appropriate counters when there is a value unassigned
`void` | `constraintBeforeAssigned(long iteration, Constraint constraint, Value assigned, Set unassigned)` Called by the constraint, before a value is assigned to its variable.
`void` | `constraintRemoved(Constraint constraint)` Called when a constraint is removed from the model
`long` | `countPotentialConflicts(long iteration, Value value, int limit)` Counts potential number of unassignments of if the given value is selected.
`double` | `countRemovals(long iteration, Collection conflictValues, Value value)` Counts number of unassignments of the given conflicting values caused by the assignment of the given value.
`double` | `countRemovals(long iteration, Value conflictValue, Value value)` Counts number of unassignments of the given conflicting value caused by the assignment of the given value.
`void` | `getInfo(Hashtable info)` Put some information from the extension to the solution info table
`void` | `getInfo(Solution solution, Dictionary info)` Called by the solution when it is asked to produce info table, see `Solution.getInfo()`.
`void` | `print(PrintWriter out, long iteration)` Print conflict-based statistics
`void` | `printHtml(long iteration, PrintWriter out, boolean printHeader, long maxVariables, long unassignmentLimit, long assignmentLimit, String imgBase, int type)` Print conflict-based statistics in HTML format
`void` | `printHtml(long iteration, PrintWriter out, DataProperties params)` Print conflict-based statistics in HTML format
`void` | `printHtml(long iteration, PrintWriter out, long maxVariables, long unassignmentLimit, long assignmentLimit, int type)` Print conflict-based statistics in HTML format
`void` | `register(Model model)` Registration of a model.
`void` | `solutionUpdated(Solution solution)` Called by the solution when it is updated, see `Solution.update(double)`.
`String` | `toString()`
`void` | `unregister(Model model)` Unregistration of a model.

Methods inherited from class ifs.extension.Extension
`afterAssigned, afterUnassigned, beforeAssigned, beforeUnassigned, getModel, getProperties, getSolver, init, isRegistered, useValueExtra, useVariableExtra, 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 solver,
                              DataProperties properties)

Method Detail

### register

    public void register(Model model)

  Description copied from class: `Extension`
  Registration of a model. This is called by the solver before start.

  Overrides:
    `register` in class `Extension`

### unregister

    public void unregister(Model 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`

### countRemovals

    public double countRemovals(long iteration,
                                Collection conflictValues,
                                Value value)

  Counts number of unassignments of the given conflicting values caused by the assignment of the given value.

### countRemovals

    public double countRemovals(long iteration,
                                Value conflictValue,
                                Value value)

  Counts number of unassignments of the given conflicting value caused by the assignment of the given value.

### countPotentialConflicts

    public long countPotentialConflicts(long iteration,
                                        Value value,
                                        int limit)

  Counts potential number of unassignments of if the given value is selected.

### printHtml

    public void printHtml(long iteration,
                          PrintWriter out,
                          long maxVariables,
                          long unassignmentLimit,
                          long assignmentLimit,
                          int type)

  Print conflict-based statistics in HTML format

### printHtml

    public void printHtml(long iteration,
                          PrintWriter out,
                          DataProperties params)

  Print conflict-based statistics in HTML format

### printHtml

    public void printHtml(long iteration,
                          PrintWriter out,
                          boolean printHeader,
                          long maxVariables,
                          long unassignmentLimit,
                          long assignmentLimit,
                          String imgBase,
                          int type)

  Print conflict-based statistics in HTML format

### print

    public void print(PrintWriter out,
                      long iteration)

  Print conflict-based statistics

### toString

    public String toString()

  Overrides:
    `toString` in class `Object`

### getInfo

    public void getInfo(Hashtable info)

  Description copied from class: `Extension`
  Put some information from the extension to the solution info table

  Specified by:
    `getInfo` in interface `ModelListener`
  Overrides:
    `getInfo` in class `Extension`
  Parameters:
    `info` - resultant table with informations (key, value).

### constraintBeforeAssigned

    public void constraintBeforeAssigned(long iteration,
                                         Constraint constraint,
                                         Value assigned,
                                         Set unassigned)

  Description copied from interface: `ConstraintListener`
  Called by the constraint, before a value is assigned to its variable.

  Specified by:
    `constraintBeforeAssigned` in interface `ConstraintListener`
  Parameters:
    `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(long iteration,
                                        Constraint constraint,
                                        Value assigned,
                                        Set unassigned)

  Increments appropriate counters when there is a value unassigned

  Specified by:
    `constraintAfterAssigned` in interface `ConstraintListener`
  Parameters:
    `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 constraint)

  Description copied from class: `Extension`
  Called when a constraint is added to the model

  Specified by:
    `constraintAdded` in interface `ModelListener`
  Overrides:
    `constraintAdded` in class `Extension`
  Parameters:
    `constraint` - added constraint

### constraintRemoved

    public void constraintRemoved(Constraint constraint)

  Description copied from class: `Extension`
  Called when a constraint is removed from the model

  Specified by:
    `constraintRemoved` in interface `ModelListener`
  Overrides:
    `constraintRemoved` in class `Extension`
  Parameters:
    `constraint` - removed constraint

### solutionUpdated

    public void solutionUpdated(Solution solution)

  Description copied from interface: `SolutionListener`
  Called by the solution when it is updated, see `Solution.update(double)`.

  Specified by:
    `solutionUpdated` in interface `SolutionListener`
  Parameters:
    `solution` - source solution

### getInfo

    public void getInfo(Solution solution,
                        Dictionary info)

  Description copied from interface: `SolutionListener`
  Called by the solution when it is asked to produce info table, see `Solution.getInfo()`. A listener can also add some its info into this table.

  Specified by:
    `getInfo` in interface `SolutionListener`
  Parameters:
    `solution` - source solution
    `info` - produced info table

### bestCleared

    public void bestCleared(Solution solution)

  Description copied from interface: `SolutionListener`
  Called by the solution when method `Solution.clearBest()` is called.

  Specified by:
    `bestCleared` in interface `SolutionListener`
  Parameters:
    `solution` - source solution

### bestSaved

    public void bestSaved(Solution solution)

  Description copied from interface: `SolutionListener`
  Called by the solution when method `Solution.saveBest()` is called.

  Specified by:
    `bestSaved` in interface `SolutionListener`
  Parameters:
    `solution` - source solution

### bestRestored

    public void bestRestored(Solution solution)

  Description copied from interface: `SolutionListener`
  Called by the solution when method `Solution.restoreBest()` is called.

  Specified by:
    `bestRestored` in interface `SolutionListener`
  Parameters:
    `solution` - source solution

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2005 Tomáš Müller