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