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