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