001package org.cpsolver.exam.model; 002 003import java.util.Iterator; 004import java.util.Set; 005 006import org.cpsolver.exam.criteria.DistributionPenalty; 007import org.cpsolver.ifs.assignment.Assignment; 008import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 009import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 010 011 012/** 013 * Distribution binary constraint. <br> 014 * <br> 015 * The following binary distribution constraints are implemented 016 * <ul> 017 * <li>Same room 018 * <li>Different room 019 * <li>Same period 020 * <li>Different period 021 * <li>Precedence 022 * <li>Same day 023 * </ul> 024 * <br> 025 * <br> 026 * 027 * @version ExamTT 1.3 (Examination Timetabling)<br> 028 * Copyright (C) 2008 - 2014 Tomáš Müller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 */ 046public class ExamDistributionConstraint extends ConstraintWithContext<Exam, ExamPlacement, ExamDistributionConstraint.Context> { 047 @Deprecated 048 public static int sDistSameRoom = DistributionType.SameRoom.ordinal() - 1; 049 private DistributionType iType = null; 050 private boolean iHard = true; 051 private int iWeight = 0; 052 053 public static enum DistributionType { 054 /** Same room constraint type */ 055 SameRoom("same-room", "EX_SAME_ROOM", false, new RoomCheck() { 056 @Override 057 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 058 return first.getRoomPlacements().containsAll(second.getRoomPlacements()) || second.getRoomPlacements().containsAll(first.getRoomPlacements()); 059 } 060 @Override 061 public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second) { 062 return first.getRoomPlacements().contains(second); 063 }}), 064 /** Different room constraint type */ 065 DifferentRoom("different-room", "EX_SAME_ROOM", true, new RoomCheck() { 066 @Override 067 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 068 for (Iterator<ExamRoomPlacement> i = first.getRoomPlacements().iterator(); i.hasNext();) 069 if (second.getRoomPlacements().contains(i.next())) 070 return false; 071 return true; 072 } 073 @Override 074 public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second) { 075 return !first.getRoomPlacements().contains(second); 076 }}), 077 /** Same period constraint type */ 078 SamePeriod("same-period", "EX_SAME_PER", false, new PeriodCheck() { 079 @Override 080 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 081 return first.getPeriod().getIndex() == second.getPeriod().getIndex(); 082 } 083 @Override 084 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 085 return first.getIndex() == second.getIndex(); 086 }}), 087 /** Different period constraint type */ 088 DifferentPeriod("different-period", "EX_SAME_PER", true, new PeriodCheck() { 089 @Override 090 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 091 return first.getPeriod().getIndex() != second.getPeriod().getIndex(); 092 } 093 @Override 094 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 095 return first.getIndex() != second.getIndex(); 096 }}), 097 /** Precedence constraint type */ 098 Precedence("precedence", "EX_PRECEDENCE", false, new PeriodCheck() { 099 @Override 100 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 101 return first.getPeriod().getIndex() < second.getPeriod().getIndex(); 102 } 103 @Override 104 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 105 return first.getIndex() < second.getIndex(); 106 }}), 107 /** Precedence constraint type (reverse order) */ 108 PrecedenceRev("precedence-rev", "EX_PRECEDENCE", true, new PeriodCheck() { 109 @Override 110 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 111 return first.getPeriod().getIndex() > second.getPeriod().getIndex(); 112 } 113 @Override 114 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 115 return first.getIndex() > second.getIndex(); 116 }}), 117 /** Same day constraint type */ 118 SameDay("same-day", "EX_SAME_DAY", false, new PeriodCheck() { 119 @Override 120 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 121 return first.getPeriod().getDay() == second.getPeriod().getDay(); 122 } 123 @Override 124 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 125 return first.getDay() == second.getDay(); 126 }}), 127 /** Different day constraint type */ 128 DifferentDay("different-day", "EX_SAME_DAY", true, new PeriodCheck() { 129 @Override 130 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 131 return first.getPeriod().getDay() != second.getPeriod().getDay(); 132 } 133 @Override 134 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 135 return first.getDay() != second.getDay(); 136 }}), 137 ; 138 private String iReference; 139 private String iUniTimeReference; 140 private boolean iUniTimeNegative; 141 private PairCheck iCheck; 142 private DistributionType(String reference, String utReference, boolean utNegative, PairCheck check) { 143 iReference = reference; 144 iUniTimeReference = utReference; 145 iUniTimeNegative = utNegative; 146 iCheck = check; 147 } 148 149 public String getReference() { return iReference; } 150 public boolean isSatisfied(ExamPlacement first, ExamPlacement second) { 151 return iCheck.isSatisfied(first, second); 152 } 153 public boolean isRoomRelated() { return iCheck instanceof RoomCheck; } 154 public boolean isPeriodRelated() { return iCheck instanceof PeriodCheck; } 155 public boolean isSatisfied(ExamPeriod first, ExamPeriod second) { 156 if (iCheck instanceof PeriodCheck) 157 return ((PeriodCheck)iCheck).isSatisfied(first, second); 158 else 159 return true; 160 } 161 public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second) { 162 if (iCheck instanceof RoomCheck) 163 return ((RoomCheck)iCheck).isSatisfied(first, second); 164 else 165 return true; 166 } 167 public String getUniTimeReference() { return iUniTimeReference; } 168 public boolean isUniTimeNegative() { return iUniTimeNegative; } 169 } 170 171 public static interface PairCheck { 172 public boolean isSatisfied(ExamPlacement first, ExamPlacement second); 173 } 174 175 public static interface PeriodCheck extends PairCheck { 176 public boolean isSatisfied(ExamPeriod first, ExamPeriod second); 177 } 178 179 public static interface RoomCheck extends PairCheck { 180 public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second); 181 } 182 183 /** 184 * Constructor 185 * 186 * @param id 187 * constraint unique id 188 * @param type 189 * constraint type 190 * @param hard 191 * true if the constraint is hard (cannot be violated) 192 * @param weight 193 * if not hard, penalty for violation 194 */ 195 public ExamDistributionConstraint(long id, DistributionType type, boolean hard, int weight) { 196 iId = id; 197 iType = type; 198 iHard = hard; 199 iWeight = weight; 200 } 201 202 /** 203 * Constructor 204 * 205 * @param id 206 * constraint unique id 207 * @param type 208 * constraint type 209 * @param hard 210 * true if the constraint is hard (cannot be violated) 211 * @param weight 212 * if not hard, penalty for violation 213 * @deprecated use {@link ExamDistributionConstraint#ExamDistributionConstraint(long, DistributionType, boolean, int)} 214 */ 215 @Deprecated 216 public ExamDistributionConstraint(long id, int type, boolean hard, int weight) { 217 iId = id; 218 iType = DistributionType.values()[type]; 219 iHard = hard; 220 iWeight = weight; 221 } 222 223 /** 224 * Constructor 225 * 226 * @param id 227 * constraint unique id 228 * @param type 229 * constraint type (EX_SAME_PREF, EX_SAME_ROOM, or EX_PRECEDENCE) 230 * @param pref 231 * preference (R/P for required/prohibited, or -2, -1, 0, 1, 2 232 * for preference (from preferred to discouraged)) 233 */ 234 public ExamDistributionConstraint(long id, String type, String pref) { 235 iId = id; 236 boolean neg = "P".equals(pref) || "2".equals(pref) || "1".equals(pref); 237 for (DistributionType t: DistributionType.values()) { 238 if (t.getUniTimeReference().equals(type) && t.isUniTimeNegative() == neg) { 239 iType = t; 240 break; 241 } 242 } 243 if (iType == null) 244 throw new RuntimeException("Unkown type " + type); 245 if ("P".equals(pref) || "R".equals(pref)) 246 iHard = true; 247 else { 248 iHard = false; 249 iWeight = Integer.parseInt(pref) * Integer.parseInt(pref); 250 } 251 } 252 253 /** 254 * Constructor 255 * 256 * @param id 257 * constraint unique id 258 * @param type 259 * constraint type name 260 * @param hard true if the constraint is hard 261 * @param weight constraint penalty if violated (for soft constraint) 262 */ 263 public ExamDistributionConstraint(long id, String type, boolean hard, int weight) { 264 iId = id; 265 for (DistributionType t: DistributionType.values()) { 266 if (t.getReference().equals(type)) { 267 iType = t; break; 268 } 269 } 270 if (iType == null) 271 throw new RuntimeException("Unknown type '" + type + "'."); 272 iHard = hard; 273 iWeight = weight; 274 } 275 276 /** 277 * True if hard (must be satisfied), false for soft (should be satisfied) 278 */ 279 @Override 280 public boolean isHard() { 281 return iHard; 282 } 283 284 /** 285 * If not hard, penalty for violation 286 * @return constraint penalty if violated 287 */ 288 public int getWeight() { 289 return iWeight; 290 } 291 292 /** 293 * Constraint type 294 * @return constraint type 295 */ 296 public int getType() { 297 return iType.ordinal() - 1; 298 } 299 300 public DistributionType getDistributionType() { 301 return iType; 302 } 303 304 /** 305 * Constraint type name 306 * @return constraint type name (one of {@link DistributionType#getReference()}) 307 */ 308 public String getTypeString() { 309 return iType.getReference(); 310 } 311 312 /** 313 * String representation -- constraint type name (exam 1, exam 2) 314 */ 315 @Override 316 public String toString() { 317 return getTypeString() + " (" + variables() + ")"; 318 } 319 320 /** 321 * Compute conflicts -- there is a conflict if the other variable is 322 * assigned and 323 * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is 324 * false 325 */ 326 @Override 327 public void computeConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPlacement givenPlacement, Set<ExamPlacement> conflicts) { 328 boolean before = true; 329 for (Exam exam : variables()) { 330 if (exam.equals(givenPlacement.variable())) { 331 before = false; 332 continue; 333 } 334 ExamPlacement placement = assignment.getValue(exam); 335 if (placement == null) 336 continue; 337 if (!iType.isSatisfied(before ? placement : givenPlacement, before ? givenPlacement : placement)) 338 conflicts.add(placement); 339 } 340 } 341 342 /** 343 * Check for conflict -- there is a conflict if the other variable is 344 * assigned and 345 * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is 346 * false 347 */ 348 @Override 349 public boolean inConflict(Assignment<Exam, ExamPlacement> assignment, ExamPlacement givenPlacement) { 350 boolean before = true; 351 for (Exam exam : variables()) { 352 if (exam.equals(givenPlacement.variable())) { 353 before = false; 354 continue; 355 } 356 ExamPlacement placement = assignment.getValue(exam); 357 if (placement == null) 358 continue; 359 if (!iType.isSatisfied(before ? placement : givenPlacement, before ? givenPlacement : placement)) 360 return true; 361 } 362 return false; 363 } 364 365 /** 366 * Consistency check -- 367 * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is 368 * called 369 */ 370 @Override 371 public boolean isConsistent(ExamPlacement first, ExamPlacement second) { 372 boolean before = (variables().indexOf(first.variable()) < variables().indexOf(second.variable())); 373 return iType.isSatisfied(before ? first : second, before ? second : first); 374 } 375 376 /** 377 * Check assignments of the given exams 378 * 379 * @param first 380 * assignment of the first exam 381 * @param second 382 * assignment of the second exam 383 * @return true, if the constraint is satisfied 384 * @deprecated use {@link DistributionType#isSatisfied(ExamPlacement, ExamPlacement)} 385 */ 386 @Deprecated 387 public boolean check(ExamPlacement first, ExamPlacement second) { 388 return iType.isSatisfied(first, second); 389 } 390 391 /** 392 * Compare with other constraint for equality 393 */ 394 @Override 395 public boolean equals(Object o) { 396 if (o == null || !(o instanceof ExamDistributionConstraint)) 397 return false; 398 ExamDistributionConstraint c = (ExamDistributionConstraint) o; 399 return getType() == c.getType() && getId() == c.getId(); 400 } 401 402 /** 403 * Return true if this is hard constraint or this is a soft constraint 404 * without any violation 405 * @param assignment current assignment 406 * @return true if the constraint is satisfied 407 */ 408 public boolean isSatisfied(Assignment<Exam, ExamPlacement> assignment) { 409 return isSatisfied(assignment, null); 410 } 411 412 /** 413 * Return true if this is hard constraint or this is a soft constraint 414 * without any violation 415 * 416 * @param assignment current assignment 417 * @param p 418 * exam assignment to be made 419 * @return true if the constraint is satisfied 420 */ 421 public boolean isSatisfied(Assignment<Exam, ExamPlacement> assignment, ExamPlacement p) { 422 return countViolations(assignment, p) == 0; 423 } 424 425 /** 426 * Return number of violated pairs for a soft constraint and the given placement 427 * 428 * @param assignment current assignment 429 * @param p 430 * exam assignment to be made 431 * @return number of examination pairs violated 432 */ 433 public int countViolations(Assignment<Exam, ExamPlacement> assignment, ExamPlacement p) { 434 if (isHard()) return 0; 435 if (p == null) return countViolations(assignment); 436 if (countAssignedVariables(assignment) + (assignment.getValue(p.variable()) == null ? 1 : 0) < 2) return 0; // not enough variables 437 438 int nrViolatedPairs = 0; 439 boolean before = true; 440 for (Exam other: variables()) { 441 if (other.equals(p.variable())) { 442 before = false; 443 continue; 444 } 445 ExamPlacement otherPlacement = assignment.getValue(other); 446 if (otherPlacement == null) continue; 447 if (before) { 448 if (!iType.isSatisfied(otherPlacement, p)) nrViolatedPairs ++; 449 } else { 450 if (!iType.isSatisfied(p, otherPlacement)) nrViolatedPairs ++; 451 } 452 } 453 return nrViolatedPairs; 454 } 455 456 /** 457 * Return number of all violated pairs for a soft constraint 458 * 459 * @param assignment current assignment 460 * @return number of examination pairs violated 461 */ 462 public int countViolations(Assignment<Exam, ExamPlacement> assignment) { 463 if (isHard()) return 0; 464 int violations = 0; 465 for (int i = 0; i < variables().size() - 1; i++) { 466 ExamPlacement first = assignment.getValue(variables().get(i)); 467 if (first == null) continue; 468 for (int j = i + 1; j < variables().size(); j++) { 469 ExamPlacement second = assignment.getValue(variables().get(j)); 470 if (second == null) continue; 471 if (!iType.isSatisfied(first, second)) violations ++; 472 } 473 } 474 return violations; 475 } 476 477 /** True if the constraint is related to rooms 478 * @return true if the constraint is related to room placement 479 **/ 480 public boolean isRoomRelated() { 481 return iType.isRoomRelated(); 482 } 483 484 /** True if the constraint is related to periods 485 * @return true if the constraint is related to period placement 486 **/ 487 public boolean isPeriodRelated() { 488 return iType.isPeriodRelated(); 489 } 490 491 @Override 492 public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) { 493 return new Context(assignment); 494 } 495 496 public class Context implements AssignmentConstraintContext<Exam, ExamPlacement> { 497 private int iViolations = 0; 498 499 public Context(Assignment<Exam, ExamPlacement> assignment) { 500 updateCriterion(assignment); 501 } 502 503 @Override 504 public void assigned(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement) { 505 updateCriterion(assignment); 506 } 507 508 @Override 509 public void unassigned(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement) { 510 updateCriterion(assignment); 511 } 512 513 protected void updateCriterion(Assignment<Exam, ExamPlacement> assignment) { 514 if (!isHard()) { 515 ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(assignment, -iViolations * getWeight(), ExamDistributionConstraint.this); 516 iViolations = countViolations(assignment); 517 ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(assignment, +iViolations * getWeight(), ExamDistributionConstraint.this); 518 } 519 } 520 521 public int getViolations() { return iViolations; } 522 } 523}