001 package net.sf.cpsolver.coursett.constraint; 002 003 import java.util.ArrayList; 004 import java.util.HashSet; 005 import java.util.HashMap; 006 import java.util.Iterator; 007 import java.util.List; 008 import java.util.Set; 009 010 import net.sf.cpsolver.coursett.Constants; 011 import net.sf.cpsolver.coursett.criteria.DistributionPreferences; 012 import net.sf.cpsolver.coursett.model.Lecture; 013 import net.sf.cpsolver.coursett.model.Placement; 014 import net.sf.cpsolver.coursett.model.TimeLocation; 015 import net.sf.cpsolver.coursett.model.TimetableModel; 016 import net.sf.cpsolver.ifs.model.Constraint; 017 import net.sf.cpsolver.ifs.model.GlobalConstraint; 018 import net.sf.cpsolver.ifs.model.Model; 019 import net.sf.cpsolver.ifs.model.WeakeningConstraint; 020 import net.sf.cpsolver.ifs.util.DataProperties; 021 import net.sf.cpsolver.ifs.util.DistanceMetric; 022 import net.sf.cpsolver.ifs.util.ToolBox; 023 024 /** 025 * Group constraint. <br> 026 * This constraint expresses relations between several classes, e.g., that two 027 * sections of the same lecture can not be taught at the same time, or that some 028 * classes have to be taught one immediately after another. It can be either 029 * hard or soft. <br> 030 * <br> 031 * Following constraints are now supported: 032 * <table border='1'> 033 * <tr> 034 * <th>Constraint</th> 035 * <th>Comment</th> 036 * </tr> 037 * <tr> 038 * <td>SAME_TIME</td> 039 * <td>Same time: given classes have to be taught in the same hours. If the 040 * classes are of different length, the smaller one cannot start before the 041 * longer one and it cannot end after the longer one.</td> 042 * </tr> 043 * <tr> 044 * <td>SAME_DAYS</td> 045 * <td>Same days: given classes have to be taught in the same day. If the 046 * classes are of different time patterns, the days of one class have to form a 047 * subset of the days of the other class.</td> 048 * </tr> 049 * <tr> 050 * <td>BTB</td> 051 * <td>Back-to-back constraint: given classes have to be taught in the same room 052 * and they have to follow one strictly after another.</td> 053 * </tr> 054 * <tr> 055 * <td>BTB_TIME</td> 056 * <td>Back-to-back constraint: given classes have to follow one strictly after 057 * another, but they can be taught in different rooms.</td> 058 * </tr> 059 * <tr> 060 * <td>DIFF_TIME</td> 061 * <td>Different time: given classes cannot overlap in time.</td> 062 * </tr> 063 * <tr> 064 * <td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td> 065 * <td>Number of hours between: between the given classes, the exact number of 066 * hours have to be kept.</td> 067 * </tr> 068 * <tr> 069 * <td>SAME_START</td> 070 * <td>Same starting hour: given classes have to start in the same hour.</td> 071 * </tr> 072 * <tr> 073 * <td>SAME_ROOM</td> 074 * <td>Same room: given classes have to be placed in the same room.</td> 075 * </tr> 076 * <tr> 077 * <td>NHB_GTE(1)</td> 078 * <td>Greater than or equal to 1 hour between: between the given classes, the 079 * number of hours have to be one or more.</td> 080 * </tr> 081 * <tr> 082 * <td>NHB_LT(6)</td> 083 * <td>Less than 6 hours between: between the given classes, the number of hours 084 * have to be less than six.</td> 085 * </tr> 086 * </table> 087 * 088 * @version CourseTT 1.2 (University Course Timetabling)<br> 089 * Copyright (C) 2006 - 2010 Tomas Muller<br> 090 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 091 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 092 * <br> 093 * This library is free software; you can redistribute it and/or modify 094 * it under the terms of the GNU Lesser General Public License as 095 * published by the Free Software Foundation; either version 3 of the 096 * License, or (at your option) any later version. <br> 097 * <br> 098 * This library is distributed in the hope that it will be useful, but 099 * WITHOUT ANY WARRANTY; without even the implied warranty of 100 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 101 * Lesser General Public License for more details. <br> 102 * <br> 103 * You should have received a copy of the GNU Lesser General Public 104 * License along with this library; if not see 105 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 106 */ 107 108 public class GroupConstraint extends Constraint<Lecture, Placement> { 109 private Long iConstraintId; 110 private int iPreference; 111 private ConstraintType iType; 112 private boolean iIsRequired; 113 private boolean iIsProhibited; 114 private int iLastPreference = 0; 115 private int iDayOfWeekOffset = 0; 116 private boolean iPrecedenceConsiderDatePatterns = true; 117 118 /** 119 * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), 120 * only need to implement this interface. 121 */ 122 public static interface PairCheck { 123 /** 124 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 125 * @param gc Calling group constraint 126 * @param plc1 First placement 127 * @param plc2 Second placement 128 * @return true if constraint is satisfied 129 */ 130 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2); 131 /** 132 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 133 * @param gc Calling group constraint 134 * @param plc1 First placement 135 * @param plc2 Second placement 136 * @return true if constraint is satisfied 137 */ 138 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2); 139 } 140 141 /** 142 * Group constraint building blocks (individual constraints that need more than {@link PairCheck}) 143 */ 144 public static enum Flag { 145 /** Back-to-back constraint (sequence check) */ 146 BACK_TO_BACK, 147 /** Can share room flag */ 148 CAN_SHARE_ROOM, 149 /** Maximum hours a day (number of slots a day check) */ 150 MAX_HRS_DAY, 151 /** Children cannot overlap */ 152 CH_NOTOVERLAP; 153 /** Bit number (to combine flags) */ 154 int flag() { return 1 << ordinal(); } 155 } 156 157 /** 158 * Group constraint type. 159 */ 160 public static enum ConstraintType { 161 /** 162 * Same Time: Given classes must be taught at the same time of day (independent of the actual day the classes meet). 163 * For the classes of the same length, this is the same constraint as same start. For classes of different length, 164 * the shorter one cannot start before, nor end after, the longer one.<BR> 165 * When prohibited or (strongly) discouraged: one class may not meet on any day at a time of day that overlaps with 166 * that of the other. For example, one class can not meet M 7:30 while the other meets F 7:30. Note the difference 167 * here from the different time constraint that only prohibits the actual class meetings from overlapping. 168 */ 169 SAME_TIME("SAME_TIME", "Same Time", new PairCheck() { 170 @Override 171 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 172 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 173 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()); 174 } 175 @Override 176 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 177 return !(plc1.getTimeLocation().shareHours(plc2.getTimeLocation())); 178 }}), 179 /** 180 * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class 181 * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one 182 * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday. 183 * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR> 184 * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot 185 * overlap in days). For instance, if one class is MFW, the second has to be TTh. 186 */ 187 SAME_DAYS("SAME_DAYS", "Same Days", new PairCheck() { 188 @Override 189 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 190 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 191 } 192 @Override 193 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 194 return !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 195 }}), 196 /** 197 * Back-To-Back & Same Room: Classes must be offered in adjacent time segments and must be placed in the same room. 198 * Given classes must also be taught on the same days.<BR> 199 * When prohibited or (strongly) discouraged: classes cannot be back-to-back. There must be at least half-hour 200 * between these classes, and they must be taught on the same days and in the same room. 201 */ 202 BTB("BTB", "Back-To-Back & Same Room", new PairCheck() { 203 @Override 204 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 205 return 206 plc1.sameRooms(plc2) && 207 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 208 } 209 @Override 210 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 211 return 212 plc1.sameRooms(plc2) && 213 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 214 }}, Flag.BACK_TO_BACK), 215 /** 216 * Back-To-Back: Classes must be offered in adjacent time segments but may be placed in different rooms. Given classes 217 * must also be taught on the same days.<BR> 218 * When prohibited or (strongly) discouraged: no pair of classes can be taught back-to-back. They may not overlap in time, 219 * but must be taught on the same days. This means that there must be at least half-hour between these classes. 220 */ 221 BTB_TIME("BTB_TIME", "Back-To-Back", new PairCheck() { 222 @Override 223 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 224 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 225 } 226 @Override 227 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 228 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 229 }}, Flag.BACK_TO_BACK), 230 /** 231 * Different Time: Given classes cannot overlap in time. They may be taught at the same time of day if they are on 232 * different days. For instance, MF 7:30 is compatible with TTh 7:30.<BR> 233 * When prohibited or (strongly) discouraged: every pair of classes in the constraint must overlap in time. 234 */ 235 DIFF_TIME("DIFF_TIME", "Different Time", new PairCheck() { 236 @Override 237 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 238 return !plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 239 } 240 @Override 241 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 242 return plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 243 }}), 244 /** 245 * 1 Hour Between: Given classes must have exactly 1 hour in between the end of one and the beginning of another. 246 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 247 * When prohibited or (strongly) discouraged: classes can not have 1 hour in between. They may not overlap in time 248 * but must be taught on the same days. 249 */ 250 NHB_1("NHB(1)", "1 Hour Between", 10, 12, BTB_TIME.check(), Flag.BACK_TO_BACK), 251 /** 252 * 2 Hours Between: Given classes must have exactly 2 hours in between the end of one and the beginning of another. 253 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 254 * When prohibited or (strongly) discouraged: classes can not have 2 hours in between. They may not overlap in time 255 * but must be taught on the same days. 256 */ 257 NHB_2("NHB(2)", "2 Hours Between", 20, 24, BTB_TIME.check(), Flag.BACK_TO_BACK), 258 /** 259 * 3 Hours Between: Given classes must have exactly 3 hours in between the end of one and the beginning of another. 260 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 261 * When prohibited or (strongly) discouraged: classes can not have 3 hours in between. They may not overlap in time 262 * but must be taught on the same days. 263 */ 264 NHB_3("NHB(3)", "3 Hours Between", 30, 36, BTB_TIME.check(), Flag.BACK_TO_BACK), 265 /** 266 * 4 Hours Between: Given classes must have exactly 4 hours in between the end of one and the beginning of another. 267 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 268 * When prohibited or (strongly) discouraged: classes can not have 4 hours in between. They may not overlap in time 269 * but must be taught on the same days. 270 */ 271 NHB_4("NHB(4)", "4 Hours Between", 40, 48, BTB_TIME.check(), Flag.BACK_TO_BACK), 272 /** 273 * 5 Hours Between: Given classes must have exactly 5 hours in between the end of one and the beginning of another. 274 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 275 * When prohibited or (strongly) discouraged: classes can not have 5 hours in between. They may not overlap in time 276 * but must be taught on the same days. 277 */ 278 NHB_5("NHB(5)", "5 Hours Between", 50, 60, BTB_TIME.check(), Flag.BACK_TO_BACK), 279 /** 280 * 6 Hours Between: Given classes must have exactly 6 hours in between the end of one and the beginning of another. 281 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 282 * When prohibited or (strongly) discouraged: classes can not have 6 hours in between. They may not overlap in time 283 * but must be taught on the same days. 284 */ 285 NHB_6("NHB(6)", "6 Hours Between", 60, 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 286 /** 287 * 7 Hours Between: Given classes must have exactly 7 hours in between the end of one and the beginning of another. 288 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 289 * When prohibited or (strongly) discouraged: classes can not have 7 hours in between. They may not overlap in time 290 * but must be taught on the same days. 291 */ 292 NHB_7("NHB(7)", "7 Hours Between", 70, 84, BTB_TIME.check(), Flag.BACK_TO_BACK), 293 /** 294 * 8 Hours Between: Given classes must have exactly 8 hours in between the end of one and the beginning of another. 295 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 296 * When prohibited or (strongly) discouraged: classes can not have 8 hours in between. They may not overlap in time 297 * but must be taught on the same days. 298 */ 299 NHB_8("NHB(8)", "8 Hours Between", 80, 96, BTB_TIME.check(), Flag.BACK_TO_BACK), 300 /** 301 * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual 302 * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR> 303 * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the 304 * same half-hour period of any day of the week. 305 */ 306 SAME_START("SAME_START", "Same Start Time", new PairCheck() { 307 @Override 308 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 309 return 310 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) == 311 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 312 } 313 @Override 314 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 315 return 316 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) != 317 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 318 }}), 319 /** 320 * Same Room: Given classes must be taught in the same room.<BR> 321 * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room. 322 */ 323 SAME_ROOM("SAME_ROOM", "Same Room", new PairCheck() { 324 @Override 325 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 326 return plc1.sameRooms(plc2); 327 } 328 @Override 329 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 330 return !plc1.sameRooms(plc2); 331 }}), 332 /** 333 * At Least 1 Hour Between: Given classes have to have 1 hour or more in between.<BR> 334 * When prohibited or (strongly) discouraged: given classes have to have less than 1 hour in between. 335 */ 336 NHB_GTE_1("NHB_GTE(1)", "At Least 1 Hour Between", 6, 288, BTB_TIME.check(), Flag.BACK_TO_BACK), 337 /** 338 * Less Than 6 Hours Between: Given classes must have less than 6 hours from end of first class to the beginning of 339 * the next. Given classes must also be taught on the same days.<BR> 340 * When prohibited or (strongly) discouraged: given classes must have 6 or more hours between. This constraint does 341 * not carry over from classes taught at the end of one day to the beginning of the next. 342 */ 343 NHB_LT_6("NHB_LT(6)", "Less Than 6 Hours Between", 0, 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 344 /** 345 * 1.5 Hour Between: Given classes must have exactly 90 minutes in between the end of one and the beginning of another. 346 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 347 * When prohibited or (strongly) discouraged: classes can not have 90 minutes in between. They may not overlap in time 348 * but must be taught on the same days. 349 */ 350 NHB_1_5("NHB(1.5)", "1.5 Hour Between", 15, 18, BTB_TIME.check(), Flag.BACK_TO_BACK), 351 /** 352 * 4.5 Hours Between: Given classes must have exactly 4.5 hours in between the end of one and the beginning of another. 353 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 354 * When prohibited or (strongly) discouraged: classes can not have 4.5 hours in between. They may not overlap in time 355 * but must be taught on the same days. 356 */ 357 NHB_4_5("NHB(4.5)", "4.5 Hours Between", 45, 54, BTB_TIME.check(), Flag.BACK_TO_BACK), 358 /** 359 * Same Students: Given classes are treated as they are attended by the same students, i.e., they cannot overlap in time 360 * and if they are back-to-back the assigned rooms cannot be too far (student limit is used). 361 */ 362 SAME_STUDENTS("SAME_STUDENTS", "Same Students", new PairCheck() { 363 @Override 364 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 365 return !JenrlConstraint.isInConflict(plc1, plc2, ((TimetableModel)gc.getModel()).getDistanceMetric()); 366 } 367 @Override 368 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 369 return true; 370 }}), 371 /** 372 * Same Instructor: Given classes are treated as they are taught by the same instructor, i.e., they cannot overlap in time 373 * and if they are back-to-back the assigned rooms cannot be too far (instructor limit is used).<BR> 374 * If the constraint is required and the classes are back-to-back, discouraged and strongly discouraged distances between 375 * assigned rooms are also considered. 376 */ 377 SAME_INSTR("SAME_INSTR", "Same Instructor", new PairCheck() { 378 @Override 379 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 380 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 381 if (t1.shareDays(t2) && t1.shareWeeks(t2)) { 382 if (t1.shareHours(t2)) return false; // overlap 383 DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric(); 384 if ((t1.getStartSlot() + t1.getLength() == t2.getStartSlot() || t2.getStartSlot() + t2.getLength() == t1.getStartSlot())) { 385 if (Placement.getDistanceInMeters(m, plc1, plc2) > m.getInstructorProhibitedLimit()) 386 return false; 387 } else if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) { 388 if (t1.getStartSlot() + t1.getLength() < t2.getStartSlot() && 389 Placement.getDistanceInMinutes(m, plc1, plc2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength())) 390 return false; 391 if (t2.getStartSlot() + t2.getLength() < t1.getStartSlot() && 392 Placement.getDistanceInMinutes(m, plc1, plc2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength())) 393 return false; 394 } 395 } 396 return true; 397 } 398 @Override 399 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 400 return true; 401 }}), 402 /** 403 * Can Share Room: Given classes can share the room (use the room in the same time) if the room is big enough. 404 */ 405 CAN_SHARE_ROOM("CAN_SHARE_ROOM", "Can Share Room", null, Flag.CAN_SHARE_ROOM), 406 /** 407 * Precedence: Given classes have to be taught in the given order (the first meeting of the first class has to end before 408 * the first meeting of the second class etc.)<BR> 409 * When prohibited or (strongly) discouraged: classes have to be taught in the order reverse to the given one. 410 */ 411 PRECEDENCE("PRECEDENCE", "Precedence", new PairCheck() { 412 @Override 413 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 414 return gc.isPrecedence(plc1, plc2, true, true); 415 } 416 @Override 417 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 418 return gc.isPrecedence(plc1, plc2, false, true); 419 }}), 420 /** 421 * Back-To-Back Day: Classes must be offered on adjacent days and may be placed in different rooms.<BR> 422 * When prohibited or (strongly) discouraged: classes can not be taught on adjacent days. They also can not be taught 423 * on the same days. This means that there must be at least one day between these classes. 424 */ 425 BTB_DAY("BTB_DAY", "Back-To-Back Day", new PairCheck() { 426 @Override 427 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 428 return 429 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 430 isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 431 } 432 @Override 433 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 434 return 435 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 436 !isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 437 }}), 438 /** 439 * Meet Together: Given classes are meeting together (same as if the given classes require constraints Can Share Room, 440 * Same Room, Same Time and Same Days all together). 441 */ 442 MEET_WITH("MEET_WITH", "Meet Together", new PairCheck() { 443 @Override 444 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 445 return 446 plc1.sameRooms(plc2) && 447 sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 448 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 449 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 450 451 } 452 @Override 453 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 454 return true; 455 }}, Flag.CAN_SHARE_ROOM), 456 /** 457 * More Than 1 Day Between: Given classes must have two or more days in between.<br> 458 * When prohibited or (strongly) discouraged: given classes must be offered on adjacent days or with at most one day in between. 459 */ 460 NDB_GT_1("NDB_GT_1", "More Than 1 Day Between", new PairCheck() { 461 @Override 462 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 463 return 464 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 465 isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 466 } 467 @Override 468 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 469 return 470 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 471 !isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 472 }}), 473 /** 474 * Children Cannot Overlap: If parent classes do not overlap in time, children classes can not overlap in time as well.<BR> 475 * Note: This constraint only needs to be put on the parent classes. Preferred configurations are Required All Classes 476 * or Pairwise (Strongly) Preferred. 477 */ 478 CH_NOTOVERLAP("CH_NOTOVERLAP", "Children Cannot Overlap", new PairCheck() { 479 @Override 480 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 481 return gc.isChildrenNotOverlap(plc1.variable(), plc1, plc2.variable(), plc2); 482 } 483 @Override 484 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 485 return true; 486 }}), 487 /** 488 * Next Day: The second class has to be placed on the following day of the first class (if the first class is on Friday, 489 * second class have to be on Monday).<br> 490 * When prohibited or (strongly) discouraged: The second class has to be placed on the previous day of the first class 491 * (if the first class is on Monday, second class have to be on Friday).<br> 492 * Note: This constraint works only between pairs of classes. 493 */ 494 FOLLOWING_DAY("FOLLOWING_DAY", "Next Day", new PairCheck() { 495 @Override 496 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 497 return gc.isFollowingDay(plc1, plc2, true); 498 } 499 @Override 500 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 501 return gc.isFollowingDay(plc1, plc2, false); 502 }}), 503 /** 504 * Two Days After: The second class has to be placed two days after the first class (Monday → Wednesday, Tuesday → 505 * Thurday, Wednesday → Friday, Thursday → Monday, Friday → Tuesday).<br> 506 * When prohibited or (strongly) discouraged: The second class has to be placed two days before the first class (Monday → 507 * Thursday, Tuesday → Friday, Wednesday → Monday, Thursday → Tuesday, Friday → Wednesday).<br> 508 * Note: This constraint works only between pairs of classes. 509 */ 510 EVERY_OTHER_DAY("EVERY_OTHER_DAY", "Two Days After", new PairCheck() { 511 @Override 512 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 513 return gc.isEveryOtherDay(plc1, plc2, true); 514 } 515 @Override 516 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 517 return gc.isEveryOtherDay(plc1, plc2, false); 518 }}), 519 /** 520 * At Most 5 Hours A Day: Classes are to be placed in a way that there is no more than five hours in any day. 521 */ 522 MAX_HRS_DAY_5("MAX_HRS_DAY(5)", "At Most 5 Hours A Day", 60, null, Flag.MAX_HRS_DAY), 523 /** 524 * At Most 6 Hours A Day: Classes are to be placed in a way that there is no more than six hours in any day. 525 */ 526 MAX_HRS_DAY_6("MAX_HRS_DAY(6)", "At Most 6 Hours A Day", 72, null, Flag.MAX_HRS_DAY), 527 /** 528 * At Most 7 Hours A Day: Classes are to be placed in a way that there is no more than seven hours in any day. 529 */ 530 MAX_HRS_DAY_7("MAX_HRS_DAY(7)", "At Most 7 Hours A Day", 84, null, Flag.MAX_HRS_DAY), 531 /** 532 * At Most 8 Hours A Day: Classes are to be placed in a way that there is no more than eight hours in any day. 533 */ 534 MAX_HRS_DAY_8("MAX_HRS_DAY(8)", "At Most 8 Hours A Day", 96, null, Flag.MAX_HRS_DAY), 535 /** 536 * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br> 537 * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns. 538 */ 539 SAME_WEEKS("SAME_WEEKS", "Same Weeks", new PairCheck() { 540 @Override 541 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 542 return plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode()); 543 } 544 @Override 545 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 546 return !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation()); 547 }}), 548 /** 549 * Classes (of different courses) are to be attended by the same students. For instance, 550 * if class A1 (of a course A) and class B1 (of a course B) are linked, a student requesting 551 * both courses must attend A1 if and only if he also attends B1. This is a student sectioning 552 * constraint that is interpreted as Same Students constraint during course timetabling. 553 */ 554 LINKED_SECTIONS("LINKED_SECTIONS", "Linked Classes", SAME_STUDENTS.check()), 555 /** 556 * Back-To-Back Precedence: Given classes have to be taught in the given order, on the same days, 557 * and in adjacent time segments. 558 * When prohibited or (strongly) discouraged: Given classes have to be taught in the given order, 559 * on the same days, but cannot be back-to-back. 560 */ 561 BTB_PRECEDENCE("BTB_PRECEDENCE", "Back-To-Back Precedence", new PairCheck() { 562 @Override 563 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 564 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 565 } 566 @Override 567 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 568 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 569 }}, Flag.BACK_TO_BACK), 570 571 /** 572 * Same Days-Time: Given classes must be taught at the same time of day and on the same days. 573 * It is the combination of Same Days and Same Time distribution preferences. 574 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 575 * during the same time. 576 */ 577 SAME_DAYS_TIME("SAME_D_T", "Same Days-Time", new PairCheck() { 578 @Override 579 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 580 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 581 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 582 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 583 } 584 @Override 585 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 586 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 587 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 588 }}), 589 /** 590 * Same Days-Room-Time: Given classes must be taught at the same time of day, on the same days and in the same room. 591 * It is the combination of Same Days, Same Time and Same Room distribution preferences. 592 * Note that this constraint is the same as Meet Together constraint, except it does not allow room sharing. In other words, 593 * it is only useful when these classes are taught during non-overlapping date patterns. 594 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 595 * during the same time in the same room. 596 */ 597 SAME_DAYS_ROOM_TIME("SAME_D_R_T", "Same Days-Room-Time", new PairCheck() { 598 @Override 599 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 600 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 601 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 602 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 603 plc1.sameRooms(plc2); 604 } 605 @Override 606 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 607 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 608 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) || 609 !plc1.sameRooms(plc2); 610 }}), 611 ; 612 613 String iReference, iName; 614 int iFlag = 0; 615 Flag[] iFlags = null; 616 int iMin = 0, iMax = 0; 617 PairCheck iCheck = null; 618 ConstraintType(String reference, String name, PairCheck check, Flag... flags) { 619 iReference = reference; 620 iName = name; 621 iCheck = check; 622 iFlags = flags; 623 for (Flag f: flags) 624 iFlag |= f.flag(); 625 } 626 ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) { 627 this(reference, name, check, flags); 628 iMin = iMax = limit; 629 } 630 ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) { 631 this(reference, name, check, flags); 632 iMin = min; 633 iMax = max; 634 } 635 636 /** Constraint reference */ 637 public String reference() { return iReference; } 638 /** Constraint name */ 639 public String getName() { return iName; } 640 /** Minimum (gap) parameter */ 641 public int getMin() { return iMin; } 642 /** Maximum (gap, hours a day) parameter */ 643 public int getMax() { return iMax; } 644 645 /** Flag check (true if contains given flag) */ 646 public boolean is(Flag f) { return (iFlag & f.flag()) != 0; } 647 648 /** Constraint type from reference */ 649 public static ConstraintType get(String reference) { 650 for (ConstraintType t: ConstraintType.values()) 651 if (t.reference().equals(reference)) return t; 652 return null; 653 } 654 655 /** True if a required or preferred constraint is satisfied between a pair of placements */ 656 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { return (iCheck == null ? true : iCheck.isSatisfied(gc, plc1, plc2)); } 657 /** True if a prohibited or discouraged constraint is satisfied between a pair of placements */ 658 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return (iCheck == null ? true : iCheck.isViolated(gc, plc1, plc2)); } 659 /** Pair check */ 660 private PairCheck check() { return iCheck; } 661 } 662 663 public GroupConstraint() { 664 } 665 666 @Override 667 public void setModel(Model<Lecture, Placement> model) { 668 super.setModel(model); 669 if (model != null) { 670 DataProperties config = ((TimetableModel)model).getProperties(); 671 iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0); 672 iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true); 673 } 674 } 675 676 @Override 677 public void addVariable(Lecture lecture) { 678 if (!variables().contains(lecture)) 679 super.addVariable(lecture); 680 if (getType().is(Flag.CH_NOTOVERLAP)) { 681 if (lecture.getChildrenSubpartIds() != null) { 682 for (Long subpartId: lecture.getChildrenSubpartIds()) { 683 for (Lecture ch : lecture.getChildren(subpartId)) { 684 if (!variables().contains(ch)) 685 super.addVariable(ch); 686 } 687 } 688 } 689 } 690 } 691 692 @Override 693 public void removeVariable(Lecture lecture) { 694 if (variables().contains(lecture)) 695 super.removeVariable(lecture); 696 if (getType().is(Flag.CH_NOTOVERLAP)) { 697 if (lecture.getChildrenSubpartIds() != null) { 698 for (Long subpartId: lecture.getChildrenSubpartIds()) { 699 for (Lecture ch : lecture.getChildren(subpartId)) { 700 if (variables().contains(ch)) 701 super.removeVariable(ch); 702 } 703 } 704 } 705 } 706 } 707 708 /** 709 * Constructor 710 * 711 * @param id 712 * constraint id 713 * @param type 714 * constraString type (e.g, {@link ConstraintType#SAME_TIME}) 715 * @param preference 716 * time preference ("R" for required, "P" for prohibited, "-2", 717 * "-1", "1", "2" for soft preference) 718 */ 719 public GroupConstraint(Long id, ConstraintType type, String preference) { 720 iConstraintId = id; 721 iType = type; 722 iIsRequired = preference.equals(Constants.sPreferenceRequired); 723 iIsProhibited = preference.equals(Constants.sPreferenceProhibited); 724 iPreference = Constants.preference2preferenceLevel(preference); 725 } 726 727 /** Constraint id */ 728 public Long getConstraintId() { 729 return iConstraintId; 730 } 731 732 @Override 733 public long getId() { 734 return (iConstraintId == null ? -1 : iConstraintId.longValue()); 735 } 736 737 /** Generated unique id */ 738 protected long getGeneratedId() { 739 return iId; 740 } 741 742 /** ConstraString type (e.g, {@link ConstraintType#SAME_TIME}) */ 743 public ConstraintType getType() { 744 return iType; 745 } 746 747 public void setType(ConstraintType type) { 748 iType = type; 749 } 750 751 /** Is constraint required */ 752 public boolean isRequired() { 753 return iIsRequired; 754 } 755 756 /** Is constraint prohibited */ 757 public boolean isProhibited() { 758 return iIsProhibited; 759 } 760 761 /** 762 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for 763 * preference 764 */ 765 public String getPrologPreference() { 766 return Constants.preferenceLevel2preference(iPreference); 767 } 768 769 @Override 770 public boolean isConsistent(Placement value1, Placement value2) { 771 if (!isHard()) 772 return true; 773 if (!isSatisfiedPair(value1, value2)) 774 return false; 775 if (getType().is(Flag.BACK_TO_BACK)) { 776 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 777 assignments.put(value1.variable(), value1); 778 assignments.put(value2.variable(), value2); 779 if (!isSatisfiedSeq(assignments, false, null)) 780 return false; 781 } 782 if (getType().is(Flag.MAX_HRS_DAY)) { 783 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 784 assignments.put(value1.variable(), value1); 785 assignments.put(value2.variable(), value2); 786 for (int dayCode: Constants.DAY_CODES) { 787 if (nrSlotsADay(dayCode, assignments, null) > getType().getMax()) 788 return false; 789 } 790 } 791 return true; 792 } 793 794 @Override 795 public void computeConflicts(Placement value, Set<Placement> conflicts) { 796 if (!isHard()) 797 return; 798 for (Lecture v : variables()) { 799 if (v.equals(value.variable())) 800 continue; // ignore this variable 801 if (v.getAssignment() == null) 802 continue; // there is an unassigned variable -- great, still a 803 // chance to get violated 804 if (!isSatisfiedPair(v.getAssignment(), value)) 805 conflicts.add(v.getAssignment()); 806 } 807 if (getType().is(Flag.BACK_TO_BACK)) { 808 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 809 assignments.put(value.variable(), value); 810 if (!isSatisfiedSeq(assignments, true, conflicts)) 811 conflicts.add(value); 812 } 813 if (getType().is(Flag.MAX_HRS_DAY)) { 814 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 815 assignments.put(value.variable(), value); 816 for (int dayCode: Constants.DAY_CODES) { 817 if (nrSlotsADay(dayCode, assignments, conflicts) > getType().getMax()) { 818 List<Placement> adepts = new ArrayList<Placement>(); 819 for (Lecture lecture: assignedVariables()) { 820 if (conflicts.contains(lecture.getAssignment()) || lecture.equals(value.variable())) continue; 821 if (lecture.getAssignment().getTimeLocation() == null) continue; 822 if ((lecture.getAssignment().getTimeLocation().getDayCode() & dayCode) == 0) continue; 823 adepts.add(lecture.getAssignment()); 824 } 825 do { 826 Placement conflict = ToolBox.random(adepts); 827 adepts.remove(conflict); 828 conflicts.add(conflict); 829 } while (!adepts.isEmpty() && nrSlotsADay(dayCode, assignments, conflicts) > getType().getMax()); 830 } 831 } 832 } 833 834 // Forward checking 835 forwardCheck(value, conflicts, new HashSet<GroupConstraint>()); 836 } 837 838 public void forwardCheck(Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore) { 839 try { 840 ignore.add(this); 841 842 int neededSize = value.variable().maxRoomUse(); 843 844 for (Lecture lecture: variables()) { 845 if (conflicts.contains(value)) break; // already conflicting 846 847 if (lecture.equals(value.variable())) continue; // Skip this lecture 848 if (lecture.getAssignment() != null) { // Has assignment, check whether it is conflicting 849 if (isSatisfiedPair(value, lecture.getAssignment())) { 850 // Increase needed size if the assignment is of the same room and overlapping in time 851 if (getType().is(Flag.CAN_SHARE_ROOM) && sameRoomAndOverlaps(value, lecture.getAssignment())) { 852 neededSize += lecture.maxRoomUse(); 853 } 854 continue; 855 } 856 conflicts.add(lecture.getAssignment()); 857 } 858 859 // Look for supporting assignments assignment 860 boolean shareRoomAndOverlaps = true; 861 List<Placement> supporters = new ArrayList<Placement>(); 862 for (Placement other: lecture.values()) { 863 if (isSatisfiedPair(value, other)) { 864 supporters.add(other); 865 if (getType().is(Flag.CAN_SHARE_ROOM) && shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 866 shareRoomAndOverlaps = false; 867 } 868 } 869 // No supporting assignment -> fail 870 if (supporters.isEmpty()) { 871 conflicts.add(value); // other class cannot be assigned with this value 872 return; 873 } 874 // Increase needed size if all supporters are of the same room and in overlapping times 875 if (getType().is(Flag.CAN_SHARE_ROOM) && shareRoomAndOverlaps) { 876 neededSize += lecture.maxRoomUse(); 877 } 878 879 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 880 if (supporters.size() == 1) { 881 Placement supporter = supporters.get(0); 882 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 883 if (other instanceof WeakeningConstraint) continue; 884 if (other instanceof GroupConstraint) { 885 GroupConstraint gc = (GroupConstraint)other; 886 if (!ignore.contains(gc)) 887 gc.forwardCheck(supporter, conflicts, ignore); 888 } else { 889 other.computeConflicts(supporter, conflicts); 890 } 891 } 892 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 893 if (other instanceof WeakeningConstraint) continue; 894 other.computeConflicts(supporter, conflicts); 895 } 896 897 if (conflicts.contains(supporter)) 898 conflicts.add(value); 899 } 900 } 901 902 if (getType().is(Flag.CAN_SHARE_ROOM) && neededSize > value.getRoomSize()) { 903 // room is too small to fit all meet with classes 904 conflicts.add(value); 905 } 906 907 } finally { 908 ignore.remove(this); 909 } 910 } 911 912 @Override 913 public boolean inConflict(Placement value) { 914 if (!isHard()) 915 return false; 916 for (Lecture v : variables()) { 917 if (v.equals(value.variable())) 918 continue; // ignore this variable 919 if (v.getAssignment() == null) 920 continue; // there is an unassigned variable -- great, still a 921 // chance to get violated 922 if (!isSatisfiedPair(v.getAssignment(), value)) 923 return true; 924 } 925 if (getType().is(Flag.BACK_TO_BACK)) { 926 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 927 assignments.put(value.variable(), value); 928 if (!isSatisfiedSeq(assignments, true, null)) 929 return true; 930 } 931 if (getType().is(Flag.MAX_HRS_DAY)) { 932 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 933 assignments.put(value.variable(), value); 934 for (int dayCode: Constants.DAY_CODES) { 935 if (nrSlotsADay(dayCode, assignments, null) > getType().getMax()) 936 return true; 937 } 938 } 939 return false; 940 } 941 942 /** Constraint preference (0 if prohibited or reqired) */ 943 public int getPreference() { 944 return iPreference; 945 } 946 947 /** 948 * Current constraint preference (0 if prohibited or reqired, depends on 949 * current satisfaction of the constraint) 950 */ 951 public int getCurrentPreference() { 952 if (isHard()) return 0; // no preference 953 if (countAssignedVariables() < 2) return 0; // not enough variable 954 if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day 955 int over = 0; 956 for (int dayCode: Constants.DAY_CODES) 957 over += Math.max(0, nrSlotsADay(dayCode, null, null) - getType().getMax()); 958 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 959 } 960 int nrViolatedPairs = 0; 961 for (Lecture v1 : variables()) { 962 if (v1.getAssignment() == null) continue; 963 for (Lecture v2 : variables()) { 964 if (v2.getAssignment() == null || v1.getId() >= v2.getId()) continue; 965 if (!isSatisfiedPair(v1.getAssignment(), v2.getAssignment())) nrViolatedPairs++; 966 } 967 } 968 if (getType().is(Flag.BACK_TO_BACK)) { 969 Set<Placement> conflicts = new HashSet<Placement>(); 970 if (isSatisfiedSeq(new HashMap<Lecture, Placement>(), true, conflicts)) 971 nrViolatedPairs += conflicts.size(); 972 else 973 nrViolatedPairs = variables().size(); 974 } 975 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 976 } 977 978 /** Current constraint preference (if given placement is assigned) */ 979 public int getCurrentPreference(Placement placement) { 980 if (getType().is(Flag.MAX_HRS_DAY)) { 981 if (placement.getTimeLocation() == null) return 0; 982 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 983 assignments.put(placement.variable(), placement); 984 int over = 0; 985 for (int dayCode: Constants.DAY_CODES) 986 if ((placement.getTimeLocation().getDayCode() & dayCode) != 0) 987 over += Math.min(Math.max(0, nrSlotsADay(dayCode, assignments, null) - getType().getMax()), placement.getTimeLocation().getLength()); 988 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 989 } 990 int nrViolatedPairs = 0; 991 for (Lecture v1 : variables()) { 992 if (v1.getAssignment() == null || v1.equals(placement.variable())) continue; 993 if (!isSatisfiedPair(v1.getAssignment(), placement)) nrViolatedPairs++; 994 } 995 if (getType().is(Flag.BACK_TO_BACK)) { 996 HashMap<Lecture, Placement> assignment = new HashMap<Lecture, Placement>(); 997 assignment.put(placement.variable(), placement); 998 Set<Placement> conflicts = new HashSet<Placement>(); 999 if (isSatisfiedSeq(assignment, true, conflicts)) 1000 nrViolatedPairs += conflicts.size(); 1001 else 1002 nrViolatedPairs = variables().size(); 1003 } 1004 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 1005 } 1006 1007 @Override 1008 public void unassigned(long iteration, Placement value) { 1009 super.unassigned(iteration, value); 1010 if (iIsRequired || iIsProhibited) 1011 return; 1012 getModel().getCriterion(DistributionPreferences.class).inc(-iLastPreference); 1013 iLastPreference = Math.min(0, getCurrentPreference()); 1014 getModel().getCriterion(DistributionPreferences.class).inc(iLastPreference); 1015 } 1016 1017 @Override 1018 public void assigned(long iteration, Placement value) { 1019 super.assigned(iteration, value); 1020 if (iIsRequired || iIsProhibited) 1021 return; 1022 getModel().getCriterion(DistributionPreferences.class).inc(-iLastPreference); 1023 iLastPreference = Math.min(0, getCurrentPreference()); 1024 getModel().getCriterion(DistributionPreferences.class).inc(iLastPreference); 1025 } 1026 1027 @Override 1028 public String toString() { 1029 StringBuffer sb = new StringBuffer(); 1030 sb.append(getName()); 1031 sb.append(" between "); 1032 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 1033 Lecture v = e.next(); 1034 sb.append(v.getName()); 1035 if (e.hasNext()) 1036 sb.append(", "); 1037 } 1038 return sb.toString(); 1039 } 1040 1041 @Override 1042 public boolean isHard() { 1043 return iIsRequired || iIsProhibited; 1044 } 1045 1046 @Override 1047 public String getName() { 1048 return getType().getName(); 1049 } 1050 1051 1052 private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) { 1053 int ord1 = variables().indexOf(p1.variable()); 1054 int ord2 = variables().indexOf(p2.variable()); 1055 TimeLocation t1 = null, t2 = null; 1056 if (ord1 < ord2) { 1057 if (firstGoesFirst) { 1058 t1 = p1.getTimeLocation(); 1059 t2 = p2.getTimeLocation(); 1060 } else { 1061 t2 = p1.getTimeLocation(); 1062 t1 = p2.getTimeLocation(); 1063 } 1064 } else { 1065 if (!firstGoesFirst) { 1066 t1 = p1.getTimeLocation(); 1067 t2 = p2.getTimeLocation(); 1068 } else { 1069 t2 = p1.getTimeLocation(); 1070 t1 = p2.getTimeLocation(); 1071 } 1072 } 1073 if (considerDatePatterns && iPrecedenceConsiderDatePatterns) { 1074 boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode())); 1075 if (!sameDatePattern) { 1076 int m1 = getFirstMeeting(t1), m2 = getFirstMeeting(t2); 1077 if (m1 != m2) return m1 < m2; 1078 } 1079 } 1080 return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement(); 1081 } 1082 1083 private int getFirstMeeting(TimeLocation time) { 1084 int idx = -1; 1085 while ((idx = time.getWeekCode().nextSetBit(1 + idx)) >= 0) { 1086 int dow = (idx + iDayOfWeekOffset) % 7; 1087 if ((time.getDayCode() & Constants.DAY_CODES[dow]) != 0) break; 1088 } 1089 return idx; 1090 } 1091 1092 private static boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) { 1093 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1094 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1095 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1096 if (f1 < 0) 1097 f1 = i; 1098 e1 = i; 1099 } 1100 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1101 if (f2 < 0) 1102 f2 = i; 1103 e2 = i; 1104 } 1105 } 1106 return (e1 + 1 == f2) || (e2 + 1 == f1); 1107 } 1108 1109 private static boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) { 1110 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1111 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1112 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1113 if (f1 < 0) 1114 f1 = i; 1115 e1 = i; 1116 } 1117 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1118 if (f2 < 0) 1119 f2 = i; 1120 e2 = i; 1121 } 1122 } 1123 return (e1 - f2 > 2) || (e2 - f1 > 2); 1124 } 1125 1126 private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1127 int ord1 = variables().indexOf(p1.variable()); 1128 int ord2 = variables().indexOf(p2.variable()); 1129 TimeLocation t1 = null, t2 = null; 1130 if (ord1 < ord2) { 1131 if (firstGoesFirst) { 1132 t1 = p1.getTimeLocation(); 1133 t2 = p2.getTimeLocation(); 1134 } else { 1135 t2 = p1.getTimeLocation(); 1136 t1 = p2.getTimeLocation(); 1137 } 1138 } else { 1139 if (!firstGoesFirst) { 1140 t1 = p1.getTimeLocation(); 1141 t2 = p2.getTimeLocation(); 1142 } else { 1143 t2 = p1.getTimeLocation(); 1144 t1 = p2.getTimeLocation(); 1145 } 1146 } 1147 int f1 = -1, f2 = -1, e1 = -1; 1148 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1149 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1150 if (f1 < 0) 1151 f1 = i; 1152 e1 = i; 1153 } 1154 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1155 if (f2 < 0) 1156 f2 = i; 1157 } 1158 } 1159 return ((e1 + 1) % Constants.NR_DAYS_WEEK == f2); 1160 } 1161 1162 private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1163 int ord1 = variables().indexOf(p1.variable()); 1164 int ord2 = variables().indexOf(p2.variable()); 1165 TimeLocation t1 = null, t2 = null; 1166 if (ord1 < ord2) { 1167 if (firstGoesFirst) { 1168 t1 = p1.getTimeLocation(); 1169 t2 = p2.getTimeLocation(); 1170 } else { 1171 t2 = p1.getTimeLocation(); 1172 t1 = p2.getTimeLocation(); 1173 } 1174 } else { 1175 if (!firstGoesFirst) { 1176 t1 = p1.getTimeLocation(); 1177 t2 = p2.getTimeLocation(); 1178 } else { 1179 t2 = p1.getTimeLocation(); 1180 t1 = p2.getTimeLocation(); 1181 } 1182 } 1183 int f1 = -1, f2 = -1, e1 = -1; 1184 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1185 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1186 if (f1 < 0) 1187 f1 = i; 1188 e1 = i; 1189 } 1190 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1191 if (f2 < 0) 1192 f2 = i; 1193 } 1194 } 1195 return ((e1 + 2) % Constants.NR_DAYS_WEEK == f2); 1196 } 1197 1198 private static boolean sameDays(int[] days1, int[] days2) { 1199 if (days2.length < days1.length) 1200 return sameDays(days2, days1); 1201 int i2 = 0; 1202 for (int i1 = 0; i1 < days1.length; i1++) { 1203 int d1 = days1[i1]; 1204 while (true) { 1205 if (i2 == days2.length) 1206 return false; 1207 int d2 = days2[i2]; 1208 if (d1 == d2) 1209 break; 1210 i2++; 1211 if (i2 == days2.length) 1212 return false; 1213 } 1214 i2++; 1215 } 1216 return true; 1217 } 1218 1219 private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) { 1220 return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()); 1221 } 1222 1223 private static boolean sameHours(int start1, int len1, int start2, int len2) { 1224 if (len1 > len2) 1225 return sameHours(start2, len2, start1, len1); 1226 start1 %= Constants.SLOTS_PER_DAY; 1227 start2 %= Constants.SLOTS_PER_DAY; 1228 return (start1 >= start2 && start1 + len1 <= start2 + len2); 1229 } 1230 1231 private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) { 1232 if (gapMin <= totalGap && totalGap <= gapMax) 1233 return true; 1234 if (totalGap < 2 * gapMin) 1235 return false; 1236 for (int i = 0; i < lengths.size(); i++) { 1237 int length = lengths.get(i); 1238 lengths.remove(i); 1239 for (int gap = gapMin; gap <= gapMax; gap++) 1240 if (canFill(totalGap - gap - length, gapMin, gapMax, lengths)) 1241 return true; 1242 lengths.add(i, length); 1243 } 1244 return false; 1245 } 1246 1247 private boolean isSatisfiedSeq(HashMap<Lecture, Placement> assignments, boolean considerCurrentAssignments, 1248 Set<Placement> conflicts) { 1249 if (conflicts == null) 1250 return isSatisfiedSeqCheck(assignments, considerCurrentAssignments, conflicts); 1251 else { 1252 Set<Placement> bestConflicts = isSatisfiedRecursive(0, assignments, considerCurrentAssignments, conflicts, 1253 new HashSet<Placement>(), null); 1254 if (bestConflicts == null) 1255 return false; 1256 conflicts.addAll(bestConflicts); 1257 return true; 1258 } 1259 } 1260 1261 private Set<Placement> isSatisfiedRecursive(int idx, HashMap<Lecture, Placement> assignments, 1262 boolean considerCurrentAssignments, Set<Placement> conflicts, Set<Placement> newConflicts, 1263 Set<Placement> bestConflicts) { 1264 if (idx == variables().size() && newConflicts.isEmpty()) 1265 return bestConflicts; 1266 if (isSatisfiedSeqCheck(assignments, considerCurrentAssignments, conflicts)) { 1267 if (bestConflicts == null || bestConflicts.size() > newConflicts.size()) 1268 return new HashSet<Placement>(newConflicts); 1269 return bestConflicts; 1270 } 1271 if (idx == variables().size()) 1272 return bestConflicts; 1273 bestConflicts = isSatisfiedRecursive(idx + 1, assignments, considerCurrentAssignments, conflicts, newConflicts, 1274 bestConflicts); 1275 Lecture lecture = variables().get(idx); 1276 if (assignments != null && assignments.containsKey(lecture)) 1277 return bestConflicts; 1278 Placement placement = (assignments == null ? null : assignments.get(lecture)); 1279 if (placement == null && considerCurrentAssignments) 1280 placement = lecture.getAssignment(); 1281 if (placement == null) 1282 return bestConflicts; 1283 if (conflicts != null && conflicts.contains(placement)) 1284 return bestConflicts; 1285 conflicts.add(placement); 1286 newConflicts.add(placement); 1287 bestConflicts = isSatisfiedRecursive(idx + 1, assignments, considerCurrentAssignments, conflicts, newConflicts, 1288 bestConflicts); 1289 newConflicts.remove(placement); 1290 conflicts.remove(placement); 1291 return bestConflicts; 1292 } 1293 1294 private boolean isSatisfiedSeqCheck(HashMap<Lecture, Placement> assignments, boolean considerCurrentAssignments, 1295 Set<Placement> conflicts) { 1296 if (!getType().is(Flag.BACK_TO_BACK)) return true; 1297 int gapMin = getType().getMin(); 1298 int gapMax = getType().getMax(); 1299 1300 List<Integer> lengths = new ArrayList<Integer>(); 1301 1302 Placement[] res = new Placement[Constants.SLOTS_PER_DAY]; 1303 for (int i = 0; i < Constants.SLOTS_PER_DAY; i++) 1304 res[i] = null; 1305 1306 int nrLectures = 0; 1307 1308 for (Lecture lecture : variables()) { 1309 Placement placement = (assignments == null ? null : assignments.get(lecture)); 1310 if (placement == null && considerCurrentAssignments) 1311 placement = lecture.getAssignment(); 1312 if (placement == null) { 1313 lengths.add(lecture.timeLocations().get(0).getLength()); 1314 } else if (conflicts != null && conflicts.contains(placement)) { 1315 lengths.add(lecture.timeLocations().get(0).getLength()); 1316 } else { 1317 int pos = placement.getTimeLocation().getStartSlot(); 1318 int length = placement.getTimeLocation().getLength(); 1319 for (int j = pos; j < pos + length; j++) { 1320 if (res[j] != null) { 1321 if (conflicts == null) 1322 return false; 1323 if (!assignments.containsKey(lecture)) 1324 conflicts.add(placement); 1325 else if (!assignments.containsKey(res[j].variable())) 1326 conflicts.add(res[j]); 1327 } 1328 } 1329 for (int j = pos; j < pos + length; j++) 1330 res[j] = placement; 1331 nrLectures++; 1332 } 1333 } 1334 if (nrLectures <= 1) 1335 return true; 1336 1337 if (iIsRequired || (!iIsProhibited && iPreference < 0)) { 1338 int i = 0; 1339 Placement p = res[i]; 1340 while (p == null) 1341 p = res[++i]; 1342 i += res[i].getTimeLocation().getLength(); 1343 nrLectures--; 1344 while (nrLectures > 0) { 1345 int gap = 0; 1346 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1347 gap++; 1348 i++; 1349 } 1350 if (i == Constants.SLOTS_PER_DAY) 1351 break; 1352 if (!canFill(gap, gapMin, gapMax, lengths)) 1353 return false; 1354 p = res[i]; 1355 i += res[i].getTimeLocation().getLength(); 1356 nrLectures--; 1357 } 1358 } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) { 1359 int i = 0; 1360 Placement p = res[i]; 1361 while (p == null) 1362 p = res[++i]; 1363 i += res[i].getTimeLocation().getLength(); 1364 nrLectures--; 1365 while (nrLectures > 0) { 1366 int gap = 0; 1367 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1368 gap++; 1369 i++; 1370 } 1371 if (i == Constants.SLOTS_PER_DAY) 1372 break; 1373 if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths)) 1374 && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY, 1375 lengths))) { 1376 return false; 1377 } 1378 p = res[i]; 1379 i += res[i].getTimeLocation().getLength(); 1380 nrLectures--; 1381 } 1382 } 1383 return true; 1384 } 1385 1386 public boolean isSatisfied() { 1387 if (isHard()) return true; 1388 if (countAssignedVariables() < 2) return true; 1389 if (getPreference() == 0) return true; 1390 return isHard() || countAssignedVariables() < 2 || getPreference() == 0 || getCurrentPreference() < 0; 1391 } 1392 1393 public boolean isChildrenNotOverlap(Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) { 1394 if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) { 1395 // same subpart 1396 boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 1397 1398 if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent()) 1399 && lec2.getParent() != null && variables().contains(lec2.getParent())) { 1400 // children overlaps 1401 Placement p1 = lec1.getParent().getAssignment(); 1402 Placement p2 = lec2.getParent().getAssignment(); 1403 // parents not overlap, but children do 1404 if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 1405 return false; 1406 } 1407 1408 if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) { 1409 // parents not overlap 1410 for (Long subpartId: lec1.getChildrenSubpartIds()) { 1411 for (Lecture c1 : lec1.getChildren(subpartId)) { 1412 if (c1.getAssignment() == null) 1413 continue; 1414 for (Lecture c2 : lec2.getChildren(subpartId)) { 1415 if (c2.getAssignment() == null) 1416 continue; 1417 if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) 1418 continue; 1419 Placement p1 = c1.getAssignment(); 1420 Placement p2 = c2.getAssignment(); 1421 // parents not overlap, but children do 1422 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 1423 return false; 1424 } 1425 } 1426 } 1427 } 1428 } else { 1429 // different subpart 1430 } 1431 return true; 1432 } 1433 1434 public boolean isSatisfiedPair(Placement plc1, Placement plc2) { 1435 if (iIsRequired || (!iIsProhibited && iPreference <= 0)) 1436 return getType().isSatisfied(this, plc1, plc2); 1437 else if (iIsProhibited || (!iIsRequired && iPreference > 0)) 1438 return getType().isViolated(this, plc1, plc2); 1439 return true; 1440 } 1441 1442 public boolean canShareRoom() { 1443 return getType().is(Flag.CAN_SHARE_ROOM); 1444 } 1445 1446 private int nrSlotsADay(int dayCode, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1447 Set<Integer> slots = new HashSet<Integer>(); 1448 for (Lecture lecture: variables()) { 1449 Placement placement = (assignments == null ? null : assignments.get(lecture)); 1450 if (placement == null) { 1451 placement = lecture.getAssignment(); 1452 if (conflicts != null && conflicts.contains(placement)) continue; 1453 } 1454 if (placement == null || placement.getTimeLocation() == null) continue; 1455 TimeLocation t = placement.getTimeLocation(); 1456 if (t == null || (t.getDayCode() & dayCode) == 0) continue; 1457 for (int i = 0; i < t.getLength(); i++) 1458 slots.add(i + t.getStartSlot()); 1459 } 1460 return slots.size(); 1461 } 1462 1463 @Override 1464 public boolean equals(Object o) { 1465 if (o == null || !(o instanceof GroupConstraint)) return false; 1466 return getGeneratedId() == ((GroupConstraint) o).getGeneratedId(); 1467 } 1468 }