001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Comparator; 006import java.util.HashMap; 007import java.util.HashSet; 008import java.util.List; 009import java.util.Set; 010 011import org.cpsolver.coursett.Constants; 012import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion; 013import org.cpsolver.coursett.model.Lecture; 014import org.cpsolver.coursett.model.Placement; 015import org.cpsolver.coursett.model.TimeLocation; 016import org.cpsolver.coursett.model.TimetableModel; 017import org.cpsolver.ifs.assignment.Assignment; 018import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 019import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 020import org.cpsolver.ifs.criteria.Criterion; 021 022 023/** 024 * Flexible constraint. <br> 025 * This constraint expresses relations between several classes. Provides similar 026 * functions as Group constraint. Unlike group constraint, Flexible constraint 027 * is able to parse some of its parameters from its reference field<br> 028 * 029 * @version CourseTT 1.3 (University Course Timetabling)<br> 030 * Copyright (C) 2013 Matej Lukac<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 abstract class FlexibleConstraint extends ConstraintWithContext<Lecture, Placement, FlexibleConstraint.FlexibleConstraintContext> { 047 048 protected int iPreference; 049 private boolean iIsRequired; 050 private String iOwner; 051 052 // Constraint type 053 protected FlexibleConstraintType iConstraintType = null; 054 055 // A pattern the constraint was created from 056 protected String iReference = ""; 057 058 // Determines whether the constraint is checked for every week in the semester 059 protected List<BitSet> iWeeks = null; 060 protected Integer iDayOfWeekOffset = null; 061 protected Boolean iPreciseDateComputation = null; 062 063 /** 064 * Flexible constraint types 065 * 066 */ 067 public static enum FlexibleConstraintType { 068 /** 069 * Given classes must be taught in a way there is a break between two blocks of classes. 070 */ 071 MAXBLOCK_BACKTOBACK("_(MaxBlock):([0-9]+):([0-9]+)_", MaxBlockFlexibleConstraint.class, "Block"), 072 /** 073 * There must be a break of a given length in a given time interval. 074 */ 075 BREAK("_(Break):([0-9]+):([0-9]+):([0-9]+)_", BreakFlexibleConstraint.class, "Break"), 076 /** 077 * Limit number of breaks between adjacent classes on a day. 078 */ 079 MAX_BREAKS("_(MaxBreaks):([0-9]+):([0-9]+)_", MaxBreaksFlexibleConstraint.class, "MaxBreaks"), 080 /** 081 * Limit number of weeks on which an a class can take place. 082 */ 083 MAX_WEEKS("_(MaxWeeks):([0-9]+):([0-9]+)_", MaxWeeksFlexibleConstraint.class, "MaxWeeks"), 084 /** 085 * Limit number of days of a week. 086 */ 087 MAX_DAYS("_(MaxDays):([0-9]+)_", MaxDaysFlexibleConstraint.class, "MaxDays"), 088 /** 089 * Minimize free time of an instructor during a day (between the first and the last class). 090 */ 091 MAX_HOLES("_(MaxHoles):([0-9]+)_", MaxHolesFlexibleConstraint.class, "MaxHoles"), 092 /** 093 * Limit number of half-days of a week. 094 */ 095 MAX_HALF_DAYS("_(MaxHalfDays):([0-9]+)_", MaxHalfDaysFlexibleConstraint.class, "MaxHalfDays"), 096 /** 097 * Limit number of consecutive days of a week. 098 */ 099 MAX_CONSECUTIVE_DAYS("_(MaxConsDays):([0-9]+)_", MaxConsecutiveDaysFlexibleConstraint.class, "MaxConsDays"), 100 ; 101 102 private String iPattern; 103 private Class<? extends FlexibleConstraint> iImplementation; 104 private String iName; 105 FlexibleConstraintType(String pattern, Class<? extends FlexibleConstraint> implementation, String name) { 106 iPattern = pattern; iImplementation = implementation; iName = name; 107 } 108 109 public String getPattern() { return iPattern; } 110 111 public String getName() { return iName.replaceAll("(?<=[^A-Z])([A-Z])"," $1"); } 112 113 public FlexibleConstraint create(Long id, String owner, String preference, String reference) throws IllegalArgumentException { 114 try { 115 return iImplementation.getConstructor(Long.class, String.class, String.class, String.class).newInstance(id, owner, preference, reference); 116 } catch (IllegalArgumentException e) { 117 throw e; 118 } catch (Exception e) { 119 throw new IllegalArgumentException(e.getMessage(), e); 120 } 121 } 122 } 123 124 /** 125 * Constructor 126 * @param id unique id 127 * @param owner identifier of distribution preference the constraint was created for 128 * @param preference time preference ("R" for required, "P" for prohibited, "-2", 129 * "-1", "1", "2" for soft preference) 130 * @param reference parameters of the constraint in String form 131 */ 132 public FlexibleConstraint(Long id, String owner, String preference, String reference){ 133 super(); 134 iId = id; 135 iReference = reference; 136 iPreference = Constants.preference2preferenceLevel(preference); 137 iIsRequired = preference.equals(Constants.sPreferenceRequired); 138 iOwner = owner; 139 } 140 141 142 /** 143 * Return current number of violations. 144 * @param assignment current assignment 145 * @param conflicts conflicting placements to be unassigned 146 * @param assignments assigned placements 147 * @return the number of violations of the constraint during days and all weeks of the semester 148 */ 149 public abstract double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments); 150 151 152 /** 153 * Return weeks of the term. 154 * @return a list of bitsets (one for each week of the term) representing datePatterns or null if semester is whole semester is considered 155 */ 156 public List<BitSet> getWeeks(){ 157 if (iWeeks == null){ 158 TimetableModel model = (TimetableModel) getModel(); 159 iWeeks = new ArrayList<BitSet>(); 160 161 boolean checkWeeks = model.getProperties().getPropertyBoolean("FlexibleConstraint.CheckWeeks", false); 162 163 if (checkWeeks) { 164 // get weeks method returns bitsets representing weeks during semester 165 iWeeks = model.getWeeks(); 166 } else { 167 // weeks are not considered, all placements are taken into consideration 168 iWeeks.add(null); 169 } 170 } 171 172 return iWeeks; 173 } 174 175 public int getDayOfWeekOffset() { 176 if (iDayOfWeekOffset == null) { 177 TimetableModel model = (TimetableModel) getModel(); 178 iDayOfWeekOffset = model.getProperties().getPropertyInt("DatePattern.DayOfWeekOffset", 0); 179 } 180 return iDayOfWeekOffset; 181 } 182 183 public boolean isPreciseDateComputation() { 184 if (iPreciseDateComputation == null) { 185 TimetableModel model = (TimetableModel) getModel(); 186 iPreciseDateComputation = model.getProperties().getPropertyBoolean("FlexibleConstraint.PreciseDateComputation", false); 187 } 188 return iPreciseDateComputation; 189 } 190 191 @Override 192 public boolean isConsistent(Placement value1, Placement value2) { 193 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 194 if (value1 != null) 195 assignments.put(value1.variable(), value1); 196 if (value2 != null) 197 assignments.put(value2.variable(), value2); 198 199 if (getNrViolations(null, null, assignments) != 0) return false; 200 201 return super.isConsistent(value1, value2); 202 } 203 204 /** 205 * Returns placements of variables assigned to this constraint with assignment which satisfy following conditions: 206 * They must be taught in the day included in dayCode. 207 * They cannot be included in conflicts 208 * Their date pattern intersects with week 209 * 210 * @param assignment current assignment 211 * @param dayCode representation of days in week combination 212 * @param conflicts placements to be unassigned 213 * @param value placement to be assigned 214 * @param assignments placements of variables 215 * @param week bitset representing a date pattern 216 * @return placements of variables assigned to this constraint with assignment which satisfy conditions above 217 */ 218 protected Set<Placement> getRelevantPlacements(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, 219 HashMap<Lecture, Placement> assignments, BitSet week) { 220 Set<Placement> placements = new HashSet<Placement>(); 221 222 for (Lecture lecture : variables()) { 223 // lecture of the value is already assigned 224 if(value != null && lecture.equals(value.variable()))continue; 225 226 // lecture might not have assignment if it is present in assignments 227 if (assignments != null && assignments.containsKey(lecture)) { 228 Placement placement = assignments.get(lecture); 229 if (placement != null && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode)) 230 placements.add(placement); 231 } else if (assignment != null) { 232 Placement placement = assignment.getValue(lecture); 233 if (placement != null && (conflicts == null || !conflicts.contains(placement)) && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode)) 234 placements.add(placement); 235 } 236 } 237 238 if (value == null || (conflicts != null && conflicts.contains(value))) { 239 return placements; 240 } 241 242 if (shareWeeksAndDay(value.getTimeLocation(), week, dayCode)) placements.add(value); 243 244 return placements; 245 } 246 247 /** 248 * Used to determine the daycode and week of a timelocation 249 * 250 * @param t timelocation 251 * @param week date pattern compared to timelocation 252 * @param dayCode days compared to timelocation 253 * @return true if TimeLocation matches the date pattern and days 254 */ 255 protected boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){ 256 if (isPreciseDateComputation()) return t.overlaps(dayCode, week, dayCode); 257 258 boolean matchDay = (t.getDayCode() & dayCode) != 0; 259 boolean matchWeek = (week == null || t.shareWeeks(week)); 260 return matchDay && matchWeek; 261 } 262 263 /** 264 * Creates a list of blocks from a placements sorted by startSlot 265 * 266 * @param sorted list of placements sorted by startSlot 267 * @param maxBreakBetweenBTB maximum number of free slots between BTB placements 268 * @return groups of BTB placements as a list of blocks 269 */ 270 protected List<Block> mergeToBlocks(List<Placement> sorted, int maxBreakBetweenBTB){ 271 List<Block> blocks = new ArrayList<Block>(); 272 // add placements to blocks 273 for (int i = 0; i < sorted.size(); i++) { 274 Placement placement = sorted.get(i); 275 boolean added = false; 276 // add placement to a suitable block 277 for (int j = 0; j < blocks.size(); j++) { 278 if (blocks.get(j).addPlacement(placement)) { 279 added = true; 280 } 281 } 282 // create a new block if a lecture does not fit into any block 283 if (!added) { 284 Block block = new Block(maxBreakBetweenBTB); 285 block.addPlacement(placement); 286 blocks.add(block); 287 } 288 } 289 return blocks; 290 } 291 292 @Override 293 public boolean isHard() { 294 return iIsRequired; 295 } 296 297 @Override 298 public String getName() { 299 return iOwner + ": " + iConstraintType.getName(); 300 } 301 302 public FlexibleConstraintType getType(){ 303 return iConstraintType; 304 } 305 306 public String getReference() { 307 return iReference; 308 } 309 310 public String getOwner() { 311 return iOwner; 312 } 313 314 /** 315 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for 316 * preference 317 * @return prolog preference 318 */ 319 public String getPrologPreference() { 320 return Constants.preferenceLevel2preference(iPreference); 321 } 322 323 /** 324 * Return the current preference of the flexible constraint, considering conflicts and new assignments. 325 * Used to compute value for flexible constraint criterion. 326 * @param assignment current assignment 327 * @param conflicts conflicting assignment 328 * @param assignments proposed assignments 329 * @return the current preference of the flexible constraint 330 */ 331 public double getCurrentPreference(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){ 332 if (isHard()) return 0; 333 double pref = getNrViolations(assignment, conflicts, assignments); 334 if(pref == 0){ 335 return - Math.abs(iPreference); 336 } 337 return Math.abs(iPreference) * pref; 338 } 339 340 /** 341 * A block is a list of placements sorted by startSlot, which are BTB. 342 * maxSlotsBetweenBackToBack determines the number of free slots between two BTB placements 343 * 344 */ 345 public class Block { 346 347 // start slot of the block 348 private int startSlotCurrentBlock = -1; 349 // end slot of the block 350 private int endSlotCurrentBlock = -1; 351 // max number of slots between classes to be considered Back-To-Back; 4 slots default 352 private int maxSlotsBetweenBackToBack = 4; 353 // the list of placements of this block 354 private List<Placement> placements = new ArrayList<Placement>(); 355 356 public Block(int maxSlotsBetweenBTB){ 357 this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB; 358 } 359 360 /** 361 * Adds placement to the block and updates block's attributes. 362 * 363 * @param placement placement to be added to the block 364 * @return true if the placement was successfully added to the block 365 */ 366 public boolean addPlacement(Placement placement){ 367 if (placement == null){ 368 return false; 369 } 370 371 TimeLocation t = placement.getTimeLocation(); 372 373 if (t == null){ 374 return false; 375 } 376 377 // if placements is empty, the block only contains currently added placement -> set start and end 378 if (placements.isEmpty()){ 379 placements.add(placement); 380 startSlotCurrentBlock = t.getStartSlot(); 381 endSlotCurrentBlock = t.getStartSlot() + t.getLength(); 382 return true; 383 } 384 385 // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock 386 if (t.getStartSlot() == startSlotCurrentBlock){ 387 placements.add(placement); 388 int tEnd = t.getStartSlot() + t.getLength(); 389 if (tEnd > endSlotCurrentBlock){ 390 endSlotCurrentBlock = tEnd; 391 } 392 return true; 393 } 394 395 // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement 396 if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){ 397 placements.add(placement); 398 int tEnd = t.getStartSlot() + t.getLength(); 399 if (tEnd > endSlotCurrentBlock){ 400 endSlotCurrentBlock = tEnd; 401 } 402 return true; 403 } 404 405 return false; 406 } 407 408 public boolean haveSameStartTime() { 409 if (!placements.isEmpty()) { 410 int startSlot = placements.get(0).getTimeLocation().getStartSlot(); 411 for (Placement p : getPlacements()) { 412 if (p.getTimeLocation().getStartSlot() != startSlot) 413 return false; 414 } 415 } 416 return true; 417 } 418 419 public int getStartSlotCurrentBlock(){ 420 return startSlotCurrentBlock; 421 } 422 423 public int getEndSlotCurrentBlock(){ 424 return endSlotCurrentBlock; 425 } 426 427 public int getNbrPlacements(){ 428 return placements.size(); 429 } 430 431 public List<Placement> getPlacements(){ 432 return placements; 433 } 434 435 public int getLengthInSlots(){ 436 return endSlotCurrentBlock - startSlotCurrentBlock; 437 } 438 439 @Override 440 public String toString(){ 441 return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements(); 442 } 443 } 444 445 /** 446 * Placement comparator: earlier placement first, shorter placement first if both start at the same time. 447 */ 448 protected static class PlacementTimeComparator implements Comparator<Placement> { 449 @Override 450 public int compare(Placement p1, Placement p2) { 451 TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation(); 452 // compare by start time (earlier first) 453 if (t1.getStartSlot() < t2.getStartSlot()) 454 return -1; 455 if (t1.getStartSlot() > t2.getStartSlot()) 456 return 1; 457 // same start -> compare by length (shorter first) 458 if (t1.getLength() < t2.getLength()) 459 return -1; 460 if (t1.getLength() > t2.getLength()) 461 return 1; 462 // fallback 463 return 0; 464 } 465 } 466 467 @Override 468 public String toString() { 469 return getName(); 470 } 471 472 @Override 473 public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 474 return new FlexibleConstraintContext(assignment); 475 } 476 477 public class FlexibleConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 478 protected double iLastPreference = 0; 479 480 FlexibleConstraintContext() {} 481 482 FlexibleConstraintContext(Assignment<Lecture, Placement> assignment) { 483 updateCriterion(assignment); 484 } 485 486 @Override 487 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 488 updateCriterion(assignment); 489 } 490 491 @Override 492 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 493 updateCriterion(assignment); 494 } 495 496 /** 497 * Update value of FlexibleConstraintCriterion and number of violated FlexibleConstraints 498 */ 499 protected void updateCriterion(Assignment<Lecture, Placement> assignment) { 500 if (!isHard()) { 501 Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class); 502 if (criterion != null) { 503 criterion.inc(assignment, -iLastPreference); 504 iLastPreference = getCurrentPreference(assignment, null, null); 505 criterion.inc(assignment, iLastPreference); 506 } 507 } 508 } 509 510 public double getPreference() { 511 return iLastPreference; 512 } 513 } 514}