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