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