001package org.cpsolver.studentsct; 002 003import java.io.BufferedReader; 004import java.io.File; 005import java.io.FileInputStream; 006import java.io.FileOutputStream; 007import java.io.FileReader; 008import java.io.FileWriter; 009import java.io.IOException; 010import java.io.PrintWriter; 011import java.text.DecimalFormat; 012import java.util.ArrayList; 013import java.util.Collection; 014import java.util.Collections; 015import java.util.Comparator; 016import java.util.Date; 017import java.util.HashSet; 018import java.util.HashMap; 019import java.util.Iterator; 020import java.util.List; 021import java.util.Map; 022import java.util.Set; 023import java.util.StringTokenizer; 024import java.util.TreeSet; 025 026 027import org.apache.log4j.ConsoleAppender; 028import org.apache.log4j.FileAppender; 029import org.apache.log4j.Level; 030import org.apache.log4j.Logger; 031import org.apache.log4j.PatternLayout; 032import org.cpsolver.ifs.assignment.Assignment; 033import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 034import org.cpsolver.ifs.assignment.EmptyAssignment; 035import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 036import org.cpsolver.ifs.model.Neighbour; 037import org.cpsolver.ifs.solution.Solution; 038import org.cpsolver.ifs.solution.SolutionListener; 039import org.cpsolver.ifs.solver.ParallelSolver; 040import org.cpsolver.ifs.solver.Solver; 041import org.cpsolver.ifs.solver.SolverListener; 042import org.cpsolver.ifs.util.DataProperties; 043import org.cpsolver.ifs.util.JProf; 044import org.cpsolver.ifs.util.Progress; 045import org.cpsolver.ifs.util.ProgressWriter; 046import org.cpsolver.ifs.util.ToolBox; 047import org.cpsolver.studentsct.check.CourseLimitCheck; 048import org.cpsolver.studentsct.check.InevitableStudentConflicts; 049import org.cpsolver.studentsct.check.OverlapCheck; 050import org.cpsolver.studentsct.check.SectionLimitCheck; 051import org.cpsolver.studentsct.extension.DistanceConflict; 052import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 053import org.cpsolver.studentsct.filter.CombinedStudentFilter; 054import org.cpsolver.studentsct.filter.FreshmanStudentFilter; 055import org.cpsolver.studentsct.filter.RandomStudentFilter; 056import org.cpsolver.studentsct.filter.ReverseStudentFilter; 057import org.cpsolver.studentsct.filter.StudentFilter; 058import org.cpsolver.studentsct.heuristics.StudentSctNeighbourSelection; 059import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection; 060import org.cpsolver.studentsct.heuristics.selection.OnlineSelection; 061import org.cpsolver.studentsct.heuristics.selection.SwapStudentSelection; 062import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour; 063import org.cpsolver.studentsct.heuristics.studentord.StudentOrder; 064import org.cpsolver.studentsct.heuristics.studentord.StudentRandomOrder; 065import org.cpsolver.studentsct.model.AcademicAreaCode; 066import org.cpsolver.studentsct.model.Course; 067import org.cpsolver.studentsct.model.CourseRequest; 068import org.cpsolver.studentsct.model.Enrollment; 069import org.cpsolver.studentsct.model.Offering; 070import org.cpsolver.studentsct.model.Request; 071import org.cpsolver.studentsct.model.Student; 072import org.cpsolver.studentsct.report.CourseConflictTable; 073import org.cpsolver.studentsct.report.DistanceConflictTable; 074import org.cpsolver.studentsct.report.RequestGroupTable; 075import org.cpsolver.studentsct.report.SectionConflictTable; 076import org.cpsolver.studentsct.report.TimeOverlapConflictTable; 077import org.cpsolver.studentsct.report.UnbalancedSectionsTable; 078import org.dom4j.Document; 079import org.dom4j.DocumentHelper; 080import org.dom4j.Element; 081import org.dom4j.io.OutputFormat; 082import org.dom4j.io.SAXReader; 083import org.dom4j.io.XMLWriter; 084 085/** 086 * A main class for running of the student sectioning solver from command line. <br> 087 * <br> 088 * Usage:<br> 089 * java -Xmx1024m -jar studentsct-1.1.jar config.properties [input_file] 090 * [output_folder] [batch|online|simple]<br> 091 * <br> 092 * Modes:<br> 093 * batch ... batch sectioning mode (default mode -- IFS solver with 094 * {@link StudentSctNeighbourSelection} is used)<br> 095 * online ... online sectioning mode (students are sectioned one by 096 * one, sectioning info (expected/held space) is used)<br> 097 * simple ... simple sectioning mode (students are sectioned one by 098 * one, sectioning info is not used)<br> 099 * See http://www.unitime.org for example configuration files and benchmark data 100 * sets.<br> 101 * <br> 102 * 103 * The test does the following steps: 104 * <ul> 105 * <li>Provided property file is loaded (see {@link DataProperties}). 106 * <li>Output folder is created (General.Output property) and logging is setup 107 * (using log4j). 108 * <li>Input data are loaded from the given XML file (calling 109 * {@link StudentSectioningXMLLoader#load()}). 110 * <li>Solver is executed (see {@link Solver}). 111 * <li>Resultant solution is saved to an XML file (calling 112 * {@link StudentSectioningXMLSaver#save()}. 113 * </ul> 114 * Also, a log and some reports (e.g., {@link CourseConflictTable} and 115 * {@link DistanceConflictTable}) are created in the output folder. 116 * 117 * <br> 118 * <br> 119 * Parameters: 120 * <table border='1' summary='Related Solver Parameters'> 121 * <tr> 122 * <th>Parameter</th> 123 * <th>Type</th> 124 * <th>Comment</th> 125 * </tr> 126 * <tr> 127 * <td>Test.LastLikeCourseDemands</td> 128 * <td>{@link String}</td> 129 * <td>Load last-like course demands from the given XML file (in the format that 130 * is being used for last like course demand table in the timetabling 131 * application)</td> 132 * </tr> 133 * <tr> 134 * <td>Test.StudentInfos</td> 135 * <td>{@link String}</td> 136 * <td>Load last-like course demands from the given XML file (in the format that 137 * is being used for last like course demand table in the timetabling 138 * application)</td> 139 * </tr> 140 * <tr> 141 * <td>Test.CrsReq</td> 142 * <td>{@link String}</td> 143 * <td>Load student requests from the given semi-colon separated list files (in 144 * the format that is being used by the old MSF system)</td> 145 * </tr> 146 * <tr> 147 * <td>Test.EtrChk</td> 148 * <td>{@link String}</td> 149 * <td>Load student information (academic area, classification, major, minor) 150 * from the given semi-colon separated list files (in the format that is being 151 * used by the old MSF system)</td> 152 * </tr> 153 * <tr> 154 * <td>Sectioning.UseStudentPreferencePenalties</td> 155 * <td>{@link Boolean}</td> 156 * <td>If true, {@link StudentPreferencePenalties} are used (applicable only for 157 * online sectioning)</td> 158 * </tr> 159 * <tr> 160 * <td>Test.StudentOrder</td> 161 * <td>{@link String}</td> 162 * <td>A class that is used for ordering of students (must be an interface of 163 * {@link StudentOrder}, default is {@link StudentRandomOrder}, not applicable 164 * only for batch sectioning)</td> 165 * </tr> 166 * <tr> 167 * <td>Test.CombineStudents</td> 168 * <td>{@link File}</td> 169 * <td>If provided, students are combined from the input file (last-like 170 * students) and the provided file (real students). Real non-freshmen students 171 * are taken from real data, last-like data are loaded on top of the real data 172 * (all students, but weighted to occupy only the remaining space).</td> 173 * </tr> 174 * <tr> 175 * <td>Test.CombineStudentsLastLike</td> 176 * <td>{@link File}</td> 177 * <td>If provided (together with Test.CombineStudents), students are combined 178 * from the this file (last-like students) and Test.CombineStudents file (real 179 * students). Real non-freshmen students are taken from real data, last-like 180 * data are loaded on top of the real data (all students, but weighted to occupy 181 * only the remaining space).</td> 182 * </tr> 183 * <tr> 184 * <td>Test.CombineAcceptProb</td> 185 * <td>{@link Double}</td> 186 * <td>Used in combining students, probability of a non-freshmen real student to 187 * be taken into the combined file (default is 1.0 -- all real non-freshmen 188 * students are taken).</td> 189 * </tr> 190 * <tr> 191 * <td>Test.FixPriorities</td> 192 * <td>{@link Boolean}</td> 193 * <td>If true, course/free time request priorities are corrected (to go from 194 * zero, without holes or duplicates).</td> 195 * </tr> 196 * <tr> 197 * <td>Test.ExtraStudents</td> 198 * <td>{@link File}</td> 199 * <td>If provided, students are loaded from the given file on top of the 200 * students loaded from the ordinary input file (students with the same id are 201 * skipped).</td> 202 * </tr> 203 * </table> 204 * <br> 205 * <br> 206 * 207 * @version StudentSct 1.3 (Student Sectioning)<br> 208 * Copyright (C) 2007 - 2014 Tomas Muller<br> 209 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 210 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 211 * <br> 212 * This library is free software; you can redistribute it and/or modify 213 * it under the terms of the GNU Lesser General Public License as 214 * published by the Free Software Foundation; either version 3 of the 215 * License, or (at your option) any later version. <br> 216 * <br> 217 * This library is distributed in the hope that it will be useful, but 218 * WITHOUT ANY WARRANTY; without even the implied warranty of 219 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 220 * Lesser General Public License for more details. <br> 221 * <br> 222 * You should have received a copy of the GNU Lesser General Public 223 * License along with this library; if not see 224 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 225 */ 226 227public class Test { 228 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(Test.class); 229 private static java.text.SimpleDateFormat sDateFormat = new java.text.SimpleDateFormat("yyMMdd_HHmmss", 230 java.util.Locale.US); 231 private static DecimalFormat sDF = new DecimalFormat("0.000"); 232 233 /** Load student sectioning model 234 * @param cfg solver configuration 235 * @return loaded solution 236 **/ 237 public static Solution<Request, Enrollment> load(DataProperties cfg) { 238 StudentSectioningModel model = null; 239 Assignment<Request, Enrollment> assignment = null; 240 try { 241 if (cfg.getProperty("Test.CombineStudents") == null) { 242 model = new StudentSectioningModel(cfg); 243 assignment = new DefaultSingleAssignment<Request, Enrollment>(); 244 new StudentSectioningXMLLoader(model, assignment).load(); 245 } else { 246 Solution<Request, Enrollment> solution = combineStudents(cfg, 247 new File(cfg.getProperty("Test.CombineStudentsLastLike", cfg.getProperty("General.Input", "." + File.separator + "solution.xml"))), 248 new File(cfg.getProperty("Test.CombineStudents"))); 249 model = (StudentSectioningModel)solution.getModel(); 250 assignment = solution.getAssignment(); 251 } 252 if (cfg.getProperty("Test.ExtraStudents") != null) { 253 StudentSectioningXMLLoader extra = new StudentSectioningXMLLoader(model, assignment); 254 extra.setInputFile(new File(cfg.getProperty("Test.ExtraStudents"))); 255 extra.setLoadOfferings(false); 256 extra.setLoadStudents(true); 257 extra.setStudentFilter(new ExtraStudentFilter(model)); 258 extra.load(); 259 } 260 if (cfg.getProperty("Test.LastLikeCourseDemands") != null) 261 loadLastLikeCourseDemandsXml(model, new File(cfg.getProperty("Test.LastLikeCourseDemands"))); 262 if (cfg.getProperty("Test.StudentInfos") != null) 263 loadStudentInfoXml(model, new File(cfg.getProperty("Test.StudentInfos"))); 264 if (cfg.getProperty("Test.CrsReq") != null) 265 loadCrsReqFiles(model, cfg.getProperty("Test.CrsReq")); 266 } catch (Exception e) { 267 sLog.error("Unable to load model, reason: " + e.getMessage(), e); 268 return null; 269 } 270 if (cfg.getPropertyBoolean("Debug.DistanceConflict", false)) 271 DistanceConflict.sDebug = true; 272 if (cfg.getPropertyBoolean("Debug.BranchBoundSelection", false)) 273 BranchBoundSelection.sDebug = true; 274 if (cfg.getPropertyBoolean("Debug.SwapStudentsSelection", false)) 275 SwapStudentSelection.sDebug = true; 276 if (cfg.getPropertyBoolean("Debug.TimeOverlaps", false)) 277 TimeOverlapsCounter.sDebug = true; 278 if (cfg.getProperty("CourseRequest.SameTimePrecise") != null) 279 CourseRequest.sSameTimePrecise = cfg.getPropertyBoolean("CourseRequest.SameTimePrecise", false); 280 Logger.getLogger(BacktrackNeighbourSelection.class).setLevel( 281 cfg.getPropertyBoolean("Debug.BacktrackNeighbourSelection", false) ? Level.DEBUG : Level.INFO); 282 if (cfg.getPropertyBoolean("Test.FixPriorities", false)) 283 fixPriorities(model); 284 return new Solution<Request, Enrollment>(model, assignment); 285 } 286 287 /** Batch sectioning test 288 * @param cfg solver configuration 289 * @return resultant solution 290 **/ 291 public static Solution<Request, Enrollment> batchSectioning(DataProperties cfg) { 292 Solution<Request, Enrollment> solution = load(cfg); 293 if (solution == null) 294 return null; 295 StudentSectioningModel model = (StudentSectioningModel)solution.getModel(); 296 297 if (cfg.getPropertyBoolean("Test.ComputeSectioningInfo", true)) 298 model.clearOnlineSectioningInfos(); 299 300 Progress.getInstance(model).addProgressListener(new ProgressWriter(System.out)); 301 302 solve(solution, cfg); 303 304 return solution; 305 } 306 307 /** Online sectioning test 308 * @param cfg solver configuration 309 * @return resultant solution 310 * @throws Exception thrown when the sectioning fails 311 **/ 312 public static Solution<Request, Enrollment> onlineSectioning(DataProperties cfg) throws Exception { 313 Solution<Request, Enrollment> solution = load(cfg); 314 if (solution == null) 315 return null; 316 StudentSectioningModel model = (StudentSectioningModel)solution.getModel(); 317 Assignment<Request, Enrollment> assignment = solution.getAssignment(); 318 319 solution.addSolutionListener(new TestSolutionListener()); 320 double startTime = JProf.currentTimeSec(); 321 322 Solver<Request, Enrollment> solver = new Solver<Request, Enrollment>(cfg); 323 solver.setInitalSolution(solution); 324 solver.initSolver(); 325 326 OnlineSelection onlineSelection = new OnlineSelection(cfg); 327 onlineSelection.init(solver); 328 329 double totalPenalty = 0, minPenalty = 0, maxPenalty = 0; 330 double minAvEnrlPenalty = 0, maxAvEnrlPenalty = 0; 331 double totalPrefPenalty = 0, minPrefPenalty = 0, maxPrefPenalty = 0; 332 double minAvEnrlPrefPenalty = 0, maxAvEnrlPrefPenalty = 0; 333 int nrChoices = 0, nrEnrollments = 0, nrCourseRequests = 0; 334 int chChoices = 0, chCourseRequests = 0, chStudents = 0; 335 336 int choiceLimit = model.getProperties().getPropertyInt("Test.ChoicesLimit", -1); 337 338 File outDir = new File(model.getProperties().getProperty("General.Output", ".")); 339 outDir.mkdirs(); 340 PrintWriter pw = new PrintWriter(new FileWriter(new File(outDir, "choices.csv"))); 341 342 List<Student> students = model.getStudents(); 343 try { 344 @SuppressWarnings("rawtypes") 345 Class studentOrdClass = Class.forName(model.getProperties().getProperty("Test.StudentOrder", StudentRandomOrder.class.getName())); 346 @SuppressWarnings("unchecked") 347 StudentOrder studentOrd = (StudentOrder) studentOrdClass.getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { model.getProperties() }); 348 students = studentOrd.order(model.getStudents()); 349 } catch (Exception e) { 350 sLog.error("Unable to reorder students, reason: " + e.getMessage(), e); 351 } 352 353 ShutdownHook hook = new ShutdownHook(solver); 354 Runtime.getRuntime().addShutdownHook(hook); 355 356 for (Student student : students) { 357 if (student.nrAssignedRequests(assignment) > 0) 358 continue; // skip students with assigned courses (i.e., students 359 // already assigned by a batch sectioning process) 360 sLog.info("Sectioning student: " + student); 361 362 BranchBoundSelection.Selection selection = onlineSelection.getSelection(assignment, student); 363 BranchBoundNeighbour neighbour = selection.select(); 364 if (neighbour != null) { 365 StudentPreferencePenalties penalties = null; 366 if (selection instanceof OnlineSelection.EpsilonSelection) { 367 OnlineSelection.EpsilonSelection epsSelection = (OnlineSelection.EpsilonSelection) selection; 368 penalties = epsSelection.getPenalties(); 369 for (int i = 0; i < neighbour.getAssignment().length; i++) { 370 Request r = student.getRequests().get(i); 371 if (r instanceof CourseRequest) { 372 nrCourseRequests++; 373 chCourseRequests++; 374 int chChoicesThisRq = 0; 375 CourseRequest request = (CourseRequest) r; 376 for (Enrollment x : request.getAvaiableEnrollments(assignment)) { 377 nrEnrollments++; 378 if (epsSelection.isAllowed(i, x)) { 379 nrChoices++; 380 if (choiceLimit <= 0 || chChoicesThisRq < choiceLimit) { 381 chChoices++; 382 chChoicesThisRq++; 383 } 384 } 385 } 386 } 387 } 388 chStudents++; 389 if (chStudents == 100) { 390 pw.println(sDF.format(((double) chChoices) / chCourseRequests)); 391 pw.flush(); 392 chStudents = 0; 393 chChoices = 0; 394 chCourseRequests = 0; 395 } 396 } 397 for (int i = 0; i < neighbour.getAssignment().length; i++) { 398 if (neighbour.getAssignment()[i] == null) 399 continue; 400 Enrollment enrollment = neighbour.getAssignment()[i]; 401 if (enrollment.getRequest() instanceof CourseRequest) { 402 CourseRequest request = (CourseRequest) enrollment.getRequest(); 403 double[] avEnrlMinMax = getMinMaxAvailableEnrollmentPenalty(assignment, request); 404 minAvEnrlPenalty += avEnrlMinMax[0]; 405 maxAvEnrlPenalty += avEnrlMinMax[1]; 406 totalPenalty += enrollment.getPenalty(); 407 minPenalty += request.getMinPenalty(); 408 maxPenalty += request.getMaxPenalty(); 409 if (penalties != null) { 410 double[] avEnrlPrefMinMax = penalties.getMinMaxAvailableEnrollmentPenalty(assignment, enrollment.getRequest()); 411 minAvEnrlPrefPenalty += avEnrlPrefMinMax[0]; 412 maxAvEnrlPrefPenalty += avEnrlPrefMinMax[1]; 413 totalPrefPenalty += penalties.getPenalty(enrollment); 414 minPrefPenalty += penalties.getMinPenalty(enrollment.getRequest()); 415 maxPrefPenalty += penalties.getMaxPenalty(enrollment.getRequest()); 416 } 417 } 418 } 419 neighbour.assign(assignment, solution.getIteration()); 420 sLog.info("Student " + student + " enrolls into " + neighbour); 421 onlineSelection.updateSpace(assignment, student); 422 } else { 423 sLog.warn("No solution found."); 424 } 425 solution.update(JProf.currentTimeSec() - startTime); 426 } 427 428 if (chCourseRequests > 0) 429 pw.println(sDF.format(((double) chChoices) / chCourseRequests)); 430 431 pw.flush(); 432 pw.close(); 433 434 HashMap<String, String> extra = new HashMap<String, String>(); 435 sLog.info("Overall penalty is " + getPerc(totalPenalty, minPenalty, maxPenalty) + "% (" 436 + sDF.format(totalPenalty) + "/" + sDF.format(minPenalty) + ".." + sDF.format(maxPenalty) + ")"); 437 extra.put("Overall penalty", getPerc(totalPenalty, minPenalty, maxPenalty) + "% (" + sDF.format(totalPenalty) 438 + "/" + sDF.format(minPenalty) + ".." + sDF.format(maxPenalty) + ")"); 439 extra.put("Overall available enrollment penalty", getPerc(totalPenalty, minAvEnrlPenalty, maxAvEnrlPenalty) 440 + "% (" + sDF.format(totalPenalty) + "/" + sDF.format(minAvEnrlPenalty) + ".." + sDF.format(maxAvEnrlPenalty) + ")"); 441 if (onlineSelection.isUseStudentPrefPenalties()) { 442 sLog.info("Overall preference penalty is " + getPerc(totalPrefPenalty, minPrefPenalty, maxPrefPenalty) 443 + "% (" + sDF.format(totalPrefPenalty) + "/" + sDF.format(minPrefPenalty) + ".." + sDF.format(maxPrefPenalty) + ")"); 444 extra.put("Overall preference penalty", getPerc(totalPrefPenalty, minPrefPenalty, maxPrefPenalty) + "% (" 445 + sDF.format(totalPrefPenalty) + "/" + sDF.format(minPrefPenalty) + ".." + sDF.format(maxPrefPenalty) + ")"); 446 extra.put("Overall preference available enrollment penalty", getPerc(totalPrefPenalty, 447 minAvEnrlPrefPenalty, maxAvEnrlPrefPenalty) 448 + "% (" + sDF.format(totalPrefPenalty) + "/" + sDF.format(minAvEnrlPrefPenalty) + ".." + sDF.format(maxAvEnrlPrefPenalty) + ")"); 449 extra.put("Average number of choices", sDF.format(((double) nrChoices) / nrCourseRequests) + " (" 450 + nrChoices + "/" + nrCourseRequests + ")"); 451 extra.put("Average number of enrollments", sDF.format(((double) nrEnrollments) / nrCourseRequests) + " (" 452 + nrEnrollments + "/" + nrCourseRequests + ")"); 453 } 454 hook.setExtra(extra); 455 456 return solution; 457 } 458 459 /** 460 * Minimum and maximum enrollment penalty, i.e., 461 * {@link Enrollment#getPenalty()} of all enrollments 462 * @param request a course request 463 * @return minimum and maximum of the enrollment penalty 464 */ 465 public static double[] getMinMaxEnrollmentPenalty(CourseRequest request) { 466 List<Enrollment> enrollments = request.values(new EmptyAssignment<Request, Enrollment>()); 467 if (enrollments.isEmpty()) 468 return new double[] { 0, 0 }; 469 double min = Double.MAX_VALUE, max = Double.MIN_VALUE; 470 for (Enrollment enrollment : enrollments) { 471 double penalty = enrollment.getPenalty(); 472 min = Math.min(min, penalty); 473 max = Math.max(max, penalty); 474 } 475 return new double[] { min, max }; 476 } 477 478 /** 479 * Minimum and maximum available enrollment penalty, i.e., 480 * {@link Enrollment#getPenalty()} of all available enrollments 481 * @param assignment current assignment 482 * @param request a course request 483 * @return minimum and maximum of the available enrollment penalty 484 */ 485 public static double[] getMinMaxAvailableEnrollmentPenalty(Assignment<Request, Enrollment> assignment, CourseRequest request) { 486 List<Enrollment> enrollments = request.getAvaiableEnrollments(assignment); 487 if (enrollments.isEmpty()) 488 return new double[] { 0, 0 }; 489 double min = Double.MAX_VALUE, max = Double.MIN_VALUE; 490 for (Enrollment enrollment : enrollments) { 491 double penalty = enrollment.getPenalty(); 492 min = Math.min(min, penalty); 493 max = Math.max(max, penalty); 494 } 495 return new double[] { min, max }; 496 } 497 498 /** 499 * Compute percentage 500 * 501 * @param value 502 * current value 503 * @param min 504 * minimal bound 505 * @param max 506 * maximal bound 507 * @return (value-min)/(max-min) 508 */ 509 public static String getPerc(double value, double min, double max) { 510 if (max == min) 511 return sDF.format(100.0); 512 return sDF.format(100.0 - 100.0 * (value - min) / (max - min)); 513 } 514 515 /** 516 * Print some information about the solution 517 * 518 * @param solution 519 * given solution 520 * @param computeTables 521 * true, if reports {@link CourseConflictTable} and 522 * {@link DistanceConflictTable} are to be computed as well 523 * @param computeSectInfos 524 * true, if online sectioning infou is to be computed as well 525 * (see 526 * {@link StudentSectioningModel#computeOnlineSectioningInfos(Assignment)}) 527 * @param runChecks 528 * true, if checks {@link OverlapCheck} and 529 * {@link SectionLimitCheck} are to be performed as well 530 */ 531 public static void printInfo(Solution<Request, Enrollment> solution, boolean computeTables, boolean computeSectInfos, boolean runChecks) { 532 StudentSectioningModel model = (StudentSectioningModel) solution.getModel(); 533 534 if (computeTables) { 535 if (solution.getModel().assignedVariables(solution.getAssignment()).size() > 0) { 536 try { 537 File outDir = new File(model.getProperties().getProperty("General.Output", ".")); 538 outDir.mkdirs(); 539 CourseConflictTable cct = new CourseConflictTable((StudentSectioningModel) solution.getModel()); 540 cct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "conflicts-lastlike.csv")); 541 cct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "conflicts-real.csv")); 542 543 DistanceConflictTable dct = new DistanceConflictTable((StudentSectioningModel) solution.getModel()); 544 dct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "distances-lastlike.csv")); 545 dct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "distances-real.csv")); 546 547 SectionConflictTable sct = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.OVERLAPS); 548 sct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "time-conflicts-lastlike.csv")); 549 sct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "time-conflicts-real.csv")); 550 551 SectionConflictTable ust = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.UNAVAILABILITIES); 552 ust.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "availability-conflicts-lastlike.csv")); 553 ust.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "availability-conflicts-real.csv")); 554 555 SectionConflictTable ct = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.OVERLAPS_AND_UNAVAILABILITIES); 556 ct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "section-conflicts-lastlike.csv")); 557 ct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "section-conflicts-real.csv")); 558 559 UnbalancedSectionsTable ubt = new UnbalancedSectionsTable((StudentSectioningModel) solution.getModel()); 560 ubt.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "unbalanced-lastlike.csv")); 561 ubt.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "unbalanced-real.csv")); 562 563 TimeOverlapConflictTable toc = new TimeOverlapConflictTable((StudentSectioningModel) solution.getModel()); 564 toc.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "time-overlaps-lastlike.csv")); 565 toc.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "time-overlaps-real.csv")); 566 567 RequestGroupTable rqt = new RequestGroupTable((StudentSectioningModel) solution.getModel()); 568 rqt.create(solution.getAssignment(), model.getProperties()).save(new File(outDir, "request-groups.csv")); 569 } catch (IOException e) { 570 sLog.error(e.getMessage(), e); 571 } 572 } 573 574 solution.saveBest(); 575 } 576 577 if (computeSectInfos) 578 model.computeOnlineSectioningInfos(solution.getAssignment()); 579 580 if (runChecks) { 581 try { 582 if (model.getProperties().getPropertyBoolean("Test.InevitableStudentConflictsCheck", false)) { 583 InevitableStudentConflicts ch = new InevitableStudentConflicts(model); 584 if (!ch.check(solution.getAssignment())) 585 ch.getCSVFile().save( 586 new File(new File(model.getProperties().getProperty("General.Output", ".")), 587 "inevitable-conflicts.csv")); 588 } 589 } catch (IOException e) { 590 sLog.error(e.getMessage(), e); 591 } 592 new OverlapCheck(model).check(solution.getAssignment()); 593 new SectionLimitCheck(model).check(solution.getAssignment()); 594 try { 595 CourseLimitCheck ch = new CourseLimitCheck(model); 596 if (!ch.check()) 597 ch.getCSVFile().save( 598 new File(new File(model.getProperties().getProperty("General.Output", ".")), 599 "course-limits.csv")); 600 } catch (IOException e) { 601 sLog.error(e.getMessage(), e); 602 } 603 } 604 605 sLog.info("Best solution found after " + solution.getBestTime() + " seconds (" + solution.getBestIteration() 606 + " iterations)."); 607 sLog.info("Info: " + ToolBox.dict2string(solution.getExtendedInfo(), 2)); 608 } 609 610 /** Solve the student sectioning problem using IFS solver 611 * @param solution current solution 612 * @param cfg solver configuration 613 * @return resultant solution 614 **/ 615 public static Solution<Request, Enrollment> solve(Solution<Request, Enrollment> solution, DataProperties cfg) { 616 int nrSolvers = cfg.getPropertyInt("Parallel.NrSolvers", 1); 617 Solver<Request, Enrollment> solver = (nrSolvers == 1 ? new Solver<Request, Enrollment>(cfg) : new ParallelSolver<Request, Enrollment>(cfg)); 618 solver.setInitalSolution(solution); 619 if (cfg.getPropertyBoolean("Test.Verbose", false)) { 620 solver.addSolverListener(new SolverListener<Request, Enrollment>() { 621 @Override 622 public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) { 623 return true; 624 } 625 626 @Override 627 public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) { 628 return true; 629 } 630 631 @Override 632 public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 633 sLog.debug("Select[" + iteration + "]: " + neighbour); 634 return true; 635 } 636 637 @Override 638 public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 639 sLog.debug("Failed[" + iteration + "]: " + neighbour); 640 } 641 }); 642 } 643 solution.addSolutionListener(new TestSolutionListener()); 644 645 Runtime.getRuntime().addShutdownHook(new ShutdownHook(solver)); 646 647 solver.start(); 648 try { 649 solver.getSolverThread().join(); 650 } catch (InterruptedException e) { 651 } 652 653 return solution; 654 } 655 656 /** 657 * Compute last-like student weight for the given course 658 * 659 * @param course 660 * given course 661 * @param real 662 * number of real students for the course 663 * @param lastLike 664 * number of last-like students for the course 665 * @return weight of a student request for the given course 666 */ 667 public static double getLastLikeStudentWeight(Course course, int real, int lastLike) { 668 int projected = course.getProjected(); 669 int limit = course.getLimit(); 670 if (course.getLimit() < 0) { 671 sLog.debug(" -- Course " + course.getName() + " is unlimited."); 672 return 1.0; 673 } 674 if (projected <= 0) { 675 sLog.warn(" -- No projected demand for course " + course.getName() + ", using course limit (" + limit 676 + ")"); 677 projected = limit; 678 } else if (limit < projected) { 679 sLog.warn(" -- Projected number of students is over course limit for course " + course.getName() + " (" 680 + Math.round(projected) + ">" + limit + ")"); 681 projected = limit; 682 } 683 if (lastLike == 0) { 684 sLog.warn(" -- No last like info for course " + course.getName()); 685 return 1.0; 686 } 687 double weight = ((double) Math.max(0, projected - real)) / lastLike; 688 sLog.debug(" -- last like student weight for " + course.getName() + " is " + weight + " (lastLike=" + lastLike 689 + ", real=" + real + ", projected=" + projected + ")"); 690 return weight; 691 } 692 693 /** 694 * Load last-like students from an XML file (the one that is used to load 695 * last like course demands table in the timetabling application) 696 * @param model problem model 697 * @param xml an XML file 698 */ 699 public static void loadLastLikeCourseDemandsXml(StudentSectioningModel model, File xml) { 700 try { 701 Document document = (new SAXReader()).read(xml); 702 Element root = document.getRootElement(); 703 HashMap<Course, List<Request>> requests = new HashMap<Course, List<Request>>(); 704 long reqId = 0; 705 for (Iterator<?> i = root.elementIterator("student"); i.hasNext();) { 706 Element studentEl = (Element) i.next(); 707 Student student = new Student(Long.parseLong(studentEl.attributeValue("externalId"))); 708 student.setDummy(true); 709 int priority = 0; 710 HashSet<Course> reqCourses = new HashSet<Course>(); 711 for (Iterator<?> j = studentEl.elementIterator("studentCourse"); j.hasNext();) { 712 Element courseEl = (Element) j.next(); 713 String subjectArea = courseEl.attributeValue("subject"); 714 String courseNbr = courseEl.attributeValue("courseNumber"); 715 Course course = null; 716 offerings: for (Offering offering : model.getOfferings()) { 717 for (Course c : offering.getCourses()) { 718 if (c.getSubjectArea().equals(subjectArea) && c.getCourseNumber().equals(courseNbr)) { 719 course = c; 720 break offerings; 721 } 722 } 723 } 724 if (course == null && courseNbr.charAt(courseNbr.length() - 1) >= 'A' 725 && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') { 726 String courseNbrNoSfx = courseNbr.substring(0, courseNbr.length() - 1); 727 offerings: for (Offering offering : model.getOfferings()) { 728 for (Course c : offering.getCourses()) { 729 if (c.getSubjectArea().equals(subjectArea) 730 && c.getCourseNumber().equals(courseNbrNoSfx)) { 731 course = c; 732 break offerings; 733 } 734 } 735 } 736 } 737 if (course == null) { 738 sLog.warn("Course " + subjectArea + " " + courseNbr + " not found."); 739 } else { 740 if (!reqCourses.add(course)) { 741 sLog.warn("Course " + subjectArea + " " + courseNbr + " already requested."); 742 } else { 743 List<Course> courses = new ArrayList<Course>(1); 744 courses.add(course); 745 CourseRequest request = new CourseRequest(reqId++, priority++, false, student, courses, false, null); 746 List<Request> requestsThisCourse = requests.get(course); 747 if (requestsThisCourse == null) { 748 requestsThisCourse = new ArrayList<Request>(); 749 requests.put(course, requestsThisCourse); 750 } 751 requestsThisCourse.add(request); 752 } 753 } 754 } 755 if (!student.getRequests().isEmpty()) 756 model.addStudent(student); 757 } 758 for (Map.Entry<Course, List<Request>> entry : requests.entrySet()) { 759 Course course = entry.getKey(); 760 List<Request> requestsThisCourse = entry.getValue(); 761 double weight = getLastLikeStudentWeight(course, 0, requestsThisCourse.size()); 762 for (Request request : requestsThisCourse) { 763 request.setWeight(weight); 764 } 765 } 766 } catch (Exception e) { 767 sLog.error(e.getMessage(), e); 768 } 769 } 770 771 /** 772 * Load course request from the given files (in the format being used by the 773 * old MSF system) 774 * 775 * @param model 776 * student sectioning model (with offerings loaded) 777 * @param files 778 * semi-colon separated list of files to be loaded 779 */ 780 public static void loadCrsReqFiles(StudentSectioningModel model, String files) { 781 try { 782 boolean lastLike = model.getProperties().getPropertyBoolean("Test.CrsReqIsLastLike", true); 783 boolean shuffleIds = model.getProperties().getPropertyBoolean("Test.CrsReqShuffleStudentIds", true); 784 boolean tryWithoutSuffix = model.getProperties().getPropertyBoolean("Test.CrsReqTryWithoutSuffix", false); 785 HashMap<Long, Student> students = new HashMap<Long, Student>(); 786 long reqId = 0; 787 for (StringTokenizer stk = new StringTokenizer(files, ";"); stk.hasMoreTokens();) { 788 String file = stk.nextToken(); 789 sLog.debug("Loading " + file + " ..."); 790 BufferedReader in = new BufferedReader(new FileReader(file)); 791 String line; 792 int lineIndex = 0; 793 while ((line = in.readLine()) != null) { 794 lineIndex++; 795 if (line.length() <= 150) 796 continue; 797 char code = line.charAt(13); 798 if (code == 'H' || code == 'T') 799 continue; // skip header and tail 800 long studentId = Long.parseLong(line.substring(14, 23)); 801 Student student = students.get(new Long(studentId)); 802 if (student == null) { 803 student = new Student(studentId); 804 if (lastLike) 805 student.setDummy(true); 806 students.put(new Long(studentId), student); 807 sLog.debug(" -- loading student " + studentId + " ..."); 808 } else 809 sLog.debug(" -- updating student " + studentId + " ..."); 810 line = line.substring(150); 811 while (line.length() >= 20) { 812 String subjectArea = line.substring(0, 4).trim(); 813 String courseNbr = line.substring(4, 8).trim(); 814 if (subjectArea.length() == 0 || courseNbr.length() == 0) { 815 line = line.substring(20); 816 continue; 817 } 818 /* 819 * // UNUSED String instrSel = line.substring(8,10); 820 * //ZZ - Remove previous instructor selection char 821 * reqPDiv = line.charAt(10); //P - Personal preference; 822 * C - Conflict resolution; //0 - (Zero) used by program 823 * only, for change requests to reschedule division // 824 * (used to reschedule canceled division) String reqDiv 825 * = line.substring(11,13); //00 - Reschedule division 826 * String reqSect = line.substring(13,15); //Contains 827 * designator for designator-required courses String 828 * credit = line.substring(15,19); char nameRaise = 829 * line.charAt(19); //N - Name raise 830 */ 831 char action = line.charAt(19); // A - Add; D - Drop; C - 832 // Change 833 sLog.debug(" -- requesting " + subjectArea + " " + courseNbr + " (action:" + action 834 + ") ..."); 835 Course course = null; 836 offerings: for (Offering offering : model.getOfferings()) { 837 for (Course c : offering.getCourses()) { 838 if (c.getSubjectArea().equals(subjectArea) && c.getCourseNumber().equals(courseNbr)) { 839 course = c; 840 break offerings; 841 } 842 } 843 } 844 if (course == null && tryWithoutSuffix && courseNbr.charAt(courseNbr.length() - 1) >= 'A' 845 && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') { 846 String courseNbrNoSfx = courseNbr.substring(0, courseNbr.length() - 1); 847 offerings: for (Offering offering : model.getOfferings()) { 848 for (Course c : offering.getCourses()) { 849 if (c.getSubjectArea().equals(subjectArea) 850 && c.getCourseNumber().equals(courseNbrNoSfx)) { 851 course = c; 852 break offerings; 853 } 854 } 855 } 856 } 857 if (course == null) { 858 if (courseNbr.charAt(courseNbr.length() - 1) >= 'A' 859 && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') { 860 } else { 861 sLog.warn(" -- course " + subjectArea + " " + courseNbr + " not found (file " 862 + file + ", line " + lineIndex + ")"); 863 } 864 } else { 865 CourseRequest courseRequest = null; 866 for (Request request : student.getRequests()) { 867 if (request instanceof CourseRequest 868 && ((CourseRequest) request).getCourses().contains(course)) { 869 courseRequest = (CourseRequest) request; 870 break; 871 } 872 } 873 if (action == 'A') { 874 if (courseRequest == null) { 875 List<Course> courses = new ArrayList<Course>(1); 876 courses.add(course); 877 courseRequest = new CourseRequest(reqId++, student.getRequests().size(), false, student, courses, false, null); 878 } else { 879 sLog.warn(" -- request for course " + course + " is already present"); 880 } 881 } else if (action == 'D') { 882 if (courseRequest == null) { 883 sLog.warn(" -- request for course " + course 884 + " is not present -- cannot be dropped"); 885 } else { 886 student.getRequests().remove(courseRequest); 887 } 888 } else if (action == 'C') { 889 if (courseRequest == null) { 890 sLog.warn(" -- request for course " + course 891 + " is not present -- cannot be changed"); 892 } else { 893 // ? 894 } 895 } else { 896 sLog.warn(" -- unknown action " + action); 897 } 898 } 899 line = line.substring(20); 900 } 901 } 902 in.close(); 903 } 904 HashMap<Course, List<Request>> requests = new HashMap<Course, List<Request>>(); 905 Set<Long> studentIds = new HashSet<Long>(); 906 for (Student student: students.values()) { 907 if (!student.getRequests().isEmpty()) 908 model.addStudent(student); 909 if (shuffleIds) { 910 long newId = -1; 911 while (true) { 912 newId = 1 + (long) (999999999L * Math.random()); 913 if (studentIds.add(new Long(newId))) 914 break; 915 } 916 student.setId(newId); 917 } 918 if (student.isDummy()) { 919 for (Request request : student.getRequests()) { 920 if (request instanceof CourseRequest) { 921 Course course = ((CourseRequest) request).getCourses().get(0); 922 List<Request> requestsThisCourse = requests.get(course); 923 if (requestsThisCourse == null) { 924 requestsThisCourse = new ArrayList<Request>(); 925 requests.put(course, requestsThisCourse); 926 } 927 requestsThisCourse.add(request); 928 } 929 } 930 } 931 } 932 Collections.sort(model.getStudents(), new Comparator<Student>() { 933 @Override 934 public int compare(Student o1, Student o2) { 935 return Double.compare(o1.getId(), o2.getId()); 936 } 937 }); 938 for (Map.Entry<Course, List<Request>> entry : requests.entrySet()) { 939 Course course = entry.getKey(); 940 List<Request> requestsThisCourse = entry.getValue(); 941 double weight = getLastLikeStudentWeight(course, 0, requestsThisCourse.size()); 942 for (Request request : requestsThisCourse) { 943 request.setWeight(weight); 944 } 945 } 946 if (model.getProperties().getProperty("Test.EtrChk") != null) { 947 for (StringTokenizer stk = new StringTokenizer(model.getProperties().getProperty("Test.EtrChk"), ";"); stk 948 .hasMoreTokens();) { 949 String file = stk.nextToken(); 950 sLog.debug("Loading " + file + " ..."); 951 BufferedReader in = new BufferedReader(new FileReader(file)); 952 try { 953 String line; 954 while ((line = in.readLine()) != null) { 955 if (line.length() < 55) 956 continue; 957 char code = line.charAt(12); 958 if (code == 'H' || code == 'T') 959 continue; // skip header and tail 960 if (code == 'D' || code == 'K') 961 continue; // skip delete nad cancel 962 long studentId = Long.parseLong(line.substring(2, 11)); 963 Student student = students.get(new Long(studentId)); 964 if (student == null) { 965 sLog.info(" -- student " + studentId + " not found"); 966 continue; 967 } 968 sLog.info(" -- reading student " + studentId); 969 String area = line.substring(15, 18).trim(); 970 if (area.length() == 0) 971 continue; 972 String clasf = line.substring(18, 20).trim(); 973 String major = line.substring(21, 24).trim(); 974 String minor = line.substring(24, 27).trim(); 975 student.getAcademicAreaClasiffications().clear(); 976 student.getMajors().clear(); 977 student.getMinors().clear(); 978 student.getAcademicAreaClasiffications().add(new AcademicAreaCode(area, clasf)); 979 if (major.length() > 0) 980 student.getMajors().add(new AcademicAreaCode(area, major)); 981 if (minor.length() > 0) 982 student.getMinors().add(new AcademicAreaCode(area, minor)); 983 } 984 } finally { 985 in.close(); 986 } 987 } 988 } 989 int without = 0; 990 for (Student student: students.values()) { 991 if (student.getAcademicAreaClasiffications().isEmpty()) 992 without++; 993 } 994 fixPriorities(model); 995 sLog.info("Students without academic area: " + without); 996 } catch (Exception e) { 997 sLog.error(e.getMessage(), e); 998 } 999 } 1000 1001 public static void fixPriorities(StudentSectioningModel model) { 1002 for (Student student : model.getStudents()) { 1003 Collections.sort(student.getRequests(), new Comparator<Request>() { 1004 @Override 1005 public int compare(Request r1, Request r2) { 1006 int cmp = Double.compare(r1.getPriority(), r2.getPriority()); 1007 if (cmp != 0) 1008 return cmp; 1009 return Double.compare(r1.getId(), r2.getId()); 1010 } 1011 }); 1012 int priority = 0; 1013 for (Request request : student.getRequests()) { 1014 if (priority != request.getPriority()) { 1015 sLog.debug("Change priority of " + request + " to " + priority); 1016 request.setPriority(priority); 1017 } 1018 } 1019 } 1020 } 1021 1022 /** Load student infos from a given XML file. 1023 * @param model problem model 1024 * @param xml an XML file 1025 **/ 1026 public static void loadStudentInfoXml(StudentSectioningModel model, File xml) { 1027 try { 1028 sLog.info("Loading student infos from " + xml); 1029 Document document = (new SAXReader()).read(xml); 1030 Element root = document.getRootElement(); 1031 HashMap<Long, Student> studentTable = new HashMap<Long, Student>(); 1032 for (Student student : model.getStudents()) { 1033 studentTable.put(new Long(student.getId()), student); 1034 } 1035 for (Iterator<?> i = root.elementIterator("student"); i.hasNext();) { 1036 Element studentEl = (Element) i.next(); 1037 Student student = studentTable.get(Long.valueOf(studentEl.attributeValue("externalId"))); 1038 if (student == null) { 1039 sLog.debug(" -- student " + studentEl.attributeValue("externalId") + " not found"); 1040 continue; 1041 } 1042 sLog.debug(" -- loading info for student " + student); 1043 student.getAcademicAreaClasiffications().clear(); 1044 if (studentEl.element("studentAcadAreaClass") != null) 1045 for (Iterator<?> j = studentEl.element("studentAcadAreaClass").elementIterator("acadAreaClass"); j 1046 .hasNext();) { 1047 Element studentAcadAreaClassElement = (Element) j.next(); 1048 student.getAcademicAreaClasiffications().add( 1049 new AcademicAreaCode(studentAcadAreaClassElement.attributeValue("academicArea"), 1050 studentAcadAreaClassElement.attributeValue("academicClass"))); 1051 } 1052 sLog.debug(" -- acad areas classifs " + student.getAcademicAreaClasiffications()); 1053 student.getMajors().clear(); 1054 if (studentEl.element("studentMajors") != null) 1055 for (Iterator<?> j = studentEl.element("studentMajors").elementIterator("major"); j.hasNext();) { 1056 Element studentMajorElement = (Element) j.next(); 1057 student.getMajors().add( 1058 new AcademicAreaCode(studentMajorElement.attributeValue("academicArea"), 1059 studentMajorElement.attributeValue("code"))); 1060 } 1061 sLog.debug(" -- majors " + student.getMajors()); 1062 student.getMinors().clear(); 1063 if (studentEl.element("studentMinors") != null) 1064 for (Iterator<?> j = studentEl.element("studentMinors").elementIterator("minor"); j.hasNext();) { 1065 Element studentMinorElement = (Element) j.next(); 1066 student.getMinors().add( 1067 new AcademicAreaCode(studentMinorElement.attributeValue("academicArea", ""), 1068 studentMinorElement.attributeValue("code", ""))); 1069 } 1070 sLog.debug(" -- minors " + student.getMinors()); 1071 } 1072 } catch (Exception e) { 1073 sLog.error(e.getMessage(), e); 1074 } 1075 } 1076 1077 /** Save solution info as XML 1078 * @param solution current solution 1079 * @param extra solution extra info 1080 * @param file file to write 1081 **/ 1082 public static void saveInfoToXML(Solution<Request, Enrollment> solution, Map<String, String> extra, File file) { 1083 FileOutputStream fos = null; 1084 try { 1085 Document document = DocumentHelper.createDocument(); 1086 document.addComment("Solution Info"); 1087 1088 Element root = document.addElement("info"); 1089 TreeSet<Map.Entry<String, String>> entrySet = new TreeSet<Map.Entry<String, String>>( 1090 new Comparator<Map.Entry<String, String>>() { 1091 @Override 1092 public int compare(Map.Entry<String, String> e1, Map.Entry<String, String> e2) { 1093 return e1.getKey().compareTo(e2.getKey()); 1094 } 1095 }); 1096 entrySet.addAll(solution.getExtendedInfo().entrySet()); 1097 if (extra != null) 1098 entrySet.addAll(extra.entrySet()); 1099 for (Map.Entry<String, String> entry : entrySet) { 1100 root.addElement("property").addAttribute("name", entry.getKey()).setText(entry.getValue()); 1101 } 1102 1103 fos = new FileOutputStream(file); 1104 (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(document); 1105 fos.flush(); 1106 fos.close(); 1107 fos = null; 1108 } catch (Exception e) { 1109 sLog.error("Unable to save info, reason: " + e.getMessage(), e); 1110 } finally { 1111 try { 1112 if (fos != null) 1113 fos.close(); 1114 } catch (IOException e) { 1115 } 1116 } 1117 } 1118 1119 private static void fixWeights(StudentSectioningModel model) { 1120 HashMap<Course, Integer> lastLike = new HashMap<Course, Integer>(); 1121 HashMap<Course, Integer> real = new HashMap<Course, Integer>(); 1122 HashSet<Long> lastLikeIds = new HashSet<Long>(); 1123 HashSet<Long> realIds = new HashSet<Long>(); 1124 for (Student student : model.getStudents()) { 1125 if (student.isDummy()) { 1126 if (!lastLikeIds.add(new Long(student.getId()))) { 1127 sLog.error("Two last-like student with id " + student.getId()); 1128 } 1129 } else { 1130 if (!realIds.add(new Long(student.getId()))) { 1131 sLog.error("Two real student with id " + student.getId()); 1132 } 1133 } 1134 for (Request request : student.getRequests()) { 1135 if (request instanceof CourseRequest) { 1136 CourseRequest courseRequest = (CourseRequest) request; 1137 Course course = courseRequest.getCourses().get(0); 1138 Integer cnt = (student.isDummy() ? lastLike : real).get(course); 1139 (student.isDummy() ? lastLike : real).put(course, new Integer( 1140 (cnt == null ? 0 : cnt.intValue()) + 1)); 1141 } 1142 } 1143 } 1144 for (Student student : new ArrayList<Student>(model.getStudents())) { 1145 if (student.isDummy() && realIds.contains(new Long(student.getId()))) { 1146 sLog.warn("There is both last-like and real student with id " + student.getId()); 1147 long newId = -1; 1148 while (true) { 1149 newId = 1 + (long) (999999999L * Math.random()); 1150 if (!realIds.contains(new Long(newId)) && !lastLikeIds.contains(new Long(newId))) 1151 break; 1152 } 1153 lastLikeIds.remove(new Long(student.getId())); 1154 lastLikeIds.add(new Long(newId)); 1155 student.setId(newId); 1156 sLog.warn(" -- last-like student id changed to " + student.getId()); 1157 } 1158 for (Request request : new ArrayList<Request>(student.getRequests())) { 1159 if (!student.isDummy()) { 1160 request.setWeight(1.0); 1161 continue; 1162 } 1163 if (request instanceof CourseRequest) { 1164 CourseRequest courseRequest = (CourseRequest) request; 1165 Course course = courseRequest.getCourses().get(0); 1166 Integer lastLikeCnt = lastLike.get(course); 1167 Integer realCnt = real.get(course); 1168 courseRequest.setWeight(getLastLikeStudentWeight(course, realCnt == null ? 0 : realCnt.intValue(), 1169 lastLikeCnt == null ? 0 : lastLikeCnt.intValue())); 1170 } else 1171 request.setWeight(1.0); 1172 if (request.getWeight() <= 0.0) { 1173 model.removeVariable(request); 1174 student.getRequests().remove(request); 1175 } 1176 } 1177 if (student.getRequests().isEmpty()) { 1178 model.getStudents().remove(student); 1179 } 1180 } 1181 } 1182 1183 /** Combine students from the provided two files 1184 * @param cfg solver configuration 1185 * @param lastLikeStudentData a file containing last-like student data 1186 * @param realStudentData a file containing real student data 1187 * @return combined solution 1188 **/ 1189 public static Solution<Request, Enrollment> combineStudents(DataProperties cfg, File lastLikeStudentData, File realStudentData) { 1190 try { 1191 RandomStudentFilter rnd = new RandomStudentFilter(1.0); 1192 1193 StudentSectioningModel model = null; 1194 Assignment<Request, Enrollment> assignment = new DefaultSingleAssignment<Request, Enrollment>(); 1195 1196 for (StringTokenizer stk = new StringTokenizer(cfg.getProperty("Test.CombineAcceptProb", "1.0"), ","); stk.hasMoreTokens();) { 1197 double acceptProb = Double.parseDouble(stk.nextToken()); 1198 sLog.info("Test.CombineAcceptProb=" + acceptProb); 1199 rnd.setProbability(acceptProb); 1200 1201 StudentFilter batchFilter = new CombinedStudentFilter(new ReverseStudentFilter( 1202 new FreshmanStudentFilter()), rnd, CombinedStudentFilter.OP_AND); 1203 1204 model = new StudentSectioningModel(cfg); 1205 StudentSectioningXMLLoader loader = new StudentSectioningXMLLoader(model, assignment); 1206 loader.setLoadStudents(false); 1207 loader.load(); 1208 1209 StudentSectioningXMLLoader lastLikeLoader = new StudentSectioningXMLLoader(model, assignment); 1210 lastLikeLoader.setInputFile(lastLikeStudentData); 1211 lastLikeLoader.setLoadOfferings(false); 1212 lastLikeLoader.setLoadStudents(true); 1213 lastLikeLoader.load(); 1214 1215 StudentSectioningXMLLoader realLoader = new StudentSectioningXMLLoader(model, assignment); 1216 realLoader.setInputFile(realStudentData); 1217 realLoader.setLoadOfferings(false); 1218 realLoader.setLoadStudents(true); 1219 realLoader.setStudentFilter(batchFilter); 1220 realLoader.load(); 1221 1222 fixWeights(model); 1223 1224 fixPriorities(model); 1225 1226 Solver<Request, Enrollment> solver = new Solver<Request, Enrollment>(model.getProperties()); 1227 solver.setInitalSolution(model); 1228 new StudentSectioningXMLSaver(solver).save(new File(new File(model.getProperties().getProperty( 1229 "General.Output", ".")), "solution-r" + ((int) (100.0 * acceptProb)) + ".xml")); 1230 1231 } 1232 1233 return model == null ? null : new Solution<Request, Enrollment>(model, assignment); 1234 1235 } catch (Exception e) { 1236 sLog.error("Unable to combine students, reason: " + e.getMessage(), e); 1237 return null; 1238 } 1239 } 1240 1241 /** 1242 * Setup log4j logging 1243 * 1244 * @param logFile log file 1245 */ 1246 public static void setupLogging(File logFile) { 1247 Logger root = Logger.getRootLogger(); 1248 ConsoleAppender console = new ConsoleAppender(new PatternLayout("[%t] %m%n")); 1249 console.setThreshold(Level.INFO); 1250 root.addAppender(console); 1251 if (logFile != null) { 1252 try { 1253 FileAppender file = new FileAppender(new PatternLayout("%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n"), logFile.getPath(), false); 1254 file.setThreshold(Level.DEBUG); 1255 root.addAppender(file); 1256 } catch (IOException e) { 1257 sLog.fatal("Unable to configure logging, reason: " + e.getMessage(), e); 1258 } 1259 } 1260 } 1261 1262 /** Main 1263 * @param args program arguments 1264 **/ 1265 public static void main(String[] args) { 1266 try { 1267 DataProperties cfg = new DataProperties(); 1268 cfg.setProperty("Termination.Class", "org.cpsolver.ifs.termination.GeneralTerminationCondition"); 1269 cfg.setProperty("Termination.StopWhenComplete", "true"); 1270 cfg.setProperty("Termination.TimeOut", "600"); 1271 cfg.setProperty("Comparator.Class", "org.cpsolver.ifs.solution.GeneralSolutionComparator"); 1272 cfg.setProperty("Value.Class", "org.cpsolver.studentsct.heuristics.EnrollmentSelection");// org.cpsolver.ifs.heuristics.GeneralValueSelection 1273 cfg.setProperty("Value.WeightConflicts", "1.0"); 1274 cfg.setProperty("Value.WeightNrAssignments", "0.0"); 1275 cfg.setProperty("Variable.Class", "org.cpsolver.ifs.heuristics.GeneralVariableSelection"); 1276 cfg.setProperty("Neighbour.Class", "org.cpsolver.studentsct.heuristics.StudentSctNeighbourSelection"); 1277 cfg.setProperty("General.SaveBestUnassigned", "0"); 1278 cfg.setProperty("Extensions.Classes", 1279 "org.cpsolver.ifs.extension.ConflictStatistics;org.cpsolver.studentsct.extension.DistanceConflict" + 1280 ";org.cpsolver.studentsct.extension.TimeOverlapsCounter"); 1281 cfg.setProperty("Data.Initiative", "puWestLafayetteTrdtn"); 1282 cfg.setProperty("Data.Term", "Fal"); 1283 cfg.setProperty("Data.Year", "2007"); 1284 cfg.setProperty("General.Input", "pu-sectll-fal07-s.xml"); 1285 if (args.length >= 1) { 1286 cfg.load(new FileInputStream(args[0])); 1287 } 1288 cfg.putAll(System.getProperties()); 1289 1290 if (args.length >= 2) { 1291 cfg.setProperty("General.Input", args[1]); 1292 } 1293 1294 File outDir = null; 1295 if (args.length >= 3) { 1296 outDir = new File(args[2], sDateFormat.format(new Date())); 1297 } else if (cfg.getProperty("General.Output") != null) { 1298 outDir = new File(cfg.getProperty("General.Output", "."), sDateFormat.format(new Date())); 1299 } else { 1300 outDir = new File(System.getProperty("user.home", ".") + File.separator + "Sectioning-Test" + File.separator + (sDateFormat.format(new Date()))); 1301 } 1302 outDir.mkdirs(); 1303 setupLogging(new File(outDir, "debug.log")); 1304 cfg.setProperty("General.Output", outDir.getAbsolutePath()); 1305 1306 if (args.length >= 4 && "online".equals(args[3])) { 1307 onlineSectioning(cfg); 1308 } else if (args.length >= 4 && "simple".equals(args[3])) { 1309 cfg.setProperty("Sectioning.UseOnlinePenalties", "false"); 1310 onlineSectioning(cfg); 1311 } else { 1312 batchSectioning(cfg); 1313 } 1314 } catch (Exception e) { 1315 sLog.error(e.getMessage(), e); 1316 e.printStackTrace(); 1317 } 1318 } 1319 1320 public static class ExtraStudentFilter implements StudentFilter { 1321 HashSet<Long> iIds = new HashSet<Long>(); 1322 1323 public ExtraStudentFilter(StudentSectioningModel model) { 1324 for (Student student : model.getStudents()) { 1325 iIds.add(new Long(student.getId())); 1326 } 1327 } 1328 1329 @Override 1330 public boolean accept(Student student) { 1331 return !iIds.contains(new Long(student.getId())); 1332 } 1333 } 1334 1335 public static class TestSolutionListener implements SolutionListener<Request, Enrollment> { 1336 @Override 1337 public void solutionUpdated(Solution<Request, Enrollment> solution) { 1338 StudentSectioningModel m = (StudentSectioningModel) solution.getModel(); 1339 if (m.getTimeOverlaps() != null && TimeOverlapsCounter.sDebug) 1340 m.getTimeOverlaps().checkTotalNrConflicts(solution.getAssignment()); 1341 if (m.getDistanceConflict() != null && DistanceConflict.sDebug) 1342 m.getDistanceConflict().checkAllConflicts(solution.getAssignment()); 1343 } 1344 1345 @Override 1346 public void getInfo(Solution<Request, Enrollment> solution, Map<String, String> info) { 1347 } 1348 1349 @Override 1350 public void getInfo(Solution<Request, Enrollment> solution, Map<String, String> info, Collection<Request> variables) { 1351 } 1352 1353 @Override 1354 public void bestCleared(Solution<Request, Enrollment> solution) { 1355 } 1356 1357 @Override 1358 public void bestSaved(Solution<Request, Enrollment> solution) { 1359 sLog.info("**BEST** " + ((StudentSectioningModel)solution.getModel()).toString(solution.getAssignment()) + ", TM:" + sDF.format(solution.getTime() / 3600.0) + "h" + 1360 (solution.getFailedIterations() > 0 ? ", F:" + sDF.format(100.0 * solution.getFailedIterations() / solution.getIteration()) + "%" : "")); 1361 } 1362 1363 @Override 1364 public void bestRestored(Solution<Request, Enrollment> solution) { 1365 } 1366 } 1367 1368 private static class ShutdownHook extends Thread { 1369 Solver<Request, Enrollment> iSolver = null; 1370 Map<String, String> iExtra = null; 1371 1372 private ShutdownHook(Solver<Request, Enrollment> solver) { 1373 setName("ShutdownHook"); 1374 iSolver = solver; 1375 } 1376 1377 void setExtra(Map<String, String> extra) { iExtra = extra; } 1378 1379 @Override 1380 public void run() { 1381 try { 1382 if (iSolver.isRunning()) iSolver.stopSolver(); 1383 Solution<Request, Enrollment> solution = iSolver.lastSolution(); 1384 solution.restoreBest(); 1385 DataProperties cfg = iSolver.getProperties(); 1386 1387 printInfo(solution, 1388 cfg.getPropertyBoolean("Test.CreateReports", true), 1389 cfg.getPropertyBoolean("Test.ComputeSectioningInfo", true), 1390 cfg.getPropertyBoolean("Test.RunChecks", true)); 1391 1392 try { 1393 new StudentSectioningXMLSaver(iSolver).save(new File(new File(cfg.getProperty("General.Output", ".")), "solution.xml")); 1394 } catch (Exception e) { 1395 sLog.error("Unable to save solution, reason: " + e.getMessage(), e); 1396 } 1397 1398 saveInfoToXML(solution, iExtra, new File(new File(cfg.getProperty("General.Output", ".")), "info.xml")); 1399 1400 Progress.removeInstance(solution.getModel()); 1401 } catch (Throwable t) { 1402 sLog.error("Test failed.", t); 1403 } 1404 } 1405 } 1406 1407}