001package org.cpsolver.studentsct.online; 002 003import java.io.File; 004import java.io.FileWriter; 005import java.io.IOException; 006import java.io.PrintWriter; 007import java.text.DecimalFormat; 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.HashMap; 011import java.util.HashSet; 012import java.util.Hashtable; 013import java.util.Iterator; 014import java.util.List; 015import java.util.Map; 016import java.util.NoSuchElementException; 017import java.util.Set; 018import java.util.TreeSet; 019 020import org.apache.logging.log4j.Logger; 021import org.cpsolver.ifs.assignment.Assignment; 022import org.cpsolver.ifs.assignment.AssignmentMap; 023import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 024import org.cpsolver.ifs.solver.Solver; 025import org.cpsolver.ifs.util.DataProperties; 026import org.cpsolver.ifs.util.DistanceMetric; 027import org.cpsolver.ifs.util.JProf; 028import org.cpsolver.ifs.util.ToolBox; 029import org.cpsolver.studentsct.StudentPreferencePenalties; 030import org.cpsolver.studentsct.StudentSectioningModel; 031import org.cpsolver.studentsct.StudentSectioningXMLLoader; 032import org.cpsolver.studentsct.StudentSectioningXMLSaver; 033import org.cpsolver.studentsct.constraint.LinkedSections; 034import org.cpsolver.studentsct.extension.DistanceConflict; 035import org.cpsolver.studentsct.extension.StudentQuality; 036import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 037import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour; 038import org.cpsolver.studentsct.heuristics.studentord.StudentChoiceOrder; 039import org.cpsolver.studentsct.model.Config; 040import org.cpsolver.studentsct.model.Course; 041import org.cpsolver.studentsct.model.CourseRequest; 042import org.cpsolver.studentsct.model.Enrollment; 043import org.cpsolver.studentsct.model.FreeTimeRequest; 044import org.cpsolver.studentsct.model.Offering; 045import org.cpsolver.studentsct.model.Request; 046import org.cpsolver.studentsct.model.Section; 047import org.cpsolver.studentsct.model.Student; 048import org.cpsolver.studentsct.model.Subpart; 049import org.cpsolver.studentsct.online.expectations.AvoidUnbalancedWhenNoExpectations; 050import org.cpsolver.studentsct.online.expectations.FractionallyOverExpected; 051import org.cpsolver.studentsct.online.expectations.FractionallyUnbalancedWhenNoExpectations; 052import org.cpsolver.studentsct.online.expectations.PercentageOverExpected; 053import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection; 054import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSuggestions; 055import org.cpsolver.studentsct.online.selection.OnlineSectioningSelection; 056import org.cpsolver.studentsct.online.selection.StudentSchedulingAssistantWeights; 057import org.cpsolver.studentsct.online.selection.SuggestionSelection; 058import org.cpsolver.studentsct.online.selection.SuggestionsBranchAndBound; 059import org.cpsolver.studentsct.reservation.CourseReservation; 060import org.cpsolver.studentsct.reservation.Reservation; 061 062/** 063 * An online student sectioning test. It loads the given problem (passed as the only argument) with no assignments. It sections all 064 * students in the given order (given by -Dsort parameter, values shuffle, choice, reverse). Multiple threads can be used to section 065 * students in parallel (given by -DnrConcurrent parameter). If parameter -Dsuggestions is set to true, the test also asks for suggestions 066 * for each of the assigned class, preferring mid-day times. Over-expected criterion can be defined by the -Doverexp parameter (see the 067 * examples bellow). Multi-criteria selection can be enabled by -DStudentWeights.MultiCriteria=true and equal weighting can be set by 068 * -DStudentWeights.PriorityWeighting=equal). 069 * 070 * <br><br> 071 * Usage:<code> 072 * java -Xmx1g -cp studentsct-1.3.jar [parameters] org.cpsolver.studentsct.online.Test data/pu-sect-fal07.xml<br> 073 * </code> 074 * Parameters:<ul> 075 * <li>-Dsort=shuffle|choice|reverse ... for taking students in random order, more choices first, or more choices last (defaults to shuffle) 076 * <li>-DnrConcurrent=N ... for the number of threads (concurrent computations of student schedules, defaults to 10) 077 * <li>-Dsuggestions=true|false ... true to use suggestions (to simulate students preferring mid-day, defaults to false) 078 * <li>-Doverexp=<i>x<sub>over</sub></i>|b<i>x<sub>over</sub></i>-<i>x<sub>disb</sub></i>%|<i>x<sub>over</sub></i>-<i>x<sub>max</sub></i>|b<i>x<sub>over</sub></i>-<i>x<sub>max</sub></i>-<i>x<sub>disb</sub></i>% for over-expected criterion, examples:<ul> 079 * <li>1.1 ... {@link PercentageOverExpected} with OverExpected.Percentage set to 1.1 (<i>x<sub>over</sub></i>) 080 * <li>b1-10 ... {@link AvoidUnbalancedWhenNoExpectations} with OverExpected.Percentage set to 1 and General.BalanceUnlimited set to 10/100 (<i>x<sub>disb</sub></i>%) 081 * <li>0.85-5 ... {@link FractionallyOverExpected} with OverExpected.Percentage set to 0.85 and OverExpected.Maximum set to 5 (<i>x<sub>max</sub></i>) 082 * <li>1.1-5-1 ... {@link FractionallyUnbalancedWhenNoExpectations} with OverExpected.Percentage set to 1.1, General.BalanceUnlimited set to 5/100, and OverExpected.Maximum set to 1 083 * </ul> 084 * <li>-DStudentWeights.PriorityWeighting=priority|equal ... priority or equal weighting (defaults to priority) 085 * <li>-DStudentWeights.MultiCriteria=true|false ... true for multi-criteria (lexicographic ordering), false for a weighted sum (default to true) 086 * <li>-DNeighbour.BranchAndBoundTimeout=M ... time limit for each student in milliseconds (CPU time, defaults to 1000) 087 * </ul> 088 * 089 * @author Tomáš Müller 090 * @version StudentSct 1.3 (Student Sectioning)<br> 091 * Copyright (C) 2014 Tomáš Müller<br> 092 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 093 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 094 * <br> 095 * This library is free software; you can redistribute it and/or modify 096 * it under the terms of the GNU Lesser General Public License as 097 * published by the Free Software Foundation; either version 3 of the 098 * License, or (at your option) any later version. <br> 099 * <br> 100 * This library is distributed in the hope that it will be useful, but 101 * WITHOUT ANY WARRANTY; without even the implied warranty of 102 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 103 * Lesser General Public License for more details. <br> 104 * <br> 105 * You should have received a copy of the GNU Lesser General Public 106 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 107 * 108 */ 109public class Test { 110 public static DecimalFormat sDF = new DecimalFormat("0.00000"); 111 public static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(Test.class); 112 113 private OnlineSectioningModel iModel; 114 private Assignment<Request, Enrollment> iAssignment; 115 private boolean iSuggestions = false; 116 117 private Map<String, Counter> iCounters = new HashMap<String, Counter>(); 118 119 public Test(DataProperties config) { 120 iModel = new TestModel(config); 121 iModel.setDistanceConflict(new DistanceConflict(new DistanceMetric(iModel.getProperties()), iModel.getProperties())); 122 iModel.getDistanceConflict().register(iModel); 123 iModel.getDistanceConflict().setAssignmentContextReference(iModel.createReference(iModel.getDistanceConflict())); 124 iModel.setTimeOverlaps(new TimeOverlapsCounter(null, iModel.getProperties())); 125 iModel.getTimeOverlaps().register(iModel); 126 iModel.getTimeOverlaps().setAssignmentContextReference(iModel.createReference(iModel.getTimeOverlaps())); 127 iModel.setStudentQuality(new StudentQuality(new DistanceMetric(iModel.getProperties()), iModel.getProperties())); 128 iModel.getStudentQuality().register(iModel); 129 iModel.getStudentQuality().setAssignmentContextReference(iModel.createReference(iModel.getStudentQuality())); 130 iModel.setStudentWeights(new StudentSchedulingAssistantWeights(iModel.getProperties())); 131 iAssignment = new DefaultSingleAssignment<Request, Enrollment>(); 132 iSuggestions = "true".equals(System.getProperty("suggestions", iSuggestions ? "true" : "false")); 133 134 String overexp = System.getProperty("overexp"); 135 if (overexp != null) { 136 boolean bal = false; 137 if (overexp.startsWith("b")) { 138 bal = true; 139 overexp = overexp.substring(1); 140 } 141 String[] x = overexp.split("[/\\-]"); 142 if (x.length == 1) { 143 iModel.setOverExpectedCriterion(new PercentageOverExpected(Double.valueOf(x[0]))); 144 } else if (x.length == 2) { 145 iModel.setOverExpectedCriterion(bal ? new AvoidUnbalancedWhenNoExpectations(Double.valueOf(x[0]), Double.valueOf(x[1]) / 100.0) : 146 new FractionallyOverExpected(Double.valueOf(x[0]), Double.valueOf(x[1]))); 147 } else { 148 iModel.setOverExpectedCriterion(new FractionallyUnbalancedWhenNoExpectations(Double.valueOf(x[0]), 149 Double.valueOf(x[1]), Double.valueOf(x[2]) / 100.0)); 150 } 151 } 152 153 sLog.info("Using " + (config.getPropertyBoolean("StudentWeights.MultiCriteria", true) ? "multi-criteria " : "") 154 + (config.getPropertyBoolean("StudentWeights.PriorityWeighting", true) ? "priority" : "equal") 155 + " weighting model" + " with over-expected " + iModel.getOverExpectedCriterion() 156 + (iSuggestions ? ", suggestions" : "") + ", " + System.getProperty("sort", "shuffle") + " order" 157 + " and " + config.getPropertyInt("Neighbour.BranchAndBoundTimeout", 1000) + " ms time limit."); 158 } 159 160 public OnlineSectioningModel model() { 161 return iModel; 162 } 163 164 public Assignment<Request, Enrollment> assignment() { 165 return iAssignment; 166 } 167 168 public void inc(String name, double value) { 169 synchronized (iCounters) { 170 Counter c = iCounters.get(name); 171 if (c == null) { 172 c = new Counter(); 173 iCounters.put(name, c); 174 } 175 c.inc(value); 176 } 177 } 178 179 public void inc(String name) { 180 inc(name, 1.0); 181 } 182 183 public Counter get(String name) { 184 synchronized (iCounters) { 185 Counter c = iCounters.get(name); 186 if (c == null) { 187 c = new Counter(); 188 iCounters.put(name, c); 189 } 190 return c; 191 } 192 } 193 194 public double getPercDisbalancedSections(Assignment<Request, Enrollment> assignment, double perc) { 195 boolean balanceUnlimited = model().getProperties().getPropertyBoolean("General.BalanceUnlimited", false); 196 double disb10Sections = 0, nrSections = 0; 197 for (Offering offering : model().getOfferings()) { 198 for (Config config : offering.getConfigs()) { 199 double enrl = config.getEnrollmentTotalWeight(assignment, null); 200 for (Subpart subpart : config.getSubparts()) { 201 if (subpart.getSections().size() <= 1) 202 continue; 203 nrSections += subpart.getSections().size(); 204 if (subpart.getLimit() > 0) { 205 // sections have limits -> desired size is section limit 206 // x (total enrollment / total limit) 207 double ratio = enrl / subpart.getLimit(); 208 for (Section section : subpart.getSections()) { 209 double desired = ratio * section.getLimit(); 210 if (Math.abs(desired - section.getEnrollmentTotalWeight(assignment, null)) >= Math.max(1.0, perc * section.getLimit())) 211 disb10Sections++; 212 } 213 } else if (balanceUnlimited) { 214 // unlimited sections -> desired size is total 215 // enrollment / number of sections 216 for (Section section : subpart.getSections()) { 217 double desired = enrl / subpart.getSections().size(); 218 if (Math.abs(desired - section.getEnrollmentTotalWeight(assignment, null)) >= Math.max(1.0, perc * desired)) 219 disb10Sections++; 220 } 221 } 222 } 223 } 224 } 225 return 100.0 * disb10Sections / nrSections; 226 } 227 228 protected Course clone(Course course, long studentId, Student originalStudent, Map<Long, Section> classTable, StudentSectioningModel model) { 229 Offering clonedOffering = new Offering(course.getOffering().getId(), course.getOffering().getName()); 230 clonedOffering.setModel(model); 231 int courseLimit = course.getLimit(); 232 if (courseLimit >= 0) { 233 courseLimit -= course.getEnrollments(assignment()).size(); 234 if (courseLimit < 0) 235 courseLimit = 0; 236 for (Iterator<Enrollment> i = course.getEnrollments(assignment()).iterator(); i.hasNext();) { 237 Enrollment enrollment = i.next(); 238 if (enrollment.getStudent().getId() == studentId) { 239 courseLimit++; 240 break; 241 } 242 } 243 } 244 Course clonedCourse = new Course(course.getId(), course.getSubjectArea(), course.getCourseNumber(), 245 clonedOffering, courseLimit, course.getProjected()); 246 clonedCourse.setNote(course.getNote()); 247 clonedCourse.setType(course.getType()); 248 clonedCourse.setTitle(course.getTitle()); 249 Hashtable<Config, Config> configs = new Hashtable<Config, Config>(); 250 Hashtable<Subpart, Subpart> subparts = new Hashtable<Subpart, Subpart>(); 251 Hashtable<Section, Section> sections = new Hashtable<Section, Section>(); 252 for (Iterator<Config> e = course.getOffering().getConfigs().iterator(); e.hasNext();) { 253 Config config = e.next(); 254 int configLimit = config.getLimit(); 255 int configEnrollment = config.getEnrollments(assignment()).size(); 256 if (configLimit >= 0) { 257 configLimit -= config.getEnrollments(assignment()).size(); 258 if (configLimit < 0) 259 configLimit = 0; 260 for (Iterator<Enrollment> i = config.getEnrollments(assignment()).iterator(); i.hasNext();) { 261 Enrollment enrollment = i.next(); 262 if (enrollment.getStudent().getId() == studentId) { 263 configLimit++; 264 configEnrollment--; 265 break; 266 } 267 } 268 } 269 OnlineConfig clonedConfig = new OnlineConfig(config.getId(), configLimit, config.getName(), clonedOffering); 270 clonedConfig.setInstructionalMethodId(config.getInstructionalMethodId()); 271 clonedConfig.setInstructionalMethodName(config.getInstructionalMethodName()); 272 clonedConfig.setInstructionalMethodReference(config.getInstructionalMethodReference()); 273 clonedConfig.setEnrollment(configEnrollment); 274 configs.put(config, clonedConfig); 275 for (Iterator<Subpart> f = config.getSubparts().iterator(); f.hasNext();) { 276 Subpart subpart = f.next(); 277 Subpart clonedSubpart = new Subpart(subpart.getId(), subpart.getInstructionalType(), subpart.getName(), 278 clonedConfig, (subpart.getParent() == null ? null : subparts.get(subpart.getParent()))); 279 clonedSubpart.setAllowOverlap(subpart.isAllowOverlap()); 280 clonedSubpart.setCredit(subpart.getCredit()); 281 subparts.put(subpart, clonedSubpart); 282 for (Iterator<Section> g = subpart.getSections().iterator(); g.hasNext();) { 283 Section section = g.next(); 284 int limit = section.getLimit(); 285 int enrl = section.getEnrollments(assignment()).size(); 286 if (limit >= 0) { 287 // limited section, deduct enrollments 288 limit -= section.getEnrollments(assignment()).size(); 289 if (limit < 0) 290 limit = 0; // over-enrolled, but not unlimited 291 if (studentId >= 0) 292 for (Enrollment enrollment : section.getEnrollments(assignment())) 293 if (enrollment.getStudent().getId() == studentId) { 294 limit++; 295 enrl--; 296 break; 297 } 298 } 299 OnlineSection clonedSection = new OnlineSection(section.getId(), limit, 300 section.getName(course .getId()), clonedSubpart, section.getPlacement(), section.getInstructors(), (section.getParent() == null ? null : sections.get(section.getParent()))); 301 clonedSection.setName(-1l, section.getName(-1l)); 302 clonedSection.setNote(section.getNote()); 303 clonedSection.setSpaceExpected(section.getSpaceExpected()); 304 clonedSection.setSpaceHeld(section.getSpaceHeld()); 305 clonedSection.setEnrollment(enrl); 306 clonedSection.setCancelled(section.isCancelled()); 307 clonedSection.setEnabled(section.isEnabled()); 308 clonedSection.setPast(section.isPast()); 309 clonedSection.setOnline(section.isOnline()); 310 if (section.getIgnoreConflictWithSectionIds() != null) 311 for (Long id : section.getIgnoreConflictWithSectionIds()) 312 clonedSection.addIgnoreConflictWith(id); 313 if (limit > 0) { 314 double available = Math.round(section.getSpaceExpected() - limit); 315 clonedSection.setPenalty(available / section.getLimit()); 316 } 317 sections.put(section, clonedSection); 318 classTable.put(section.getId(), clonedSection); 319 } 320 } 321 } 322 if (course.getOffering().hasReservations()) { 323 for (Reservation reservation : course.getOffering().getReservations()) { 324 int reservationLimit = (int) Math.round(reservation.getLimit()); 325 if (reservationLimit >= 0) { 326 reservationLimit -= reservation.getEnrollments(assignment()).size(); 327 if (reservationLimit < 0) 328 reservationLimit = 0; 329 for (Iterator<Enrollment> i = reservation.getEnrollments(assignment()).iterator(); i.hasNext();) { 330 Enrollment enrollment = i.next(); 331 if (enrollment.getStudent().getId() == studentId) { 332 reservationLimit++; 333 break; 334 } 335 } 336 if (reservationLimit <= 0 && !reservation.mustBeUsed()) 337 continue; 338 } 339 boolean applicable = originalStudent != null && reservation.isApplicable(originalStudent); 340 if (reservation instanceof CourseReservation) 341 applicable = (course.getId() == ((CourseReservation) reservation).getCourse().getId()); 342 if (reservation instanceof org.cpsolver.studentsct.reservation.DummyReservation) { 343 // Ignore by reservation only flag (dummy reservation) when 344 // the student is already enrolled in the course 345 for (Enrollment enrollment : course.getEnrollments(assignment())) 346 if (enrollment.getStudent().getId() == studentId) { 347 applicable = true; 348 break; 349 } 350 } 351 Reservation clonedReservation = new OnlineReservation(0, reservation.getId(), clonedOffering, 352 reservation.getPriority(), reservation.canAssignOverLimit(), reservationLimit, applicable, 353 reservation.mustBeUsed(), reservation.isAllowOverlap(), reservation.isExpired()); 354 for (Config config : reservation.getConfigs()) 355 clonedReservation.addConfig(configs.get(config)); 356 for (Map.Entry<Subpart, Set<Section>> entry : reservation.getSections().entrySet()) { 357 Set<Section> clonedSections = new HashSet<Section>(); 358 for (Section section : entry.getValue()) 359 clonedSections.add(sections.get(section)); 360 clonedReservation.getSections().put(subparts.get(entry.getKey()), clonedSections); 361 } 362 } 363 } 364 return clonedCourse; 365 } 366 367 protected Request addRequest(Student student, Student original, Request request, Map<Long, Section> classTable, 368 StudentSectioningModel model) { 369 if (request instanceof FreeTimeRequest) { 370 return new FreeTimeRequest(student.getRequests().size() + 1, student.getRequests().size(), 371 request.isAlternative(), student, ((FreeTimeRequest) request).getTime()); 372 } else if (request instanceof CourseRequest) { 373 List<Course> courses = new ArrayList<Course>(); 374 for (Course course : ((CourseRequest) request).getCourses()) 375 courses.add(clone(course, student.getId(), original, classTable, model)); 376 CourseRequest clonnedRequest = new CourseRequest(student.getRequests().size() + 1, student.getRequests().size(), 377 request.isAlternative(), student, courses, ((CourseRequest) request).isWaitlist(), request.getRequestPriority(), null); 378 for (Request originalRequest : original.getRequests()) { 379 Enrollment originalEnrollment = assignment().getValue(originalRequest); 380 for (Course clonnedCourse : clonnedRequest.getCourses()) { 381 if (!clonnedCourse.getOffering().hasReservations()) 382 continue; 383 if (originalEnrollment != null && clonnedCourse.equals(originalEnrollment.getCourse())) { 384 boolean needReservation = clonnedCourse.getOffering().getUnreservedSpace(assignment(), clonnedRequest) < 1.0; 385 if (!needReservation) { 386 boolean configChecked = false; 387 for (Section originalSection : originalEnrollment.getSections()) { 388 Section clonnedSection = classTable.get(originalSection.getId()); 389 if (clonnedSection.getUnreservedSpace(assignment(), clonnedRequest) < 1.0) { 390 needReservation = true; 391 break; 392 } 393 if (!configChecked 394 && clonnedSection.getSubpart().getConfig() 395 .getUnreservedSpace(assignment(), clonnedRequest) < 1.0) { 396 needReservation = true; 397 break; 398 } 399 configChecked = true; 400 } 401 } 402 if (needReservation) { 403 Reservation reservation = new OnlineReservation(0, -original.getId(), 404 clonnedCourse.getOffering(), 5, false, 1, true, false, false, true); 405 for (Section originalSection : originalEnrollment.getSections()) 406 reservation.addSection(classTable.get(originalSection.getId())); 407 } 408 break; 409 } 410 } 411 } 412 return clonnedRequest; 413 } else { 414 return null; 415 } 416 } 417 418 public boolean section(Student original) { 419 OnlineSectioningModel model = new TestModel(iModel.getProperties()); 420 model.setOverExpectedCriterion(iModel.getOverExpectedCriterion()); 421 Student student = new Student(original.getId()); 422 Hashtable<CourseRequest, Set<Section>> preferredSectionsForCourse = new Hashtable<CourseRequest, Set<Section>>(); 423 Map<Long, Section> classTable = new HashMap<Long, Section>(); 424 425 synchronized (iModel) { 426 for (Request request : original.getRequests()) { 427 Request clonnedRequest = addRequest(student, original, request, classTable, model); 428 Enrollment enrollment = assignment().getValue(request); 429 if (enrollment != null && enrollment.isCourseRequest()) { 430 Set<Section> sections = new HashSet<Section>(); 431 for (Section section : enrollment.getSections()) 432 sections.add(classTable.get(section.getId())); 433 preferredSectionsForCourse.put((CourseRequest) clonnedRequest, sections); 434 } 435 } 436 } 437 438 model.addStudent(student); 439 model.setDistanceConflict(new DistanceConflict(iModel.getDistanceConflict().getDistanceMetric(), model.getProperties())); 440 model.setTimeOverlaps(new TimeOverlapsCounter(null, model.getProperties())); 441 for (LinkedSections link : iModel.getLinkedSections()) { 442 List<Section> sections = new ArrayList<Section>(); 443 for (Offering offering : link.getOfferings()) 444 for (Subpart subpart : link.getSubparts(offering)) 445 for (Section section : link.getSections(subpart)) { 446 Section x = classTable.get(section.getId()); 447 if (x != null) 448 sections.add(x); 449 } 450 if (sections.size() >= 2) 451 model.addLinkedSections(link.isMustBeUsed(), sections); 452 } 453 OnlineSectioningSelection selection = null; 454 if (model.getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true)) { 455 selection = new MultiCriteriaBranchAndBoundSelection(iModel.getProperties()); 456 } else { 457 selection = new SuggestionSelection(model.getProperties()); 458 } 459 460 selection.setModel(model); 461 selection.setPreferredSections(preferredSectionsForCourse); 462 selection.setRequiredSections(new Hashtable<CourseRequest, Set<Section>>()); 463 selection.setRequiredFreeTimes(new HashSet<FreeTimeRequest>()); 464 465 long t0 = JProf.currentTimeMillis(); 466 Assignment<Request, Enrollment> newAssignment = new AssignmentMap<Request, Enrollment>(); 467 BranchBoundNeighbour neighbour = selection.select(newAssignment, student); 468 long time = JProf.currentTimeMillis() - t0; 469 inc("[C] CPU Time", time); 470 if (neighbour == null) { 471 inc("[F] Failure"); 472 } else { 473 if (iSuggestions) { 474 StudentPreferencePenalties penalties = new StudentPreferencePenalties(StudentPreferencePenalties.sDistTypePreference); 475 double maxOverExpected = 0; 476 int assigned = 0; 477 double penalty = 0.0; 478 Hashtable<CourseRequest, Set<Section>> enrollments = new Hashtable<CourseRequest, Set<Section>>(); 479 List<RequestSectionPair> pairs = new ArrayList<RequestSectionPair>(); 480 481 for (int i = 0; i < neighbour.getAssignment().length; i++) { 482 Enrollment enrl = neighbour.getAssignment()[i]; 483 if (enrl != null && enrl.isCourseRequest() && enrl.getAssignments() != null) { 484 assigned++; 485 for (Section section : enrl.getSections()) { 486 maxOverExpected += model.getOverExpected(newAssignment, section, enrl.getRequest()); 487 pairs.add(new RequestSectionPair(enrl.variable(), section)); 488 } 489 enrollments.put((CourseRequest) enrl.variable(), enrl.getSections()); 490 penalty += penalties.getPenalty(enrl); 491 } 492 } 493 penalty /= assigned; 494 inc("[S] Initial Penalty", penalty); 495 double nrSuggestions = 0.0, nrAccepted = 0.0, totalSuggestions = 0.0, nrTries = 0.0; 496 for (int i = 0; i < pairs.size(); i++) { 497 RequestSectionPair pair = pairs.get(i); 498 SuggestionsBranchAndBound suggestionBaB = null; 499 if (model.getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true)) { 500 suggestionBaB = new MultiCriteriaBranchAndBoundSuggestions(model.getProperties(), student, 501 newAssignment, new Hashtable<CourseRequest, Set<Section>>(), 502 new HashSet<FreeTimeRequest>(), enrollments, pair.getRequest(), pair.getSection(), 503 null, maxOverExpected, iModel.getProperties().getPropertyBoolean( 504 "StudentWeights.PriorityWeighting", true)); 505 } else { 506 suggestionBaB = new SuggestionsBranchAndBound(model.getProperties(), student, newAssignment, 507 new Hashtable<CourseRequest, Set<Section>>(), new HashSet<FreeTimeRequest>(), 508 enrollments, pair.getRequest(), pair.getSection(), null, maxOverExpected); 509 } 510 511 long x0 = JProf.currentTimeMillis(); 512 TreeSet<SuggestionsBranchAndBound.Suggestion> suggestions = suggestionBaB.computeSuggestions(); 513 inc("[S] Suggestion CPU Time", JProf.currentTimeMillis() - x0); 514 totalSuggestions += suggestions.size(); 515 if (!suggestions.isEmpty()) 516 nrSuggestions += 1.0; 517 nrTries += 1.0; 518 519 SuggestionsBranchAndBound.Suggestion best = null; 520 for (SuggestionsBranchAndBound.Suggestion suggestion : suggestions) { 521 int a = 0; 522 double p = 0.0; 523 for (int j = 0; j < suggestion.getEnrollments().length; j++) { 524 Enrollment e = suggestion.getEnrollments()[j]; 525 if (e != null && e.isCourseRequest() && e.getAssignments() != null) { 526 p += penalties.getPenalty(e); 527 a++; 528 } 529 } 530 p /= a; 531 if (a > assigned || (assigned == a && p < penalty)) { 532 best = suggestion; 533 } 534 } 535 if (best != null) { 536 nrAccepted += 1.0; 537 Enrollment[] e = best.getEnrollments(); 538 for (int j = 0; j < e.length; j++) 539 if (e[j] != null && e[j].getAssignments() == null) 540 e[j] = null; 541 neighbour = new BranchBoundNeighbour(student, best.getValue(), e); 542 assigned = 0; 543 penalty = 0.0; 544 enrollments.clear(); 545 pairs.clear(); 546 for (int j = 0; j < neighbour.getAssignment().length; j++) { 547 Enrollment enrl = neighbour.getAssignment()[j]; 548 if (enrl != null && enrl.isCourseRequest() && enrl.getAssignments() != null) { 549 assigned++; 550 for (Section section : enrl.getSections()) 551 pairs.add(new RequestSectionPair(enrl.variable(), section)); 552 enrollments.put((CourseRequest) enrl.variable(), enrl.getSections()); 553 penalty += penalties.getPenalty(enrl); 554 } 555 } 556 penalty /= assigned; 557 inc("[S] Improved Penalty", penalty); 558 } 559 } 560 inc("[S] Final Penalty", penalty); 561 if (nrSuggestions > 0) { 562 inc("[S] Classes with suggestion", nrSuggestions); 563 inc("[S] Avg. # of suggestions", totalSuggestions / nrSuggestions); 564 inc("[S] Suggestion acceptance rate [%]", nrAccepted / nrSuggestions); 565 } else { 566 inc("[S] Student with no suggestions available", 1.0); 567 } 568 if (!pairs.isEmpty()) 569 inc("[S] Probability that a class has suggestions [%]", nrSuggestions / nrTries); 570 } 571 572 List<Enrollment> enrollments = new ArrayList<Enrollment>(); 573 i: for (int i = 0; i < neighbour.getAssignment().length; i++) { 574 Request request = original.getRequests().get(i); 575 Enrollment clonnedEnrollment = neighbour.getAssignment()[i]; 576 if (clonnedEnrollment != null && clonnedEnrollment.getAssignments() != null) { 577 if (request instanceof FreeTimeRequest) { 578 enrollments.add(((FreeTimeRequest) request).createEnrollment()); 579 } else { 580 for (Course course : ((CourseRequest) request).getCourses()) 581 if (course.getId() == clonnedEnrollment.getCourse().getId()) 582 for (Config config : course.getOffering().getConfigs()) 583 if (config.getId() == clonnedEnrollment.getConfig().getId()) { 584 Set<Section> assignments = new HashSet<Section>(); 585 for (Subpart subpart : config.getSubparts()) 586 for (Section section : subpart.getSections()) { 587 if (clonnedEnrollment.getSections().contains(section)) { 588 assignments.add(section); 589 } 590 } 591 Reservation reservation = null; 592 if (clonnedEnrollment.getReservation() != null) { 593 for (Reservation r : course.getOffering().getReservations()) 594 if (r.getId() == clonnedEnrollment.getReservation().getId()) { 595 reservation = r; 596 break; 597 } 598 } 599 enrollments.add(new Enrollment(request, clonnedEnrollment.getPriority(), 600 course, config, assignments, reservation)); 601 continue i; 602 } 603 } 604 } 605 } 606 synchronized (iModel) { 607 for (Request r : original.getRequests()) { 608 Enrollment e = assignment().getValue(r); 609 r.setInitialAssignment(e); 610 if (e != null) 611 updateSpace(assignment(), e, true); 612 } 613 for (Request r : original.getRequests()) 614 if (assignment().getValue(r) != null) 615 assignment().unassign(0, r); 616 boolean fail = false; 617 for (Enrollment enrl : enrollments) { 618 if (iModel.conflictValues(assignment(), enrl).isEmpty()) { 619 assignment().assign(0, enrl); 620 } else { 621 fail = true; 622 break; 623 } 624 } 625 if (fail) { 626 for (Request r : original.getRequests()) 627 if (assignment().getValue(r) != null) 628 assignment().unassign(0, r); 629 for (Request r : original.getRequests()) 630 if (r.getInitialAssignment() != null) 631 assignment().assign(0, r.getInitialAssignment()); 632 for (Request r : original.getRequests()) 633 if (assignment().getValue(r) != null) 634 updateSpace(assignment(), assignment().getValue(r), false); 635 } else { 636 for (Enrollment enrl : enrollments) 637 updateSpace(assignment(), enrl, false); 638 } 639 if (fail) 640 return false; 641 } 642 neighbour.assign(newAssignment, 0); 643 int a = 0, u = 0, np = 0, zp = 0, pp = 0, cp = 0; 644 double over = 0; 645 double p = 0.0; 646 for (Request r : student.getRequests()) { 647 if (r instanceof CourseRequest) { 648 Enrollment e = newAssignment.getValue(r); 649 if (e != null) { 650 for (Section s : e.getSections()) { 651 if (s.getPenalty() < 0.0) 652 np++; 653 if (s.getPenalty() == 0.0) 654 zp++; 655 if (s.getPenalty() > 0.0) 656 pp++; 657 if (s.getLimit() > 0) { 658 p += s.getPenalty(); 659 cp++; 660 } 661 over += model.getOverExpected(newAssignment, s, r); 662 } 663 a++; 664 } else { 665 u++; 666 } 667 } 668 } 669 inc("[A] Student"); 670 if (over > 0.0) 671 inc("[O] Over", over); 672 if (a > 0) 673 inc("[A] Assigned", a); 674 if (u > 0) 675 inc("[A] Not Assigned", u); 676 inc("[V] Value", neighbour.value(newAssignment)); 677 if (zp > 0) 678 inc("[P] Zero penalty", zp); 679 if (np > 0) 680 inc("[P] Negative penalty", np); 681 if (pp > 0) 682 inc("[P] Positive penalty", pp); 683 if (cp > 0) 684 inc("[P] Average penalty", p / cp); 685 } 686 inc("[T0] Time <10ms", time < 10 ? 1 : 0); 687 inc("[T1] Time <100ms", time < 100 ? 1 : 0); 688 inc("[T2] Time <250ms", time < 250 ? 1 : 0); 689 inc("[T3] Time <500ms", time < 500 ? 1 : 0); 690 inc("[T4] Time <1s", time < 1000 ? 1 : 0); 691 inc("[T5] Time >=1s", time >= 1000 ? 1 : 0); 692 return true; 693 } 694 695 public static void updateSpace(Assignment<Request, Enrollment> assignment, Enrollment enrollment, boolean increment) { 696 if (enrollment == null || !enrollment.isCourseRequest()) 697 return; 698 for (Section section : enrollment.getSections()) 699 section.setSpaceHeld(section.getSpaceHeld() + (increment ? 1.0 : -1.0)); 700 List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>(); 701 int totalLimit = 0; 702 for (Enrollment enrl : enrollment.getRequest().values(assignment)) { 703 if (!enrl.getCourse().equals(enrollment.getCourse())) 704 continue; 705 boolean overlaps = false; 706 for (Request otherRequest : enrollment.getRequest().getStudent().getRequests()) { 707 if (otherRequest.equals(enrollment.getRequest()) || !(otherRequest instanceof CourseRequest)) 708 continue; 709 Enrollment otherErollment = assignment.getValue(otherRequest); 710 if (otherErollment == null) 711 continue; 712 if (enrl.isOverlapping(otherErollment)) { 713 overlaps = true; 714 break; 715 } 716 } 717 if (!overlaps) { 718 feasibleEnrollments.add(enrl); 719 if (totalLimit >= 0) { 720 int limit = enrl.getLimit(); 721 if (limit < 0) 722 totalLimit = -1; 723 else 724 totalLimit += limit; 725 } 726 } 727 } 728 double change = enrollment.getRequest().getWeight() 729 / (totalLimit > 0 ? totalLimit : feasibleEnrollments.size()); 730 for (Enrollment feasibleEnrollment : feasibleEnrollments) 731 for (Section section : feasibleEnrollment.getSections()) { 732 if (totalLimit > 0) { 733 section.setSpaceExpected(section.getSpaceExpected() + (increment ? +change : -change) 734 * feasibleEnrollment.getLimit()); 735 } else { 736 section.setSpaceExpected(section.getSpaceExpected() + (increment ? +change : -change)); 737 } 738 } 739 } 740 741 public void run() { 742 sLog.info("Input: " + ToolBox.dict2string(model().getExtendedInfo(assignment()), 2)); 743 744 List<Student> students = new ArrayList<Student>(model().getStudents()); 745 String sort = System.getProperty("sort", "shuffle"); 746 if ("shuffle".equals(sort)) { 747 Collections.shuffle(students); 748 } else if ("choice".equals(sort)) { 749 StudentChoiceOrder ord = new StudentChoiceOrder(model().getProperties()); 750 ord.setReverse(false); 751 Collections.sort(students, ord); 752 } else if ("referse".equals(sort)) { 753 StudentChoiceOrder ord = new StudentChoiceOrder(model().getProperties()); 754 ord.setReverse(true); 755 Collections.sort(students, ord); 756 } 757 758 Iterator<Student> iterator = students.iterator(); 759 int nrThreads = Integer.parseInt(System.getProperty("nrConcurrent", "10")); 760 List<Executor> executors = new ArrayList<Executor>(); 761 for (int i = 0; i < nrThreads; i++) { 762 Executor executor = new Executor(iterator); 763 executor.start(); 764 executors.add(executor); 765 } 766 767 long t0 = System.currentTimeMillis(); 768 while (iterator.hasNext()) { 769 try { 770 Thread.sleep(60000); 771 } catch (InterruptedException e) { 772 } 773 long time = System.currentTimeMillis() - t0; 774 synchronized (iModel) { 775 sLog.info("Progress [" + (time / 60000) + "m]: " + ToolBox.dict2string(model().getExtendedInfo(assignment()), 2)); 776 } 777 } 778 779 for (Executor executor : executors) { 780 try { 781 executor.join(); 782 } catch (InterruptedException e) { 783 } 784 } 785 786 sLog.info("Output: " + ToolBox.dict2string(model().getExtendedInfo(assignment()), 2)); 787 long time = System.currentTimeMillis() - t0; 788 inc("[T] Run Time [m]", time / 60000.0); 789 790 } 791 792 public class Executor extends Thread { 793 private Iterator<Student> iStudents = null; 794 795 public Executor(Iterator<Student> students) { 796 iStudents = students; 797 } 798 799 @Override 800 public void run() { 801 try { 802 for (;;) { 803 Student student = iStudents.next(); 804 int attempt = 1; 805 while (!section(student)) { 806 sLog.warn(attempt + ". attempt failed for " + student.getId()); 807 inc("[F] Failed attempt", attempt); 808 attempt++; 809 if (attempt == 101) 810 break; 811 if (attempt > 10) { 812 try { 813 Thread.sleep(ToolBox.random(100 * attempt)); 814 } catch (InterruptedException e) { 815 } 816 } 817 } 818 if (attempt > 100) 819 inc("[F] Failed enrollment (all 100 attempts)"); 820 } 821 } catch (NoSuchElementException e) { 822 } 823 } 824 825 } 826 827 public class TestModel extends OnlineSectioningModel { 828 public TestModel(DataProperties config) { 829 super(config); 830 } 831 832 @Override 833 public Map<String, String> getExtendedInfo(Assignment<Request, Enrollment> assignment) { 834 Map<String, String> ret = super.getExtendedInfo(assignment); 835 for (Map.Entry<String, Counter> e : iCounters.entrySet()) 836 ret.put(e.getKey(), e.getValue().toString()); 837 ret.put("Weighting model", 838 (model().getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true) ? "multi-criteria " : "") + 839 (model().getProperties().getPropertyBoolean("StudentWeights.PriorityWeighting", true) ? "priority" : "equal")); 840 ret.put("B&B time limit", model().getProperties().getPropertyInt("Neighbour.BranchAndBoundTimeout", 1000) + " ms"); 841 if (iSuggestions) { 842 ret.put("Suggestion time limit", model().getProperties().getPropertyInt("Suggestions.Timeout", 1000) + " ms"); 843 } 844 return ret; 845 } 846 } 847 848 private static class RequestSectionPair { 849 private Request iRequest; 850 private Section iSection; 851 852 RequestSectionPair(Request request, Section section) { 853 iRequest = request; 854 iSection = section; 855 } 856 857 Request getRequest() { 858 return iRequest; 859 } 860 861 Section getSection() { 862 return iSection; 863 } 864 } 865 866 private void stats(File input) throws IOException { 867 File file = new File(input.getParentFile(), "stats.csv"); 868 DecimalFormat df = new DecimalFormat("0.0000"); 869 boolean ex = file.exists(); 870 PrintWriter pw = new PrintWriter(new FileWriter(file, true)); 871 if (!ex) { 872 pw.println("Input File,Run Time [m],Model,Sort,Over Expected,Not Assigned,Disb. Sections [%],Distance Confs.,Time Confs. [m]," 873 + "CPU Assignment [ms],Has Suggestions [%],Nbr Suggestions,Acceptance [%],CPU Suggestions [ms]"); 874 } 875 pw.print(input.getName() + ","); 876 pw.print(df.format(get("[T] Run Time [m]").sum()) + ","); 877 pw.print(model().getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true) ? "multi-criteria " : ""); 878 pw.print(model().getProperties().getPropertyBoolean("StudentWeights.PriorityWeighting", true) ? "priority" : "equal"); 879 pw.print(iSuggestions ? " with suggestions" : ""); 880 pw.print(","); 881 pw.print(System.getProperty("sort", "shuffle") + ","); 882 pw.print("\"" + model().getOverExpectedCriterion() + "\","); 883 884 pw.print(get("[A] Not Assigned").sum() + ","); 885 pw.print(df.format(getPercDisbalancedSections(assignment(), 0.1)) + ","); 886 if (model().getStudentQuality() != null) { 887 pw.print(df.format(((double) model().getStudentQuality().getTotalPenalty(assignment(), StudentQuality.Type.Distance, StudentQuality.Type.ShortDistance)) / model().getStudents().size()) + ","); 888 pw.print(df.format(5.0 * model().getStudentQuality().getTotalPenalty(assignment(), StudentQuality.Type.CourseTimeOverlap, StudentQuality.Type.FreeTimeOverlap, StudentQuality.Type.Unavailability) / model().getStudents().size()) + ","); 889 } else { 890 pw.print(df.format(((double) model().getDistanceConflict().getTotalNrConflicts(assignment())) / model().getStudents().size()) + ","); 891 pw.print(df.format(5.0 * model().getTimeOverlaps().getTotalNrConflicts(assignment()) / model().getStudents().size()) + ","); 892 } 893 pw.print(df.format(get("[C] CPU Time").avg()) + ","); 894 if (iSuggestions) { 895 pw.print(df.format(get("[S] Probability that a class has suggestions [%]").avg()) + ","); 896 pw.print(df.format(get("[S] Avg. # of suggestions").avg()) + ","); 897 pw.print(df.format(get("[S] Suggestion acceptance rate [%]").avg()) + ","); 898 pw.print(df.format(get("[S] Suggestion CPU Time").avg())); 899 } 900 pw.println(); 901 902 pw.flush(); 903 pw.close(); 904 } 905 906 public static void main(String[] args) { 907 try { 908 System.setProperty("jprof", "cpu"); 909 ToolBox.configureLogging(); 910 911 DataProperties cfg = new DataProperties(); 912 cfg.setProperty("Neighbour.BranchAndBoundTimeout", "5000"); 913 cfg.setProperty("Suggestions.Timeout", "1000"); 914 cfg.setProperty("Extensions.Classes", DistanceConflict.class.getName() + ";" + TimeOverlapsCounter.class.getName()); 915 cfg.setProperty("StudentWeights.Class", StudentSchedulingAssistantWeights.class.getName()); 916 cfg.setProperty("StudentWeights.PriorityWeighting", "true"); 917 cfg.setProperty("StudentWeights.LeftoverSpread", "true"); 918 cfg.setProperty("StudentWeights.BalancingFactor", "0.0"); 919 cfg.setProperty("Reservation.CanAssignOverTheLimit", "true"); 920 cfg.setProperty("Distances.Ellipsoid", DistanceMetric.Ellipsoid.WGS84.name()); 921 cfg.setProperty("StudentWeights.MultiCriteria", "true"); 922 cfg.setProperty("CourseRequest.SameTimePrecise", "true"); 923 924 cfg.setProperty("Xml.LoadBest", "false"); 925 cfg.setProperty("Xml.LoadCurrent", "false"); 926 927 cfg.putAll(System.getProperties()); 928 929 final Test test = new Test(cfg); 930 931 final File input = new File(args[0]); 932 StudentSectioningXMLLoader loader = new StudentSectioningXMLLoader(test.model(), test.assignment()); 933 loader.setInputFile(input); 934 loader.load(); 935 936 test.run(); 937 938 Solver<Request, Enrollment> s = new Solver<Request, Enrollment>(cfg); 939 s.setInitalSolution(test.model()); 940 StudentSectioningXMLSaver saver = new StudentSectioningXMLSaver(s); 941 File output = new File(input.getParentFile(), input.getName().substring(0, input.getName().lastIndexOf('.')) + 942 "-" + cfg.getProperty("run", "r0") + ".xml"); 943 saver.save(output); 944 945 test.stats(input); 946 } catch (Exception e) { 947 sLog.error("Test failed: " + e.getMessage(), e); 948 } 949 } 950 951 private static class Counter { 952 private double iTotal = 0.0, iMin = 0.0, iMax = 0.0, iTotalSquare = 0.0; 953 private int iCount = 0; 954 955 void inc(double value) { 956 if (iCount == 0) { 957 iTotal = value; 958 iMin = value; 959 iMax = value; 960 iTotalSquare = value * value; 961 } else { 962 iTotal += value; 963 iMin = Math.min(iMin, value); 964 iMax = Math.max(iMax, value); 965 iTotalSquare += value * value; 966 } 967 iCount++; 968 } 969 970 int count() { 971 return iCount; 972 } 973 974 double sum() { 975 return iTotal; 976 } 977 978 double min() { 979 return iMin; 980 } 981 982 double max() { 983 return iMax; 984 } 985 986 double rms() { 987 return (iCount == 0 ? 0.0 : Math.sqrt(iTotalSquare / iCount)); 988 } 989 990 double avg() { 991 return (iCount == 0 ? 0.0 : iTotal / iCount); 992 } 993 994 @Override 995 public String toString() { 996 return sDF.format(sum()) + " (min: " + sDF.format(min()) + ", max: " + sDF.format(max()) + 997 ", avg: " + sDF.format(avg()) + ", rms: " + sDF.format(rms()) + ", cnt: " + count() + ")"; 998 } 999 } 1000 1001}