001package net.sf.cpsolver.studentsct.extension; 002 003import java.util.HashMap; 004import java.util.HashSet; 005import java.util.Iterator; 006import java.util.Map; 007import java.util.Set; 008 009import org.apache.log4j.Logger; 010 011import net.sf.cpsolver.coursett.Constants; 012import net.sf.cpsolver.coursett.model.Placement; 013import net.sf.cpsolver.coursett.model.RoomLocation; 014import net.sf.cpsolver.coursett.model.TimeLocation; 015import net.sf.cpsolver.ifs.extension.Extension; 016import net.sf.cpsolver.ifs.model.ModelListener; 017import net.sf.cpsolver.ifs.solver.Solver; 018import net.sf.cpsolver.ifs.util.DataProperties; 019import net.sf.cpsolver.ifs.util.DistanceMetric; 020import net.sf.cpsolver.studentsct.StudentSectioningModel; 021import net.sf.cpsolver.studentsct.model.CourseRequest; 022import net.sf.cpsolver.studentsct.model.Enrollment; 023import net.sf.cpsolver.studentsct.model.Request; 024import net.sf.cpsolver.studentsct.model.Section; 025import net.sf.cpsolver.studentsct.model.Student; 026 027/** 028 * This extension computes student distant conflicts. Two sections that are 029 * attended by the same student are considered in a distance conflict if they 030 * are back-to-back taught in locations that are two far away. This means that 031 * the (walking) distance in minutes between the two classes are longer than 032 * the break time of the earlier class. See {@link DistanceMetric} for more details. 033 * 034 * @see TimeLocation 035 * @see Placement 036 * 037 * <br> 038 * <br> 039 * 040 * @version StudentSct 1.2 (Student Sectioning)<br> 041 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 042 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 043 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 044 * <br> 045 * This library is free software; you can redistribute it and/or modify 046 * it under the terms of the GNU Lesser General Public License as 047 * published by the Free Software Foundation; either version 3 of the 048 * License, or (at your option) any later version. <br> 049 * <br> 050 * This library is distributed in the hope that it will be useful, but 051 * WITHOUT ANY WARRANTY; without even the implied warranty of 052 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 053 * Lesser General Public License for more details. <br> 054 * <br> 055 * You should have received a copy of the GNU Lesser General Public 056 * License along with this library; if not see 057 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 058 */ 059 060public class DistanceConflict extends Extension<Request, Enrollment> implements ModelListener<Request, Enrollment> { 061 private static Logger sLog = Logger.getLogger(DistanceConflict.class); 062 private Set<Conflict> iAllConflicts = new HashSet<Conflict>(); 063 /** Debug flag */ 064 public static boolean sDebug = false; 065 private Request iOldVariable = null; 066 private Enrollment iUnassignedValue = null; 067 private DistanceMetric iDistanceMetric = null; 068 069 /** 070 * Constructor. Beside of other thigs, this constructor also uses 071 * {@link StudentSectioningModel#setDistanceConflict(DistanceConflict)} to 072 * set the this instance to the model. 073 * 074 * @param solver 075 * constraint solver 076 * @param properties 077 * configuration 078 */ 079 public DistanceConflict(Solver<Request, Enrollment> solver, DataProperties properties) { 080 super(solver, properties); 081 if (solver != null) 082 ((StudentSectioningModel) solver.currentSolution().getModel()).setDistanceConflict(this); 083 iDistanceMetric = new DistanceMetric(properties); 084 } 085 086 /** 087 * Alternative constructor (for online student sectioning) 088 * @param metrics distance metrics 089 * @param properties configuration 090 */ 091 public DistanceConflict(DistanceMetric metrics, DataProperties properties) { 092 super(null, properties); 093 iDistanceMetric = metrics; 094 } 095 096 /** 097 * Initialize extension 098 */ 099 @Override 100 public boolean init(Solver<Request, Enrollment> solver) { 101 StudentSectioningModel m = (StudentSectioningModel)solver.currentSolution().getModel(); 102 iAllConflicts = computeAllConflicts(); 103 for (Conflict c: iAllConflicts) 104 m.add(c); 105 return true; 106 } 107 108 @Override 109 public String toString() { 110 return "DistanceConstraint"; 111 } 112 113 public DistanceMetric getDistanceMetric() { 114 return iDistanceMetric; 115 } 116 117 118 private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>(); 119 protected int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) { 120 if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1); 121 if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar()) 122 return 0; 123 if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null) 124 return iDistanceMetric.getMaxTravelDistanceInMinutes(); 125 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId()); 126 if (other2distance == null) { 127 other2distance = new HashMap<Long, Integer>(); 128 iDistanceCache.put(r1.getId(), other2distance); 129 } 130 Integer distance = other2distance.get(r2.getId()); 131 if (distance == null) { 132 distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY()); 133 other2distance.put(r2.getId(), distance); 134 } 135 return distance; 136 } 137 138 protected int getDistanceInMinutes(Placement p1, Placement p2) { 139 if (p1.isMultiRoom()) { 140 if (p2.isMultiRoom()) { 141 int dist = 0; 142 for (RoomLocation r1 : p1.getRoomLocations()) { 143 for (RoomLocation r2 : p2.getRoomLocations()) { 144 dist = Math.max(dist, getDistanceInMinutes(r1, r2)); 145 } 146 } 147 return dist; 148 } else { 149 if (p2.getRoomLocation() == null) 150 return 0; 151 int dist = 0; 152 for (RoomLocation r1 : p1.getRoomLocations()) { 153 dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation())); 154 } 155 return dist; 156 } 157 } else if (p2.isMultiRoom()) { 158 if (p1.getRoomLocation() == null) 159 return 0; 160 int dist = 0; 161 for (RoomLocation r2 : p2.getRoomLocations()) { 162 dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2)); 163 } 164 return dist; 165 } else { 166 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null) 167 return 0; 168 return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation()); 169 } 170 } 171 172 /** 173 * Return true if the given two sections are in distance conflict. This 174 * means that the sections are back-to-back and that they are placed in 175 * locations that are two far. 176 * 177 * @param s1 178 * a section 179 * @param s2 180 * a section 181 * @return true, if the given sections are in a distance conflict 182 */ 183 public boolean inConflict(Section s1, Section s2) { 184 if (s1.getPlacement() == null || s2.getPlacement() == null) 185 return false; 186 TimeLocation t1 = s1.getTime(); 187 TimeLocation t2 = s2.getTime(); 188 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 189 return false; 190 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 191 if (getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 192 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 193 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 194 if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength())) 195 return true; 196 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 197 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 198 if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength())) 199 return true; 200 } 201 } else { 202 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 203 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 204 if (dist > t1.getBreakTime()) 205 return true; 206 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 207 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 208 if (dist > t2.getBreakTime()) 209 return true; 210 } 211 } 212 return false; 213 } 214 215 /** 216 * Return number of distance conflict of a (course) enrollment. It is the 217 * number of pairs of assignments of the enrollment that are in a distance 218 * conflict. 219 * 220 * @param e1 221 * an enrollment 222 * @return number of distance conflicts 223 */ 224 public int nrConflicts(Enrollment e1) { 225 if (!e1.isCourseRequest()) 226 return 0; 227 int cnt = 0; 228 for (Section s1 : e1.getSections()) { 229 for (Section s2 : e1.getSections()) { 230 if (s1.getId() < s2.getId() && inConflict(s1, s2)) 231 cnt ++; 232 } 233 } 234 return cnt; 235 } 236 237 /** 238 * Return number of distance conflicts that are between two enrollments. It 239 * is the number of pairs of assignments of these enrollments that are in a 240 * distance conflict. 241 * 242 * @param e1 243 * an enrollment 244 * @param e2 245 * an enrollment 246 * @return number of distance conflict between given enrollments 247 */ 248 public int nrConflicts(Enrollment e1, Enrollment e2) { 249 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent())) 250 return 0; 251 int cnt = 0; 252 for (Section s1 : e1.getSections()) { 253 for (Section s2 : e2.getSections()) { 254 if (inConflict(s1, s2)) 255 cnt ++; 256 } 257 } 258 return cnt; 259 } 260 261 /** 262 * Return a set of distance conflicts ({@link Conflict} objects) of a 263 * (course) enrollment. 264 * 265 * @param e1 266 * an enrollment 267 * @return list of distance conflicts that are between assignment of the 268 * given enrollment 269 */ 270 public Set<Conflict> conflicts(Enrollment e1) { 271 Set<Conflict> ret = new HashSet<Conflict>(); 272 if (!e1.isCourseRequest()) 273 return ret; 274 for (Section s1 : e1.getSections()) { 275 for (Section s2 : e1.getSections()) { 276 if (s1.getId() < s2.getId() && inConflict(s1, s2)) 277 ret.add(new Conflict(e1.getStudent(), e1, s1, e1, s2)); 278 } 279 } 280 return ret; 281 } 282 283 /** 284 * Return a set of distance conflicts ({@link Conflict} objects) between 285 * given (course) enrollments. 286 * 287 * @param e1 288 * an enrollment 289 * @param e2 290 * an enrollment 291 * @return list of distance conflicts that are between assignment of the 292 * given enrollments 293 */ 294 public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) { 295 Set<Conflict> ret = new HashSet<Conflict>(); 296 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent())) 297 return ret; 298 for (Section s1 : e1.getSections()) { 299 for (Section s2 : e2.getSections()) { 300 if (inConflict(s1, s2)) 301 ret.add(new Conflict(e1.getStudent(), e1, s1, e2, s2)); 302 } 303 } 304 return ret; 305 } 306 307 /** 308 * Total sum of all conflict of the given enrollment and other enrollments 309 * that are assignmed to the same student. 310 */ 311 public int nrAllConflicts(Enrollment enrollment) { 312 if (!enrollment.isCourseRequest()) 313 return 0; 314 int cnt = nrConflicts(enrollment); 315 for (Request request : enrollment.getStudent().getRequests()) { 316 if (request.equals(enrollment.getRequest()) || request.getAssignment() == null 317 || request.equals(iOldVariable)) 318 continue; 319 cnt += nrConflicts(enrollment, request.getAssignment()); 320 } 321 return cnt; 322 } 323 324 /** 325 * The set of all conflicts ({@link Conflict} objects) of the given 326 * enrollment and other enrollments that are assignmed to the same student. 327 */ 328 public Set<Conflict> allConflicts(Enrollment enrollment) { 329 Set<Conflict> ret = conflicts(enrollment); 330 if (!enrollment.isCourseRequest()) 331 return ret; 332 for (Request request : enrollment.getStudent().getRequests()) { 333 if (request.equals(enrollment.getRequest()) || request.getAssignment() == null) 334 continue; 335 ret.addAll(conflicts(enrollment, request.getAssignment())); 336 } 337 return ret; 338 } 339 340 /** 341 * Called when a value is assigned to a variable. Internal number of 342 * distance conflicts is updated, see 343 * {@link DistanceConflict#getTotalNrConflicts()}. 344 */ 345 public void assigned(long iteration, Enrollment value) { 346 StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel(); 347 for (Conflict c: allConflicts(value)) { 348 if (iAllConflicts.add(c)) 349 m.add(c); 350 } 351 if (sDebug) { 352 sLog.debug("A:" + value.variable() + " := " + value); 353 int inc = nrConflicts(value); 354 if (inc != 0) { 355 sLog.debug("-- DC+" + inc + " A: " + value.variable() + " := " + value); 356 for (Iterator<Conflict> i = allConflicts(value).iterator(); i.hasNext();) 357 sLog.debug(" -- " + i.next()); 358 } 359 } 360 } 361 362 /** 363 * Called when a value is unassigned from a variable. Internal number of 364 * distance conflicts is updated, see 365 * {@link DistanceConflict#getTotalNrConflicts()}. 366 */ 367 public void unassigned(long iteration, Enrollment value) { 368 if (value.variable().equals(iOldVariable)) 369 return; 370 StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel(); 371 for (Conflict c: allConflicts(value)) { 372 if (iAllConflicts.remove(c)) 373 m.remove(c); 374 } 375 if (sDebug) { 376 sLog.debug("U:" + value.variable() + " := " + value); 377 int dec = nrAllConflicts(value); 378 if (dec != 0) { 379 sLog.debug("-- DC+" + dec + " U: " + value.variable() + " := " + value); 380 Set<Conflict> confs = allConflicts(value); 381 for (Iterator<Conflict> i = confs.iterator(); i.hasNext();) 382 sLog.debug(" -- " + i.next()); 383 } 384 } 385 } 386 387 /** Checks the counter counting all conflicts */ 388 public void checkAllConflicts() { 389 Set<Conflict> allConfs = computeAllConflicts(); 390 if (iAllConflicts.size() != allConfs.size()) { 391 sLog.error("Different number of conflicts " + iAllConflicts.size() + "!=" + allConfs.size()); 392 for (Iterator<Conflict> i = allConfs.iterator(); i.hasNext();) { 393 Conflict c = i.next(); 394 if (!iAllConflicts.contains(c)) 395 sLog.debug(" +add+ " + c); 396 } 397 for (Iterator<Conflict> i = iAllConflicts.iterator(); i.hasNext();) { 398 Conflict c = i.next(); 399 if (!allConfs.contains(c)) 400 sLog.debug(" -rem- " + c); 401 } 402 iAllConflicts = allConfs; 403 } 404 } 405 /** Actual number of all distance conflicts */ 406 public int getTotalNrConflicts() { 407 return iAllConflicts.size(); 408 } 409 410 /** 411 * Compute the actual number of all distance conflicts. Should be equal to 412 * {@link DistanceConflict#getTotalNrConflicts()}. 413 */ 414 public int countTotalNrConflicts() { 415 int total = 0; 416 for (Request r1 : getModel().variables()) { 417 if (r1.getAssignment() == null || !(r1 instanceof CourseRequest)) 418 continue; 419 total += nrConflicts(r1.getAssignment()); 420 for (Request r2 : r1.getStudent().getRequests()) { 421 if (r2.getAssignment() == null || r1.getId() >= r2.getId() || !(r2 instanceof CourseRequest)) 422 continue; 423 total += nrConflicts(r1.getAssignment(), r2.getAssignment()); 424 } 425 } 426 return total; 427 } 428 429 /** 430 * Compute a set of all distance conflicts ({@link Conflict} objects). 431 */ 432 public Set<Conflict> computeAllConflicts() { 433 Set<Conflict> ret = new HashSet<Conflict>(); 434 for (Request r1 : getModel().variables()) { 435 if (r1.getAssignment() == null || !(r1 instanceof CourseRequest)) 436 continue; 437 ret.addAll(conflicts(r1.getAssignment())); 438 for (Request r2 : r1.getStudent().getRequests()) { 439 if (r2.getAssignment() == null || r1.getId() >= r2.getId() || !(r2 instanceof CourseRequest)) 440 continue; 441 ret.addAll(conflicts(r1.getAssignment(), r2.getAssignment())); 442 } 443 } 444 return ret; 445 } 446 447 /** 448 * Return a set of all distance conflicts ({@link Conflict} objects). 449 */ 450 public Set<Conflict> getAllConflicts() { 451 return iAllConflicts; 452 } 453 454 /** 455 * Called before a value is assigned to a variable. 456 */ 457 @Override 458 public void beforeAssigned(long iteration, Enrollment value) { 459 if (value != null) { 460 if (value.variable().getAssignment() != null) { 461 unassigned(iteration, value.variable().getAssignment()); 462 iUnassignedValue = value.variable().getAssignment(); 463 } 464 iOldVariable = value.variable(); 465 } 466 } 467 468 /** 469 * Called after a value is assigned to a variable. 470 */ 471 @Override 472 public void afterAssigned(long iteration, Enrollment value) { 473 iOldVariable = null; 474 iUnassignedValue = null; 475 if (value != null) 476 assigned(iteration, value); 477 } 478 479 /** 480 * Called after a value is unassigned from a variable. 481 */ 482 @Override 483 public void afterUnassigned(long iteration, Enrollment value) { 484 if (value != null && !value.equals(iUnassignedValue)) 485 unassigned(iteration, value); 486 } 487 488 /** A representation of a distance conflict */ 489 public static class Conflict { 490 private Student iStudent; 491 private Section iS1, iS2; 492 private Enrollment iE1, iE2; 493 private int iHashCode; 494 495 /** 496 * Constructor 497 * 498 * @param student 499 * related student 500 * @param s1 501 * first conflicting section 502 * @param s2 503 * second conflicting section 504 */ 505 public Conflict(Student student, Enrollment e1, Section s1, Enrollment e2, Section s2) { 506 iStudent = student; 507 if (s1.getId() < s2.getId()) { 508 iS1 = s1; 509 iS2 = s2; 510 iE1 = e1; 511 iE2 = e2; 512 } else { 513 iS1 = s2; 514 iS2 = s1; 515 iE1 = e2; 516 iE2 = e1; 517 } 518 iHashCode = (iStudent.getId() + ":" + iS1.getId() + ":" + iS2.getId()).hashCode(); 519 } 520 521 /** Related student */ 522 public Student getStudent() { 523 return iStudent; 524 } 525 526 /** First section */ 527 public Section getS1() { 528 return iS1; 529 } 530 531 /** Second section */ 532 public Section getS2() { 533 return iS2; 534 } 535 536 /** First request */ 537 public Request getR1() { 538 return iE1.getRequest(); 539 } 540 541 /** Second request */ 542 public Request getR2() { 543 return iE2.getRequest(); 544 } 545 546 /** First enrollment */ 547 public Enrollment getE1() { 548 return iE1; 549 } 550 551 /** Second enrollment */ 552 public Enrollment getE2() { 553 return iE2; 554 } 555 556 @Override 557 public int hashCode() { 558 return iHashCode; 559 } 560 561 /** The distance between conflicting sections */ 562 public double getDistance(DistanceMetric dm) { 563 return Placement.getDistanceInMeters(dm, getS1().getPlacement(), getS2().getPlacement()); 564 } 565 566 @Override 567 public boolean equals(Object o) { 568 if (o == null || !(o instanceof Conflict)) return false; 569 Conflict c = (Conflict) o; 570 return getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2()); 571 } 572 573 @Override 574 public String toString() { 575 return getStudent() + ": " + getS1() + " -- " + getS2(); 576 } 577 } 578}