|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.sf.cpsolver.ifs.extension.Extension<V,T>
net.sf.cpsolver.ifs.extension.ConflictStatistics<V,T>
public class ConflictStatistics<V extends Variable<V,T>,T extends Value<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
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. 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) |
Solver
,
Model
,
ValueSelection
,
VariableSelection
Constructor Summary | |
---|---|
ConflictStatistics(Solver<V,T> solver,
DataProperties properties)
|
Method Summary | |
---|---|
void |
constraintAdded(Constraint<V,T> constraint)
Called when a constraint is added to the model |
void |
constraintAfterAssigned(long iteration,
Constraint<?,T> constraint,
T assigned,
Set<T> unassigned)
Increments appropriate counters when there is a value unassigned |
void |
constraintBeforeAssigned(long iteration,
Constraint<?,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 |
countPotentialConflicts(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<Assignment<T>,List<Assignment<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 net.sf.cpsolver.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 |
---|
public ConflictStatistics(Solver<V,T> solver, DataProperties properties)
Method Detail |
---|
public void register(Model<V,T> model)
Extension
register
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
public void unregister(Model<V,T> model)
Extension
unregister
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
public void reset()
public Map<Assignment<T>,List<Assignment<T>>> getNoGoods()
public void variableUnassigned(long iteration, T unassignedValue, T assignedValue)
public double countRemovals(long iteration, Collection<T> conflictValues, T value)
public double countRemovals(long iteration, T conflictValue, T value)
public long countPotentialConflicts(long iteration, T value, int limit)
public String toString()
toString
in class Object
public void constraintBeforeAssigned(long iteration, Constraint<?,T> constraint, T assigned, Set<T> unassigned)
ConstraintListener
constraintBeforeAssigned
in interface ConstraintListener<T extends Value<V,T>>
iteration
- current iterationconstraint
- source constraintassigned
- 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 valuepublic void constraintAfterAssigned(long iteration, Constraint<?,T> constraint, T assigned, Set<T> unassigned)
constraintAfterAssigned
in interface ConstraintListener<T extends Value<V,T>>
iteration
- current iterationconstraint
- source constraintassigned
- 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 valuepublic void constraintAdded(Constraint<V,T> constraint)
Extension
constraintAdded
in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
constraintAdded
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
constraint
- added constraintpublic void constraintRemoved(Constraint<V,T> constraint)
Extension
constraintRemoved
in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
constraintRemoved
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
constraint
- removed constraint
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |