|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object net.sf.cpsolver.ifs.extension.Extension net.sf.cpsolver.ifs.extension.ConflictStatistics
public class ConflictStatistics
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 solver,
DataProperties properties)
|
Method Summary | |
---|---|
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(Dictionary info)
Adds some information into the table with information about the solution |
void |
getInfo(Dictionary info,
Vector variables)
Adds some information into the table with information about the solution, only consider variables from the given set |
Hashtable |
getNoGoods()
|
void |
register(Model model)
Registration of a model. |
void |
reset()
|
String |
toString()
|
void |
unregister(Model model)
Unregistration of a model. |
void |
variableUnassigned(long iteration,
Value unassignedValue,
Value 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 solver, DataProperties properties)
Method Detail |
---|
public void register(Model model)
Extension
register
in class Extension
public void unregister(Model model)
Extension
unregister
in class Extension
public void reset()
public Hashtable getNoGoods()
public void variableUnassigned(long iteration, Value unassignedValue, Value assignedValue)
public double countRemovals(long iteration, Collection conflictValues, Value value)
public double countRemovals(long iteration, Value conflictValue, Value value)
public long countPotentialConflicts(long iteration, Value value, int limit)
public String toString()
toString
in class Object
public void getInfo(Dictionary info)
InfoProvider
getInfo
in interface InfoProvider
public void getInfo(Dictionary info, Vector variables)
InfoProvider
getInfo
in interface InfoProvider
public void constraintBeforeAssigned(long iteration, Constraint constraint, Value assigned, Set unassigned)
ConstraintListener
constraintBeforeAssigned
in interface ConstraintListener
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 constraint, Value assigned, Set unassigned)
constraintAfterAssigned
in interface ConstraintListener
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 constraint)
Extension
constraintAdded
in interface ModelListener
constraintAdded
in class Extension
constraint
- added constraintpublic void constraintRemoved(Constraint constraint)
Extension
constraintRemoved
in interface ModelListener
constraintRemoved
in class Extension
constraint
- removed constraint
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |