|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.sf.cpsolver.ifs.model.Constraint<V,T>
public abstract class Constraint<V extends Variable<V,T>,T extends Value<V,T>>
Generic constraint.
Like in other traditional Constraint Logic Programming (CLP) frameworks, the
input problem consists of variables, values and constraints. Each constraint
is defined over a subset of the problem variables and it prohibits some
combinations of values which these variables can simultaneously take. In
usual CSP problems, all constraints are binary (or the problem is transformed
into an equivalent problem with only binary constrains before the search is
started) since most of the consistency and filtering techniques are designed
only for binary constraints. In such a case, the procedure computing
conflicting variables is rather simple and it returns an unambiguous set of
variables. It enumerates all the constraints which contain the selected
variable and which are not consistent with the selected value. It returns all
the variables of such constraints, different from the selected variable.
On the other hand, most of real problems have plenty of multi-variable
constraints, like, for instance, resource constraint in timetabling. Such
resource constraint enforces the rule that none of the variables which are
using the given resource can be overlapping in time (if the resource has
capacity one) or that the amount of the resource used at a time does not
exceed its capacity. It is not very useful to replace such resource
constraint by a set of binary constraints (e.g., prohibiting two overlapping
placements in time of two particular events using the same resource), since
this approach usually ends up with thousands of constraints. Also, there is
usually a much more effective consistency and/or filtering technique working
with the original constraint (for instance, "cumulative" constraint is
usually used for modelling resource constraints in CLP).
Using multi-variable constraints, the set of conflicting variables returned
by the procedure computing conflicting variables can differ according to its
implementation. For instance, we can have a constraint A+B=C where A and C is
already assigned to A=3 and C=5. Then if the assignment B=3 is selected,
either A or B or both A and B can be unassigned to make the problem {A=3,
B=3, C=5} consistent with the constraint A+B=C. Intuitively, there should be
minimal number of variables unassigned in each iteration step (we are trying
to increase the number of the assigned variables during the search). Also,
for many constraints, it is possible to find inconsistencies even when not
all variables of the constraint are yet assigned. For instance, if there are
two lectures using the same room at the same time, we know that one of them
needs to be unassigned even when there are unassigned lectures which will
also need to be placed in that room.
In the current implementation, each hard constraint needs to implement the
procedure computeConflicts(Value, Set)
which returns all
the already assigned values that are incompatible we the selected assignment
(value which is to be assigned to its variable). This procedure is called for
all constraints which contain the selected variable in an ordered manner.
Furthermore, this order can be changed during the search. Moreover, the
computed set of conflicting variables is passed to this
computeConflicts(Value, Set)
procedure as a parameter, so
the constraint can "see" what variables are already selected for unassignment
by previously processed constraints. This way, we are not computing the very
minimal set of conflicting variables, however, we allow for computing this
set in an efficient way. It can be also tuned for a particular problem by
changing the order of constraints.
Also note that each constraint can keep its notion about the assigned
variables. For instance, the resource constraint of a particular room can
memorize a look-up table stating what lecture is assigned in what time
slot(s), so for the computation of the conflicting lectures it only looks
through the appropriate fields of this table. The implementation is based on
assigned(long,Value)
and
unassigned(long,Value)
methods that are responsible to
keeping the problem consistent with the constraint. Also note that this
default consistency technique is defined on a problem level and it can be
changed by a more dedicated one, implemented for a particular problem.
Variable
,
Model
,
Solver
Field Summary | |
---|---|
protected Collection<V> |
iAssignedVariables
|
protected List<ConstraintListener<T>> |
iConstraintListeners
|
protected long |
iId
|
Constructor Summary | |
---|---|
Constraint()
Constructor |
Method Summary | |
---|---|
void |
addConstraintListener(ConstraintListener<T> listener)
Adds a constraint listener |
void |
addVariable(V variable)
Add a variable to this constraint |
void |
assigned(long iteration,
T value)
Given value is to be assigned to its varable. |
Collection<V> |
assignedVariables()
The list of variables of this constraint that are assigned |
int |
compareTo(Constraint<V,T> c)
|
abstract void |
computeConflicts(T value,
Set<T> conflicts)
The only method which has to be implemented by any constraint. |
List<ConstraintListener<T>> |
constraintListeners()
Returns the list of registered constraint listeners |
int |
countAssignedVariables()
The number of variables of this constraint that are assigned |
int |
countVariables()
The number of variables of this constraint |
boolean |
equals(Object o)
Compare two constraints for equality ( getId() is used) |
String |
getDescription()
Constraint's description -- for printing purposes |
long |
getId()
Unique id |
Model<V,T> |
getModel()
The model which the constraint belongs to |
String |
getName()
Constraint's name -- for printing purposes |
int |
hashCode()
|
boolean |
inConflict(T value)
Returns true if the given assignment is inconsistent with the existing assignments respecting this constraint. |
boolean |
isConsistent(T value1,
T value2)
Returns true if the given assignments are consistent respecting this constraint. |
boolean |
isHard()
Returns true if the constraint is hard. |
void |
removeConstraintListener(ConstraintListener<T> listener)
Removes a constraint listener |
void |
removeVariable(V variable)
Remove a variable from this constraint |
void |
setModel(Model<V,T> model)
Sets the model which the constraint belongs to |
void |
unassigned(long iteration,
T value)
Given value is unassigned from its variable. |
List<V> |
variables()
The list of variables of this constraint |
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected long iId
protected Collection<V extends Variable<V,T>> iAssignedVariables
protected List<ConstraintListener<T extends Value<V,T>>> iConstraintListeners
Constructor Detail |
---|
public Constraint()
Method Detail |
---|
public Model<V,T> getModel()
public void setModel(Model<V,T> model)
public List<V> variables()
public Collection<V> assignedVariables()
public int countVariables()
public int countAssignedVariables()
public void addVariable(V variable)
public void removeVariable(V variable)
public abstract void computeConflicts(T value, Set<T> conflicts)
value
- value to be assigned to its varaibleconflicts
- resultant set of conflicting valuespublic boolean isConsistent(T value1, T value2)
MacPropagation
).
public boolean inConflict(T value)
MacPropagation
).
public void assigned(long iteration, T value)
public void unassigned(long iteration, T value)
public void addConstraintListener(ConstraintListener<T> listener)
public void removeConstraintListener(ConstraintListener<T> listener)
public List<ConstraintListener<T>> constraintListeners()
public long getId()
public String getName()
public String getDescription()
public int hashCode()
hashCode
in class Object
public boolean isHard()
public boolean equals(Object o)
getId()
is used)
equals
in class Object
public int compareTo(Constraint<V,T> c)
compareTo
in interface Comparable<Constraint<V extends Variable<V,T>,T extends Value<V,T>>>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |