net.sf.cpsolver.ifs.model.Constraint
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object
public abstract class Constraint
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 EnumerableCollection |
iAssignedVariables
|
protected Vector |
iConstraintListeners
|
protected long |
iId
|
| Constructor Summary | |
|---|---|
Constraint()
Constructor |
|
| Method Summary | |
|---|---|
void |
addConstraintListener(ConstraintListener listener)
Adds a constraint listener |
void |
addVariable(Variable variable)
Add a variable to this constraint |
void |
assigned(long iteration,
Value value)
Given value is to be assigned to its varable. |
EnumerableCollection |
assignedVariables()
The list of variables of this constraint that are assigned |
abstract void |
computeConflicts(Value value,
Set conflicts)
The only method which has to be implemented by any constraint. |
Vector |
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 |
getModel()
The model which the constraint belongs to |
String |
getName()
Constraint's name -- for printing purposes |
int |
hashCode()
|
boolean |
inConflict(Value value)
Returns true if the given assignment is inconsistent with the existing assignments respecting this constraint. |
boolean |
isConsistent(Value value1,
Value value2)
Returns true if the given assignments are consistent respecting this constraint. |
boolean |
isHard()
Returns true if the constraint is hard. |
void |
removeConstraintListener(ConstraintListener listener)
Removes a constraint listener |
void |
removeVariable(Variable variable)
Remove a variable from this constraint |
void |
setModel(Model model)
Sets the model which the constraint belongs to |
void |
unassigned(long iteration,
Value value)
Given value is unassigned from its varable. |
Vector |
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 EnumerableCollection iAssignedVariables
protected Vector iConstraintListeners
| Constructor Detail |
|---|
public Constraint()
| Method Detail |
|---|
public Model getModel()
public void setModel(Model model)
public Vector variables()
public EnumerableCollection assignedVariables()
public int countVariables()
public int countAssignedVariables()
public void addVariable(Variable variable)
public void removeVariable(Variable variable)
public abstract void computeConflicts(Value value,
Set conflicts)
value - value to be assigned to its varaibleconflicts - resultant set of conflicting values
public boolean isConsistent(Value value1,
Value value2)
MacPropagation).
public boolean inConflict(Value value)
MacPropagation).
public void assigned(long iteration,
Value value)
public void unassigned(long iteration,
Value value)
public void addConstraintListener(ConstraintListener listener)
public void removeConstraintListener(ConstraintListener listener)
public Vector constraintListeners()
public long getId()
public String getName()
public String getDescription()
public int hashCode()
hashCode in class Objectpublic boolean isHard()
public boolean equals(Object o)
getId() is used)
equals in class Object
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||