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