001 package net.sf.cpsolver.ifs.model;
002
003 import java.util.*;
004
005 import net.sf.cpsolver.ifs.util.*;
006
007 /**
008 * Generic constraint.
009 * <br><br>
010 * Like in other traditional Constraint Logic Programming (CLP) frameworks, the input problem consists of variables,
011 * values and constraints. Each constraint is defined over a subset of the problem variables and it prohibits some
012 * combinations of values which these variables can simultaneously take. In usual CSP problems, all constraints are
013 * binary (or the problem is transformed into an equivalent problem with only binary constrains before the search is
014 * started) since most of the consistency and filtering techniques are designed only for binary constraints.
015 * In such a case, the procedure computing conflicting variables is rather simple and it returns an unambiguous set of
016 * variables. It enumerates all the constraints which contain the selected variable and which are not consistent with
017 * the selected value. It returns all the variables of such constraints, different from the selected variable.
018 * <br><br>
019 * On the other hand, most of real problems have plenty of multi-variable constraints, like, for instance, resource
020 * constraint in timetabling. Such resource constraint enforces the rule that none of the variables which are using
021 * the given resource can be overlapping in time (if the resource has capacity one) or that the amount of the resource
022 * used at a time does not exceed its capacity. It is not very useful to replace such resource constraint by a set of
023 * binary constraints (e.g., prohibiting two overlapping placements in time of two particular events using the same
024 * resource), since this approach usually ends up with thousands of constraints. Also, there is usually a much more
025 * effective consistency and/or filtering technique working with the original constraint (for instance, "cumulative"
026 * constraint is usually used for modelling resource constraints in CLP).
027 * <br><br>
028 * Using multi-variable constraints, the set of conflicting variables returned by the procedure computing conflicting
029 * variables can differ according to its implementation. For instance, we can have a constraint A+B=C where A and C
030 * 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
031 * unassigned to make the problem {A=3, B=3, C=5} consistent with the constraint A+B=C. Intuitively, there should be
032 * minimal number of variables unassigned in each iteration step (we are trying to increase the number of the
033 * assigned variables during the search). Also, for many constraints, it is possible to find inconsistencies even
034 * when not all variables of the constraint are yet assigned. For instance, if there are two lectures using the
035 * same room at the same time, we know that one of them needs to be unassigned even when there are unassigned lectures
036 * which will also need to be placed in that room.
037 * <br><br>
038 * In the current implementation, each hard constraint needs to implement the procedure
039 * {@link Constraint#computeConflicts(Value, Set)} which returns all the already assigned values that are incompatible we
040 * the selected assignment (value which is to be assigned to its variable). This procedure is called for all constraints
041 * which contain the selected variable in an ordered manner. Furthermore, this order can be changed during the search.
042 * Moreover, the computed set of conflicting variables is passed to this {@link Constraint#computeConflicts(Value, Set)}
043 * procedure as a parameter, so the constraint can "see" what variables are already selected for unassignment by
044 * previously processed constraints. This way, we are not computing the very minimal set of conflicting variables,
045 * however, we allow for computing this set in an efficient way. It can be also tuned for a particular problem by
046 * changing the order of constraints.
047 * <br><br>
048 * Also note that each constraint can keep its notion about the assigned variables. For instance, the resource
049 * constraint of a particular room can memorize a look-up table stating what lecture is assigned in what time slot(s),
050 * so for the computation of the conflicting lectures it only looks through the appropriate fields of this table. The
051 * implementation is based on {@link Constraint#assigned(long,Value)} and {@link Constraint#unassigned(long,Value)}
052 * methods that are responsible to keeping the problem consistent with the constraint. Also note that this default
053 * consistency technique is defined on a problem level and it can be changed by a more dedicated one, implemented for a
054 * particular problem.
055 *
056 * @see Variable
057 * @see Model
058 * @see net.sf.cpsolver.ifs.solver.Solver
059 *
060 * @version
061 * IFS 1.1 (Iterative Forward Search)<br>
062 * Copyright (C) 2006 Tomáš Müller<br>
063 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
064 * Lazenska 391, 76314 Zlin, Czech Republic<br>
065 * <br>
066 * This library is free software; you can redistribute it and/or
067 * modify it under the terms of the GNU Lesser General Public
068 * License as published by the Free Software Foundation; either
069 * version 2.1 of the License, or (at your option) any later version.
070 * <br><br>
071 * This library is distributed in the hope that it will be useful,
072 * but WITHOUT ANY WARRANTY; without even the implied warranty of
073 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
074 * Lesser General Public License for more details.
075 * <br><br>
076 * You should have received a copy of the GNU Lesser General Public
077 * License along with this library; if not, write to the Free Software
078 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
079 */
080
081 public abstract class Constraint {
082 private static IdGenerator iIdGenerator = new IdGenerator();
083
084 protected long iId = -1;
085
086 private Vector iVariables = new FastVector();
087 protected EnumerableCollection iAssignedVariables = new FastVector();
088 private Model iModel = null;
089 protected Vector iConstraintListeners = null;
090
091 /** Constructor */
092 public Constraint() {
093 iId = iIdGenerator.newId();
094 }
095
096 /** The model which the constraint belongs to */
097 public Model getModel() {return iModel; }
098 /** Sets the model which the constraint belongs to */
099 public void setModel(Model model) { iModel=model; }
100 /** The list of variables of this constraint */
101 public Vector variables() { return iVariables; }
102 /** The list of variables of this constraint that are assigned */
103 public EnumerableCollection assignedVariables() { return iAssignedVariables; }
104 /** The number of variables of this constraint */
105 public int countVariables() { return variables().size(); }
106 /** The number of variables of this constraint that are assigned */
107 public int countAssignedVariables() { return assignedVariables().size(); }
108
109 /** Add a variable to this constraint */
110 public void addVariable(Variable variable) {
111 iVariables.addElement(variable);
112 variable.addContstraint(this);
113 if (variable.getAssignment()!=null) {
114 this.assigned(0,variable.getAssignment());
115 if (iAssignedVariables!=null) iAssignedVariables.addElement(variable);
116 }
117 }
118 /** Remove a variable from this constraint */
119 public void removeVariable(Variable variable) {
120 if (variable.getAssignment()!=null) {
121 this.unassigned(0,variable.getAssignment());
122 }
123 variable.removeContstraint(this);
124 iVariables.removeElement(variable);
125 if (iAssignedVariables!=null && iAssignedVariables.contains(variable)) iAssignedVariables.removeElement(variable);
126 }
127
128 /** The only method which has to be implemented by any constraint. It returns the
129 * values which needs to be unassigned in order to make this constraint consistent
130 * with the given value if it is assigned to its variable. The computed list of
131 * conflicting values is added to the given set of conflicts.
132 * @param value value to be assigned to its varaible
133 * @param conflicts resultant set of conflicting values
134 */
135 public abstract void computeConflicts(Value value, Set conflicts);
136
137 /** Returns true if the given assignments are consistent respecting this constraint.
138 * This method is used by MAC (see {@link net.sf.cpsolver.ifs.extension.MacPropagation}). */
139 public boolean isConsistent(Value value1, Value value2) {
140 return true;
141 }
142
143 /** Returns true if the given assignment is inconsistent with the existing assignments
144 * respecting this constraint. This method is used by MAC (see {@link net.sf.cpsolver.ifs.extension.MacPropagation}).
145 */
146 public boolean inConflict(Value value) {
147 Set conflicts = new HashSet();
148 computeConflicts(value, conflicts);
149 return !conflicts.isEmpty();
150 }
151
152 /** Given value is to be assigned to its varable. In this method, the constraint should unassigns
153 * all varaibles which are in conflict with the given assignment because of this constraint.
154 */
155 public void assigned(long iteration, Value value) {
156 HashSet conf = null;
157 if (isHard()) {
158 conf = new HashSet(); computeConflicts(value, conf);
159 }
160 if (iConstraintListeners!=null)
161 for (Enumeration e=iConstraintListeners.elements();e.hasMoreElements();)
162 ((ConstraintListener)e.nextElement()).constraintBeforeAssigned(iteration, this, value, conf);
163 if (conf!=null) {
164 for (Iterator i=conf.iterator(); i.hasNext(); ) {
165 Value conflictValue = (Value)i.next();
166 conflictValue.variable().unassign(iteration);
167 }
168 }
169 if (iAssignedVariables!=null) iAssignedVariables.addElement(value.variable());
170 if (iConstraintListeners!=null)
171 for (Enumeration e=iConstraintListeners.elements();e.hasMoreElements();)
172 ((ConstraintListener)e.nextElement()).constraintAfterAssigned(iteration, this, value, conf);
173 }
174
175 /** Given value is unassigned from its varable.
176 */
177 public void unassigned(long iteration, Value value) {
178 if (iAssignedVariables!=null) iAssignedVariables.removeElement(value.variable());
179 }
180
181 /** Adds a constraint listener */
182 public void addConstraintListener(ConstraintListener listener) {
183 if (iConstraintListeners==null) iConstraintListeners=new FastVector();
184 iConstraintListeners.addElement(listener);
185 }
186 /** Removes a constraint listener */
187 public void removeConstraintListener(ConstraintListener listener) {
188 if (iConstraintListeners==null) iConstraintListeners=new FastVector();
189 iConstraintListeners.removeElement(listener);
190 }
191 /** Returns the list of registered constraint listeners */
192 public Vector constraintListeners() {
193 return iConstraintListeners;
194 }
195
196 /** Unique id */
197 public long getId() { return iId;}
198 /** Constraint's name -- for printing purposes */
199 public String getName() { return String.valueOf(iId); }
200 /** Constraint's description -- for printing purposes */
201 public String getDescription() { return null; }
202 public int hashCode() { return (int)iId; }
203 /** Returns true if the constraint is hard. Only hard constraints are allowed to
204 * unassign a variable when there is a conflict with a value that is being assigned */
205 public boolean isHard() { return true; }
206
207 /** Compare two constraints for equality ({@link Constraint#getId()} is used)*/
208 public boolean equals(Object o) {
209 if (o==null || !(o instanceof Constraint)) return false;
210 return getId()==((Constraint)o).getId();
211 }
212 }