001package net.sf.cpsolver.studentsct; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Comparator; 007import java.util.HashSet; 008import java.util.List; 009import java.util.Map; 010import java.util.Set; 011import java.util.TreeSet; 012 013import net.sf.cpsolver.ifs.model.Constraint; 014import net.sf.cpsolver.ifs.model.ConstraintListener; 015import net.sf.cpsolver.ifs.model.Model; 016import net.sf.cpsolver.ifs.util.DataProperties; 017import net.sf.cpsolver.studentsct.constraint.ConfigLimit; 018import net.sf.cpsolver.studentsct.constraint.CourseLimit; 019import net.sf.cpsolver.studentsct.constraint.LinkedSections; 020import net.sf.cpsolver.studentsct.constraint.RequiredReservation; 021import net.sf.cpsolver.studentsct.constraint.ReservationLimit; 022import net.sf.cpsolver.studentsct.constraint.SectionLimit; 023import net.sf.cpsolver.studentsct.constraint.StudentConflict; 024import net.sf.cpsolver.studentsct.extension.DistanceConflict; 025import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter; 026import net.sf.cpsolver.studentsct.model.Config; 027import net.sf.cpsolver.studentsct.model.Course; 028import net.sf.cpsolver.studentsct.model.CourseRequest; 029import net.sf.cpsolver.studentsct.model.Enrollment; 030import net.sf.cpsolver.studentsct.model.Offering; 031import net.sf.cpsolver.studentsct.model.Request; 032import net.sf.cpsolver.studentsct.model.Section; 033import net.sf.cpsolver.studentsct.model.Student; 034import net.sf.cpsolver.studentsct.model.Subpart; 035import net.sf.cpsolver.studentsct.reservation.Reservation; 036import net.sf.cpsolver.studentsct.weights.PriorityStudentWeights; 037import net.sf.cpsolver.studentsct.weights.StudentWeights; 038 039import org.apache.log4j.Logger; 040 041/** 042 * Student sectioning model. 043 * 044 * <br> 045 * <br> 046 * 047 * @version StudentSct 1.2 (Student Sectioning)<br> 048 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 049 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 050 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 051 * <br> 052 * This library is free software; you can redistribute it and/or modify 053 * it under the terms of the GNU Lesser General Public License as 054 * published by the Free Software Foundation; either version 3 of the 055 * License, or (at your option) any later version. <br> 056 * <br> 057 * This library is distributed in the hope that it will be useful, but 058 * WITHOUT ANY WARRANTY; without even the implied warranty of 059 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 060 * Lesser General Public License for more details. <br> 061 * <br> 062 * You should have received a copy of the GNU Lesser General Public 063 * License along with this library; if not see 064 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 065 */ 066public class StudentSectioningModel extends Model<Request, Enrollment> { 067 private static Logger sLog = Logger.getLogger(StudentSectioningModel.class); 068 protected static DecimalFormat sDecimalFormat = new DecimalFormat("0.000"); 069 private List<Student> iStudents = new ArrayList<Student>(); 070 private List<Offering> iOfferings = new ArrayList<Offering>(); 071 private List<LinkedSections> iLinkedSections = new ArrayList<LinkedSections>(); 072 private Set<Student> iCompleteStudents = new java.util.HashSet<Student>(); 073 private double iTotalValue = 0.0; 074 private DataProperties iProperties; 075 private DistanceConflict iDistanceConflict = null; 076 private TimeOverlapsCounter iTimeOverlaps = null; 077 private int iNrDummyStudents = 0, iNrDummyRequests = 0, iNrAssignedDummyRequests = 0, iNrCompleteDummyStudents = 0; 078 private double iTotalDummyWeight = 0.0; 079 private double iTotalCRWeight = 0.0, iTotalDummyCRWeight = 0.0, iAssignedCRWeight = 0.0, iAssignedDummyCRWeight = 0.0; 080 private double iReservedSpace = 0.0, iTotalReservedSpace = 0.0; 081 private StudentWeights iStudentWeights = null; 082 private boolean iReservationCanAssignOverTheLimit; 083 protected double iProjectedStudentWeight = 0.0100; 084 private int iMaxDomainSize = -1; 085 086 087 /** 088 * Constructor 089 * 090 * @param properties 091 * configuration 092 */ 093 @SuppressWarnings("unchecked") 094 public StudentSectioningModel(DataProperties properties) { 095 super(); 096 iReservationCanAssignOverTheLimit = properties.getPropertyBoolean("Reservation.CanAssignOverTheLimit", false); 097 iAssignedVariables = new HashSet<Request>(); 098 iUnassignedVariables = new HashSet<Request>(); 099 iPerturbVariables = new HashSet<Request>(); 100 iStudentWeights = new PriorityStudentWeights(properties); 101 iMaxDomainSize = properties.getPropertyInt("Sectioning.MaxDomainSize", iMaxDomainSize); 102 if (properties.getPropertyBoolean("Sectioning.SectionLimit", true)) { 103 SectionLimit sectionLimit = new SectionLimit(properties); 104 addGlobalConstraint(sectionLimit); 105 if (properties.getPropertyBoolean("Sectioning.SectionLimit.Debug", false)) { 106 sectionLimit.addConstraintListener(new ConstraintListener<Enrollment>() { 107 @Override 108 public void constraintBeforeAssigned(long iteration, Constraint<?, Enrollment> constraint, 109 Enrollment enrollment, Set<Enrollment> unassigned) { 110 if (enrollment.getStudent().isDummy()) 111 for (Enrollment conflict : unassigned) { 112 if (!conflict.getStudent().isDummy()) { 113 sLog.warn("Enrolment of a real student " + conflict.getStudent() + " is unassigned " 114 + "\n -- " + conflict + "\ndue to an enrollment of a dummy student " 115 + enrollment.getStudent() + " " + "\n -- " + enrollment); 116 } 117 } 118 } 119 120 @Override 121 public void constraintAfterAssigned(long iteration, Constraint<?, Enrollment> constraint, 122 Enrollment assigned, Set<Enrollment> unassigned) { 123 } 124 }); 125 } 126 } 127 if (properties.getPropertyBoolean("Sectioning.ConfigLimit", true)) { 128 ConfigLimit configLimit = new ConfigLimit(properties); 129 addGlobalConstraint(configLimit); 130 } 131 if (properties.getPropertyBoolean("Sectioning.CourseLimit", true)) { 132 CourseLimit courseLimit = new CourseLimit(properties); 133 addGlobalConstraint(courseLimit); 134 } 135 if (properties.getPropertyBoolean("Sectioning.ReservationLimit", true)) { 136 ReservationLimit reservationLimit = new ReservationLimit(properties); 137 addGlobalConstraint(reservationLimit); 138 } 139 if (properties.getPropertyBoolean("Sectioning.RequiredReservations", true)) { 140 RequiredReservation requiredReservation = new RequiredReservation(); 141 addGlobalConstraint(requiredReservation); 142 } 143 try { 144 Class<StudentWeights> studentWeightsClass = (Class<StudentWeights>)Class.forName(properties.getProperty("StudentWeights.Class", PriorityStudentWeights.class.getName())); 145 iStudentWeights = studentWeightsClass.getConstructor(DataProperties.class).newInstance(properties); 146 } catch (Exception e) { 147 sLog.error("Unable to create custom student weighting model (" + e.getMessage() + "), using default.", e); 148 iStudentWeights = new PriorityStudentWeights(properties); 149 } 150 iProjectedStudentWeight = properties.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight); 151 iProperties = properties; 152 } 153 154 /** 155 * Return true if reservation that has {@link Reservation#canAssignOverLimit()} can assign enrollments over the limit 156 */ 157 public boolean getReservationCanAssignOverTheLimit() { 158 return iReservationCanAssignOverTheLimit; 159 } 160 161 /** 162 * Return student weighting model 163 */ 164 public StudentWeights getStudentWeights() { 165 return iStudentWeights; 166 } 167 168 /** 169 * Set student weighting model 170 */ 171 public void setStudentWeights(StudentWeights weights) { 172 iStudentWeights = weights; 173 } 174 175 /** 176 * Students 177 */ 178 public List<Student> getStudents() { 179 return iStudents; 180 } 181 182 /** 183 * Students with complete schedules (see {@link Student#isComplete()}) 184 */ 185 public Set<Student> getCompleteStudents() { 186 return iCompleteStudents; 187 } 188 189 /** 190 * Add a student into the model 191 */ 192 public void addStudent(Student student) { 193 iStudents.add(student); 194 if (student.isDummy()) 195 iNrDummyStudents++; 196 for (Request request : student.getRequests()) 197 addVariable(request); 198 if (getProperties().getPropertyBoolean("Sectioning.StudentConflict", true)) { 199 addConstraint(new StudentConflict(student)); 200 } 201 if (student.isComplete()) 202 iCompleteStudents.add(student); 203 } 204 205 @Override 206 public void addVariable(Request request) { 207 super.addVariable(request); 208 if (request instanceof CourseRequest) 209 iTotalCRWeight += request.getWeight(); 210 if (request.getStudent().isDummy()) { 211 iNrDummyRequests++; 212 iTotalDummyWeight += request.getWeight(); 213 if (request instanceof CourseRequest) 214 iTotalDummyCRWeight += request.getWeight(); 215 } 216 } 217 218 /** 219 * Recompute cached request weights 220 */ 221 public void requestWeightsChanged() { 222 iTotalCRWeight = 0.0; 223 iTotalDummyWeight = 0.0; iTotalDummyCRWeight = 0.0; 224 iAssignedCRWeight = 0.0; 225 iAssignedDummyCRWeight = 0.0; 226 iNrDummyRequests = 0; iNrAssignedDummyRequests = 0; 227 iTotalReservedSpace = 0.0; iReservedSpace = 0.0; 228 for (Request request: variables()) { 229 boolean cr = (request instanceof CourseRequest); 230 if (cr) 231 iTotalCRWeight += request.getWeight(); 232 if (request.getStudent().isDummy()) { 233 iTotalDummyWeight += request.getWeight(); 234 iNrDummyRequests ++; 235 if (cr) 236 iTotalDummyCRWeight += request.getWeight(); 237 } 238 if (request.getAssignment() != null) { 239 if (cr) 240 iAssignedCRWeight += request.getWeight(); 241 if (request.getAssignment().getReservation() != null) 242 iReservedSpace += request.getWeight(); 243 if (cr && ((CourseRequest)request).hasReservations()) 244 iTotalReservedSpace += request.getWeight(); 245 if (request.getStudent().isDummy()) { 246 iNrAssignedDummyRequests ++; 247 if (cr) 248 iAssignedDummyCRWeight += request.getWeight(); 249 } 250 } 251 } 252 } 253 254 /** 255 * Remove a student from the model 256 */ 257 public void removeStudent(Student student) { 258 iStudents.remove(student); 259 if (student.isDummy()) 260 iNrDummyStudents--; 261 if (student.isComplete()) 262 iCompleteStudents.remove(student); 263 StudentConflict conflict = null; 264 for (Request request : student.getRequests()) { 265 for (Constraint<Request, Enrollment> c : request.constraints()) { 266 if (c instanceof StudentConflict) { 267 conflict = (StudentConflict) c; 268 break; 269 } 270 } 271 if (conflict != null) 272 conflict.removeVariable(request); 273 removeVariable(request); 274 } 275 if (conflict != null) 276 removeConstraint(conflict); 277 } 278 279 @Override 280 public void removeVariable(Request request) { 281 super.removeVariable(request); 282 if (request instanceof CourseRequest) { 283 CourseRequest cr = (CourseRequest)request; 284 for (Course course: cr.getCourses()) 285 course.getRequests().remove(request); 286 } 287 if (request.getStudent().isDummy()) { 288 iNrDummyRequests--; 289 iTotalDummyWeight -= request.getWeight(); 290 if (request instanceof CourseRequest) 291 iTotalDummyCRWeight -= request.getWeight(); 292 } 293 if (request instanceof CourseRequest) 294 iTotalCRWeight -= request.getWeight(); 295 } 296 297 298 /** 299 * List of offerings 300 */ 301 public List<Offering> getOfferings() { 302 return iOfferings; 303 } 304 305 /** 306 * Add an offering into the model 307 */ 308 public void addOffering(Offering offering) { 309 iOfferings.add(offering); 310 } 311 312 /** 313 * Link sections using {@link LinkedSections} 314 */ 315 public void addLinkedSections(Section... sections) { 316 LinkedSections constraint = new LinkedSections(sections); 317 iLinkedSections.add(constraint); 318 constraint.createConstraints(); 319 } 320 321 /** 322 * Link sections using {@link LinkedSections} 323 */ 324 public void addLinkedSections(Collection<Section> sections) { 325 LinkedSections constraint = new LinkedSections(sections); 326 iLinkedSections.add(constraint); 327 constraint.createConstraints(); 328 } 329 330 /** 331 * List of linked sections 332 */ 333 public List<LinkedSections> getLinkedSections() { 334 return iLinkedSections; 335 } 336 337 /** 338 * Number of students with complete schedule 339 */ 340 public int nrComplete() { 341 return getCompleteStudents().size(); 342 } 343 344 /** 345 * Model info 346 */ 347 @Override 348 public Map<String, String> getInfo() { 349 Map<String, String> info = super.getInfo(); 350 if (!getStudents().isEmpty()) 351 info.put("Students with complete schedule", sDoubleFormat.format(100.0 * nrComplete() / getStudents().size()) 352 + "% (" + nrComplete() + "/" + getStudents().size() + ")"); 353 if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts() != 0) 354 info.put("Student distance conflicts", String.valueOf(getDistanceConflict().getTotalNrConflicts())); 355 if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts() != 0) 356 info.put("Time overlapping conflicts", String.valueOf(getTimeOverlaps().getTotalNrConflicts())); 357 int nrLastLikeStudents = getNrLastLikeStudents(false); 358 if (nrLastLikeStudents != 0 && nrLastLikeStudents != getStudents().size()) { 359 int nrRealStudents = getStudents().size() - nrLastLikeStudents; 360 int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(false); 361 int nrRealCompleteStudents = getCompleteStudents().size() - nrLastLikeCompleteStudents; 362 if (nrLastLikeStudents > 0) 363 info.put("Projected students with complete schedule", sDecimalFormat.format(100.0 364 * nrLastLikeCompleteStudents / nrLastLikeStudents) 365 + "% (" + nrLastLikeCompleteStudents + "/" + nrLastLikeStudents + ")"); 366 if (nrRealStudents > 0) 367 info.put("Real students with complete schedule", sDecimalFormat.format(100.0 * nrRealCompleteStudents 368 / nrRealStudents) 369 + "% (" + nrRealCompleteStudents + "/" + nrRealStudents + ")"); 370 int nrLastLikeRequests = getNrLastLikeRequests(false); 371 int nrRealRequests = variables().size() - nrLastLikeRequests; 372 int nrLastLikeAssignedRequests = getNrAssignedLastLikeRequests(false); 373 int nrRealAssignedRequests = assignedVariables().size() - nrLastLikeAssignedRequests; 374 if (nrLastLikeRequests > 0) 375 info.put("Projected assigned requests", sDecimalFormat.format(100.0 * nrLastLikeAssignedRequests / nrLastLikeRequests) 376 + "% (" + nrLastLikeAssignedRequests + "/" + nrLastLikeRequests + ")"); 377 if (nrRealRequests > 0) 378 info.put("Real assigned requests", sDecimalFormat.format(100.0 * nrRealAssignedRequests / nrRealRequests) 379 + "% (" + nrRealAssignedRequests + "/" + nrRealRequests + ")"); 380 if (iTotalCRWeight > 0.0) { 381 info.put("Assigned course requests", sDecimalFormat.format(100.0 * iAssignedCRWeight / iTotalCRWeight) + "% (" + (int)Math.round(iAssignedCRWeight) + "/" + (int)Math.round(iTotalCRWeight) + ")"); 382 if (iTotalDummyCRWeight != iTotalCRWeight) { 383 if (iTotalDummyCRWeight > 0.0) 384 info.put("Projected assigned course requests", sDecimalFormat.format(100.0 * iAssignedDummyCRWeight / iTotalDummyCRWeight) + "% (" + (int)Math.round(iAssignedDummyCRWeight) + "/" + (int)Math.round(iTotalDummyCRWeight) + ")"); 385 info.put("Real assigned course requests", sDecimalFormat.format(100.0 * (iAssignedCRWeight - iAssignedDummyCRWeight) / (iTotalCRWeight - iTotalDummyCRWeight)) + 386 "% (" + (int)Math.round(iAssignedCRWeight - iAssignedDummyCRWeight) + "/" + (int)Math.round(iTotalCRWeight - iTotalDummyCRWeight) + ")"); 387 } 388 } 389 if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts() > 0) 390 info.put("Student distance conflicts", String.valueOf(getDistanceConflict().getTotalNrConflicts())); 391 if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts() > 0) 392 info.put("Time overlapping conflicts", String.valueOf(getTimeOverlaps().getTotalNrConflicts())); 393 } 394 if (iTotalReservedSpace > 0.0) 395 info.put("Reservations", sDoubleFormat.format(100.0 * iReservedSpace / iTotalReservedSpace) + "% (" + Math.round(iReservedSpace) + "/" + Math.round(iTotalReservedSpace) + ")"); 396 397 return info; 398 } 399 400 /** 401 * Overall solution value 402 */ 403 public double getTotalValue(boolean precise) { 404 if (precise) { 405 double total = 0; 406 for (Request r: assignedVariables()) 407 total += r.getWeight() * iStudentWeights.getWeight(r.getAssignment()); 408 if (iDistanceConflict != null) 409 for (DistanceConflict.Conflict c: iDistanceConflict.computeAllConflicts()) 410 total -= avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(c); 411 if (iTimeOverlaps != null) 412 for (TimeOverlapsCounter.Conflict c: iTimeOverlaps.computeAllConflicts()) { 413 total -= c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE1(), c); 414 total -= c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE2(), c); 415 } 416 return -total; 417 } 418 return iTotalValue; 419 } 420 421 /** 422 * Overall solution value 423 */ 424 @Override 425 public double getTotalValue() { 426 return iTotalValue; 427 } 428 429 430 /** 431 * Called after an enrollment was assigned to a request. The list of 432 * complete students and the overall solution value are updated. 433 */ 434 @Override 435 public void afterAssigned(long iteration, Enrollment enrollment) { 436 super.afterAssigned(iteration, enrollment); 437 Student student = enrollment.getStudent(); 438 if (student.isComplete()) 439 iCompleteStudents.add(student); 440 double value = enrollment.getRequest().getWeight() * iStudentWeights.getWeight(enrollment); 441 iTotalValue -= value; 442 enrollment.setExtra(value); 443 if (enrollment.isCourseRequest()) 444 iAssignedCRWeight += enrollment.getRequest().getWeight(); 445 if (enrollment.getReservation() != null) 446 iReservedSpace += enrollment.getRequest().getWeight(); 447 if (enrollment.isCourseRequest() && ((CourseRequest)enrollment.getRequest()).hasReservations()) 448 iTotalReservedSpace += enrollment.getRequest().getWeight(); 449 if (student.isDummy()) { 450 iNrAssignedDummyRequests++; 451 if (enrollment.isCourseRequest()) 452 iAssignedDummyCRWeight += enrollment.getRequest().getWeight(); 453 if (student.isComplete()) 454 iNrCompleteDummyStudents++; 455 } 456 } 457 458 /** 459 * Called before an enrollment was unassigned from a request. The list of 460 * complete students and the overall solution value are updated. 461 */ 462 @Override 463 public void afterUnassigned(long iteration, Enrollment enrollment) { 464 super.afterUnassigned(iteration, enrollment); 465 Student student = enrollment.getStudent(); 466 if (iCompleteStudents.contains(student) && !student.isComplete()) { 467 iCompleteStudents.remove(student); 468 if (student.isDummy()) 469 iNrCompleteDummyStudents--; 470 } 471 Double value = (Double)enrollment.getExtra(); 472 if (value == null) 473 value = enrollment.getRequest().getWeight() * iStudentWeights.getWeight(enrollment); 474 iTotalValue += value; 475 enrollment.setExtra(null); 476 if (enrollment.isCourseRequest()) 477 iAssignedCRWeight -= enrollment.getRequest().getWeight(); 478 if (enrollment.getReservation() != null) 479 iReservedSpace -= enrollment.getRequest().getWeight(); 480 if (enrollment.isCourseRequest() && ((CourseRequest)enrollment.getRequest()).hasReservations()) 481 iTotalReservedSpace -= enrollment.getRequest().getWeight(); 482 if (student.isDummy()) { 483 iNrAssignedDummyRequests--; 484 if (enrollment.isCourseRequest()) 485 iAssignedDummyCRWeight -= enrollment.getRequest().getWeight(); 486 } 487 } 488 489 /** 490 * Configuration 491 */ 492 public DataProperties getProperties() { 493 return iProperties; 494 } 495 496 /** 497 * Empty online student sectioning infos for all sections (see 498 * {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}). 499 */ 500 public void clearOnlineSectioningInfos() { 501 for (Offering offering : iOfferings) { 502 for (Config config : offering.getConfigs()) { 503 for (Subpart subpart : config.getSubparts()) { 504 for (Section section : subpart.getSections()) { 505 section.setSpaceExpected(0); 506 section.setSpaceHeld(0); 507 } 508 } 509 } 510 } 511 } 512 513 /** 514 * Compute online student sectioning infos for all sections (see 515 * {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}). 516 */ 517 public void computeOnlineSectioningInfos() { 518 clearOnlineSectioningInfos(); 519 for (Student student : getStudents()) { 520 if (!student.isDummy()) 521 continue; 522 for (Request request : student.getRequests()) { 523 if (!(request instanceof CourseRequest)) 524 continue; 525 CourseRequest courseRequest = (CourseRequest) request; 526 Enrollment enrollment = courseRequest.getAssignment(); 527 if (enrollment != null) { 528 for (Section section : enrollment.getSections()) { 529 section.setSpaceHeld(courseRequest.getWeight() + section.getSpaceHeld()); 530 } 531 } 532 List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>(); 533 int totalLimit = 0; 534 for (Enrollment enrl : courseRequest.values()) { 535 boolean overlaps = false; 536 for (Request otherRequest : student.getRequests()) { 537 if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest)) 538 continue; 539 Enrollment otherErollment = otherRequest.getAssignment(); 540 if (otherErollment == null) 541 continue; 542 if (enrl.isOverlapping(otherErollment)) { 543 overlaps = true; 544 break; 545 } 546 } 547 if (!overlaps) { 548 feasibleEnrollments.add(enrl); 549 if (totalLimit >= 0) { 550 int limit = enrl.getLimit(); 551 if (limit < 0) totalLimit = -1; 552 else totalLimit += limit; 553 } 554 } 555 } 556 double increment = courseRequest.getWeight() / (totalLimit > 0 ? totalLimit : feasibleEnrollments.size()); 557 for (Enrollment feasibleEnrollment : feasibleEnrollments) { 558 for (Section section : feasibleEnrollment.getSections()) { 559 if (totalLimit > 0) { 560 section.setSpaceExpected(section.getSpaceExpected() + increment * feasibleEnrollment.getLimit()); 561 } else { 562 section.setSpaceExpected(section.getSpaceExpected() + increment); 563 } 564 } 565 } 566 } 567 } 568 } 569 570 /** 571 * Sum of weights of all requests that are not assigned (see 572 * {@link Request#getWeight()}). 573 */ 574 public double getUnassignedRequestWeight() { 575 double weight = 0.0; 576 for (Request request : unassignedVariables()) { 577 weight += request.getWeight(); 578 } 579 return weight; 580 } 581 582 /** 583 * Sum of weights of all requests (see {@link Request#getWeight()}). 584 */ 585 public double getTotalRequestWeight() { 586 double weight = 0.0; 587 for (Request request : unassignedVariables()) { 588 weight += request.getWeight(); 589 } 590 return weight; 591 } 592 593 /** 594 * Set distance conflict extension 595 */ 596 public void setDistanceConflict(DistanceConflict dc) { 597 iDistanceConflict = dc; 598 } 599 600 /** 601 * Return distance conflict extension 602 */ 603 public DistanceConflict getDistanceConflict() { 604 return iDistanceConflict; 605 } 606 607 /** 608 * Set time overlaps extension 609 */ 610 public void setTimeOverlaps(TimeOverlapsCounter toc) { 611 iTimeOverlaps = toc; 612 } 613 614 /** 615 * Return time overlaps extension 616 */ 617 public TimeOverlapsCounter getTimeOverlaps() { 618 return iTimeOverlaps; 619 } 620 621 /** 622 * Average priority of unassigned requests (see 623 * {@link Request#getPriority()}) 624 */ 625 public double avgUnassignPriority() { 626 double totalPriority = 0.0; 627 for (Request request : unassignedVariables()) { 628 if (request.isAlternative()) 629 continue; 630 totalPriority += request.getPriority(); 631 } 632 return 1.0 + totalPriority / unassignedVariables().size(); 633 } 634 635 /** 636 * Average number of requests per student (see {@link Student#getRequests()} 637 * ) 638 */ 639 public double avgNrRequests() { 640 double totalRequests = 0.0; 641 int totalStudents = 0; 642 for (Student student : getStudents()) { 643 if (student.nrRequests() == 0) 644 continue; 645 totalRequests += student.nrRequests(); 646 totalStudents++; 647 } 648 return totalRequests / totalStudents; 649 } 650 651 /** Number of last like ({@link Student#isDummy()} equals true) students. */ 652 public int getNrLastLikeStudents(boolean precise) { 653 if (!precise) 654 return iNrDummyStudents; 655 int nrLastLikeStudents = 0; 656 for (Student student : getStudents()) { 657 if (student.isDummy()) 658 nrLastLikeStudents++; 659 } 660 return nrLastLikeStudents; 661 } 662 663 /** Number of real ({@link Student#isDummy()} equals false) students. */ 664 public int getNrRealStudents(boolean precise) { 665 if (!precise) 666 return getStudents().size() - iNrDummyStudents; 667 int nrRealStudents = 0; 668 for (Student student : getStudents()) { 669 if (!student.isDummy()) 670 nrRealStudents++; 671 } 672 return nrRealStudents; 673 } 674 675 /** 676 * Number of last like ({@link Student#isDummy()} equals true) students with 677 * a complete schedule ({@link Student#isComplete()} equals true). 678 */ 679 public int getNrCompleteLastLikeStudents(boolean precise) { 680 if (!precise) 681 return iNrCompleteDummyStudents; 682 int nrLastLikeStudents = 0; 683 for (Student student : getCompleteStudents()) { 684 if (student.isDummy()) 685 nrLastLikeStudents++; 686 } 687 return nrLastLikeStudents; 688 } 689 690 /** 691 * Number of real ({@link Student#isDummy()} equals false) students with a 692 * complete schedule ({@link Student#isComplete()} equals true). 693 */ 694 public int getNrCompleteRealStudents(boolean precise) { 695 if (!precise) 696 return getCompleteStudents().size() - iNrCompleteDummyStudents; 697 int nrRealStudents = 0; 698 for (Student student : getCompleteStudents()) { 699 if (!student.isDummy()) 700 nrRealStudents++; 701 } 702 return nrRealStudents; 703 } 704 705 /** 706 * Number of requests from projected ({@link Student#isDummy()} equals true) 707 * students. 708 */ 709 public int getNrLastLikeRequests(boolean precise) { 710 if (!precise) 711 return iNrDummyRequests; 712 int nrLastLikeRequests = 0; 713 for (Request request : variables()) { 714 if (request.getStudent().isDummy()) 715 nrLastLikeRequests++; 716 } 717 return nrLastLikeRequests; 718 } 719 720 /** 721 * Number of requests from real ({@link Student#isDummy()} equals false) 722 * students. 723 */ 724 public int getNrRealRequests(boolean precise) { 725 if (!precise) 726 return variables().size() - iNrDummyRequests; 727 int nrRealRequests = 0; 728 for (Request request : variables()) { 729 if (!request.getStudent().isDummy()) 730 nrRealRequests++; 731 } 732 return nrRealRequests; 733 } 734 735 /** 736 * Number of requests from projected ({@link Student#isDummy()} equals true) 737 * students that are assigned. 738 */ 739 public int getNrAssignedLastLikeRequests(boolean precise) { 740 if (!precise) 741 return iNrAssignedDummyRequests; 742 int nrLastLikeRequests = 0; 743 for (Request request : assignedVariables()) { 744 if (request.getStudent().isDummy()) 745 nrLastLikeRequests++; 746 } 747 return nrLastLikeRequests; 748 } 749 750 /** 751 * Number of requests from real ({@link Student#isDummy()} equals false) 752 * students that are assigned. 753 */ 754 public int getNrAssignedRealRequests(boolean precise) { 755 if (!precise) 756 return assignedVariables().size() - iNrAssignedDummyRequests; 757 int nrRealRequests = 0; 758 for (Request request : assignedVariables()) { 759 if (!request.getStudent().isDummy()) 760 nrRealRequests++; 761 } 762 return nrRealRequests; 763 } 764 765 /** 766 * Model extended info. Some more information (that is more expensive to 767 * compute) is added to an ordinary {@link Model#getInfo()}. 768 */ 769 @Override 770 public Map<String, String> getExtendedInfo() { 771 Map<String, String> info = getInfo(); 772 /* 773 int nrLastLikeStudents = getNrLastLikeStudents(true); 774 if (nrLastLikeStudents != 0 && nrLastLikeStudents != getStudents().size()) { 775 int nrRealStudents = getStudents().size() - nrLastLikeStudents; 776 int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(true); 777 int nrRealCompleteStudents = getCompleteStudents().size() - nrLastLikeCompleteStudents; 778 info.put("Projected students with complete schedule", sDecimalFormat.format(100.0 779 * nrLastLikeCompleteStudents / nrLastLikeStudents) 780 + "% (" + nrLastLikeCompleteStudents + "/" + nrLastLikeStudents + ")"); 781 info.put("Real students with complete schedule", sDecimalFormat.format(100.0 * nrRealCompleteStudents 782 / nrRealStudents) 783 + "% (" + nrRealCompleteStudents + "/" + nrRealStudents + ")"); 784 int nrLastLikeRequests = getNrLastLikeRequests(true); 785 int nrRealRequests = variables().size() - nrLastLikeRequests; 786 int nrLastLikeAssignedRequests = getNrAssignedLastLikeRequests(true); 787 int nrRealAssignedRequests = assignedVariables().size() - nrLastLikeAssignedRequests; 788 info.put("Projected assigned requests", sDecimalFormat.format(100.0 * nrLastLikeAssignedRequests 789 / nrLastLikeRequests) 790 + "% (" + nrLastLikeAssignedRequests + "/" + nrLastLikeRequests + ")"); 791 info.put("Real assigned requests", sDecimalFormat.format(100.0 * nrRealAssignedRequests / nrRealRequests) 792 + "% (" + nrRealAssignedRequests + "/" + nrRealRequests + ")"); 793 } 794 */ 795 // info.put("Average unassigned priority", sDecimalFormat.format(avgUnassignPriority())); 796 // info.put("Average number of requests", sDecimalFormat.format(avgNrRequests())); 797 798 /* 799 double total = 0; 800 for (Request r: variables()) 801 if (r.getAssignment() != null) 802 total += r.getWeight() * iStudentWeights.getWeight(r.getAssignment()); 803 */ 804 double dc = 0; 805 if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts() != 0) { 806 Set<DistanceConflict.Conflict> conf = getDistanceConflict().getAllConflicts(); 807 for (DistanceConflict.Conflict c: conf) 808 dc += avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(c); 809 if (!conf.isEmpty()) 810 info.put("Student distance conflicts", conf.size() + " (weighted: " + sDecimalFormat.format(dc) + ")"); 811 } 812 double toc = 0; 813 if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts() != 0) { 814 Set<TimeOverlapsCounter.Conflict> conf = getTimeOverlaps().getAllConflicts(); 815 int share = 0; 816 for (TimeOverlapsCounter.Conflict c: conf) { 817 toc += c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE1(), c); 818 toc += c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE2(), c); 819 share += c.getShare(); 820 } 821 if (toc != 0.0) 822 info.put("Time overlapping conflicts", share + " (average: " + sDecimalFormat.format(5.0 * share / getStudents().size()) + " min, weighted: " + sDoubleFormat.format(toc) + ")"); 823 } 824 /* 825 info.put("Overall solution value", sDecimalFormat.format(total - dc - toc) + (dc == 0.0 && toc == 0.0 ? "" : 826 " (" + (dc != 0.0 ? "distance: " + sDecimalFormat.format(dc): "") + (dc != 0.0 && toc != 0.0 ? ", " : "") + 827 (toc != 0.0 ? "overlap: " + sDecimalFormat.format(toc) : "") + ")") 828 ); 829 */ 830 831 double disbWeight = 0; 832 int disbSections = 0; 833 int disb10Sections = 0; 834 int disb10Limit = getProperties().getPropertyInt("Info.ListDisbalancedSections", 0); 835 Set<String> disb10SectionList = (disb10Limit == 0 ? null : new TreeSet<String>()); 836 for (Offering offering: getOfferings()) { 837 for (Config config: offering.getConfigs()) { 838 double enrl = config.getEnrollmentWeight(null); 839 for (Subpart subpart: config.getSubparts()) { 840 if (subpart.getSections().size() <= 1) continue; 841 if (subpart.getLimit() > 0) { 842 // sections have limits -> desired size is section limit x (total enrollment / total limit) 843 double ratio = enrl / subpart.getLimit(); 844 for (Section section: subpart.getSections()) { 845 double desired = ratio * section.getLimit(); 846 disbWeight += Math.abs(section.getEnrollmentWeight(null) - desired); 847 disbSections ++; 848 if (Math.abs(desired - section.getEnrollmentWeight(null)) >= Math.max(1.0, 0.1 * section.getLimit())) { 849 disb10Sections++; 850 if (disb10SectionList != null) 851 disb10SectionList.add(section.getSubpart().getConfig().getOffering().getName() + " " + section.getSubpart().getName() + " " + section.getName()); 852 } 853 } 854 } else { 855 // unlimited sections -> desired size is total enrollment / number of sections 856 for (Section section: subpart.getSections()) { 857 double desired = enrl / subpart.getSections().size(); 858 disbWeight += Math.abs(section.getEnrollmentWeight(null) - desired); 859 disbSections ++; 860 if (Math.abs(desired - section.getEnrollmentWeight(null)) >= Math.max(1.0, 0.1 * desired)) { 861 disb10Sections++; 862 if (disb10SectionList != null) 863 disb10SectionList.add(section.getSubpart().getConfig().getOffering().getName() + " " + section.getSubpart().getName() + " " + section.getName()); 864 } 865 } 866 } 867 } 868 } 869 } 870 if (disbSections != 0) { 871 info.put("Average disbalance", sDecimalFormat.format(disbWeight / disbSections) + 872 " (" + sDecimalFormat.format(iAssignedCRWeight == 0 ? 0.0 : 100.0 * disbWeight / iAssignedCRWeight) + "%)"); 873 String list = ""; 874 if (disb10SectionList != null) { 875 int i = 0; 876 for (String section: disb10SectionList) { 877 if (i == disb10Limit) { 878 list += "<br>..."; 879 break; 880 } 881 list += "<br>" + section; 882 i++; 883 } 884 } 885 info.put("Sections disbalanced by 10% or more", disb10Sections + " (" + sDecimalFormat.format(disbSections == 0 ? 0.0 : 100.0 * disb10Sections / disbSections) + "%)" + list); 886 } 887 return info; 888 } 889 890 @Override 891 public void restoreBest() { 892 restoreBest(new Comparator<Request>() { 893 @Override 894 public int compare(Request r1, Request r2) { 895 Enrollment e1 = r1.getBestAssignment(); 896 Enrollment e2 = r2.getBestAssignment(); 897 // Reservations first 898 if (e1.getReservation() != null && e2.getReservation() == null) return -1; 899 if (e1.getReservation() == null && e2.getReservation() != null) return 1; 900 // Then assignment iteration (i.e., order in which assignments were made) 901 if (r1.getBestAssignmentIteration() != r2.getBestAssignmentIteration()) 902 return (r1.getBestAssignmentIteration() < r2.getBestAssignmentIteration() ? -1 : 1); 903 // Then student and priority 904 return r1.compareTo(r2); 905 } 906 }); 907 } 908 909 @Override 910 public String toString() { 911 return (getNrRealStudents(false) > 0 ? "RRq:" + getNrAssignedRealRequests(false) + "/" + getNrRealRequests(false) + ", " : "") 912 + (getNrLastLikeStudents(false) > 0 ? "DRq:" + getNrAssignedLastLikeRequests(false) + "/" + getNrLastLikeRequests(false) + ", " : "") 913 + (getNrRealStudents(false) > 0 ? "RS:" + getNrCompleteRealStudents(false) + "/" + getNrRealStudents(false) + ", " : "") 914 + (getNrLastLikeStudents(false) > 0 ? "DS:" + getNrCompleteLastLikeStudents(false) + "/" + getNrLastLikeStudents(false) + ", " : "") 915 + "V:" 916 + sDecimalFormat.format(-getTotalValue()) 917 + (getDistanceConflict() == null ? "" : ", DC:" + getDistanceConflict().getTotalNrConflicts()) 918 + (getTimeOverlaps() == null ? "" : ", TOC:" + getTimeOverlaps().getTotalNrConflicts()) 919 + ", %:" + sDecimalFormat.format(-100.0 * getTotalValue() / (getStudents().size() - iNrDummyStudents + 920 (iProjectedStudentWeight < 0.0 ? iNrDummyStudents * (iTotalDummyWeight / iNrDummyRequests) :iProjectedStudentWeight * iTotalDummyWeight))); 921 922 } 923 924 /** 925 * Quadratic average of two weights. 926 */ 927 public double avg(double w1, double w2) { 928 return Math.sqrt(w1 * w2); 929 } 930 931 public void add(DistanceConflict.Conflict c) { 932 iTotalValue += avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(c); 933 } 934 935 public void remove(DistanceConflict.Conflict c) { 936 iTotalValue -= avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(c); 937 } 938 939 public void add(TimeOverlapsCounter.Conflict c) { 940 iTotalValue += c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE1(), c); 941 iTotalValue += c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE2(), c); 942 } 943 944 public void remove(TimeOverlapsCounter.Conflict c) { 945 iTotalValue -= c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE1(), c); 946 iTotalValue -= c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(c.getE2(), c); 947 } 948 949 /** 950 * Maximal domain size (i.e., number of enrollments of a course request), -1 if there is no limit. 951 */ 952 public int getMaxDomainSize() { return iMaxDomainSize; } 953 954 /** 955 * Maximal domain size (i.e., number of enrollments of a course request), -1 if there is no limit. 956 */ 957 public void setMaxDomainSize(int maxDomainSize) { iMaxDomainSize = maxDomainSize; } 958}