001 package net.sf.cpsolver.exam; 002 003 import java.io.File; 004 import java.io.FileInputStream; 005 import java.io.FileOutputStream; 006 import java.io.FileWriter; 007 import java.io.IOException; 008 import java.io.PrintWriter; 009 import java.text.DecimalFormat; 010 import java.util.Collection; 011 import java.util.Map; 012 013 import net.sf.cpsolver.exam.criteria.DistributionPenalty; 014 import net.sf.cpsolver.exam.criteria.ExamRotationPenalty; 015 import net.sf.cpsolver.exam.criteria.InstructorBackToBackConflicts; 016 import net.sf.cpsolver.exam.criteria.InstructorDirectConflicts; 017 import net.sf.cpsolver.exam.criteria.InstructorDistanceBackToBackConflicts; 018 import net.sf.cpsolver.exam.criteria.InstructorMoreThan2ADayConflicts; 019 import net.sf.cpsolver.exam.criteria.InstructorNotAvailableConflicts; 020 import net.sf.cpsolver.exam.criteria.LargeExamsPenalty; 021 import net.sf.cpsolver.exam.criteria.PeriodPenalty; 022 import net.sf.cpsolver.exam.criteria.PerturbationPenalty; 023 import net.sf.cpsolver.exam.criteria.RoomPenalty; 024 import net.sf.cpsolver.exam.criteria.RoomSizePenalty; 025 import net.sf.cpsolver.exam.criteria.RoomSplitDistancePenalty; 026 import net.sf.cpsolver.exam.criteria.RoomSplitPenalty; 027 import net.sf.cpsolver.exam.criteria.StudentBackToBackConflicts; 028 import net.sf.cpsolver.exam.criteria.StudentDirectConflicts; 029 import net.sf.cpsolver.exam.criteria.StudentDistanceBackToBackConflicts; 030 import net.sf.cpsolver.exam.criteria.StudentMoreThan2ADayConflicts; 031 import net.sf.cpsolver.exam.criteria.StudentNotAvailableConflicts; 032 import net.sf.cpsolver.exam.model.Exam; 033 import net.sf.cpsolver.exam.model.ExamDistributionConstraint; 034 import net.sf.cpsolver.exam.model.ExamInstructor; 035 import net.sf.cpsolver.exam.model.ExamModel; 036 import net.sf.cpsolver.exam.model.ExamPeriod; 037 import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 038 import net.sf.cpsolver.exam.model.ExamPlacement; 039 import net.sf.cpsolver.exam.model.ExamRoom; 040 import net.sf.cpsolver.exam.model.ExamRoomPlacement; 041 import net.sf.cpsolver.exam.model.ExamStudent; 042 import net.sf.cpsolver.exam.reports.ExamAssignments; 043 import net.sf.cpsolver.exam.reports.ExamCourseSectionAssignments; 044 import net.sf.cpsolver.exam.reports.ExamInstructorConflicts; 045 import net.sf.cpsolver.exam.reports.ExamNbrMeetingsPerDay; 046 import net.sf.cpsolver.exam.reports.ExamPeriodUsage; 047 import net.sf.cpsolver.exam.reports.ExamRoomSchedule; 048 import net.sf.cpsolver.exam.reports.ExamRoomSplit; 049 import net.sf.cpsolver.exam.reports.ExamStudentBackToBackConflicts; 050 import net.sf.cpsolver.exam.reports.ExamStudentConflicts; 051 import net.sf.cpsolver.exam.reports.ExamStudentConflictsBySectionCourse; 052 import net.sf.cpsolver.exam.reports.ExamStudentConflictsPerExam; 053 import net.sf.cpsolver.exam.reports.ExamStudentDirectConflicts; 054 import net.sf.cpsolver.exam.reports.ExamStudentMoreTwoADay; 055 import net.sf.cpsolver.ifs.solution.Solution; 056 import net.sf.cpsolver.ifs.solution.SolutionListener; 057 import net.sf.cpsolver.ifs.solver.Solver; 058 import net.sf.cpsolver.ifs.util.DataProperties; 059 import net.sf.cpsolver.ifs.util.Progress; 060 import net.sf.cpsolver.ifs.util.ToolBox; 061 062 import org.apache.log4j.ConsoleAppender; 063 import org.apache.log4j.FileAppender; 064 import org.apache.log4j.Level; 065 import org.apache.log4j.Logger; 066 import org.apache.log4j.PatternLayout; 067 import org.dom4j.Document; 068 import org.dom4j.io.OutputFormat; 069 import org.dom4j.io.SAXReader; 070 import org.dom4j.io.XMLWriter; 071 072 /** 073 * An examination timetabling test program. The following steps are performed: 074 * <ul> 075 * <li>Input properties are loaded 076 * <li>Input problem is loaded (General.Input property) 077 * <li>Problem is solved (using the given properties) 078 * <li>Solution is save (General.OutputFile property) 079 * </ul> 080 * <br> 081 * <br> 082 * Usage: <code> 083 * java -Xmx1024m -jar examtt-1.1.jar exam.properties input.xml output.xml 084 * </code> <br> 085 * <br> 086 * 087 * @version ExamTT 1.2 (Examination Timetabling)<br> 088 * Copyright (C) 2007 - 2010 Tomas Muller<br> 089 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 090 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 091 * <br> 092 * This library is free software; you can redistribute it and/or modify 093 * it under the terms of the GNU Lesser General Public License as 094 * published by the Free Software Foundation; either version 3 of the 095 * License, or (at your option) any later version. <br> 096 * <br> 097 * This library is distributed in the hope that it will be useful, but 098 * WITHOUT ANY WARRANTY; without even the implied warranty of 099 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 100 * Lesser General Public License for more details. <br> 101 * <br> 102 * You should have received a copy of the GNU Lesser General Public 103 * License along with this library; if not see 104 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 105 */ 106 public class Test { 107 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(Test.class); 108 109 /** 110 * Setup log4j logging 111 * 112 * @param logFile 113 * log file 114 * @param debug 115 * true if debug messages should be logged (use -Ddebug=true to 116 * enable debug message) 117 */ 118 public static void setupLogging(File logFile, boolean debug) { 119 Logger root = Logger.getRootLogger(); 120 ConsoleAppender console = new ConsoleAppender(new PatternLayout("%m%n"));// %-5p 121 // %c{1}> 122 // %m%n 123 console.setThreshold(Level.INFO); 124 root.addAppender(console); 125 if (logFile != null) { 126 try { 127 FileAppender file = new FileAppender(new PatternLayout( 128 "%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n"), logFile.getPath(), false); 129 file.setThreshold(Level.DEBUG); 130 root.addAppender(file); 131 } catch (IOException e) { 132 sLog.fatal("Unable to configure logging, reason: " + e.getMessage(), e); 133 } 134 } 135 if (!debug) 136 root.setLevel(Level.INFO); 137 } 138 139 /** Generate exam reports */ 140 public static void createReports(ExamModel model, File outDir, String outName) throws IOException { 141 new ExamAssignments(model).report().save(new File(outDir, outName + ".schdex.csv")); 142 143 new ExamCourseSectionAssignments(model).report().save(new File(outDir, outName + ".schdcs.csv")); 144 145 new ExamStudentConflicts(model).report().save(new File(outDir, outName + ".sconf.csv")); 146 147 new ExamInstructorConflicts(model).report().save(new File(outDir, outName + ".iconf.csv")); 148 149 new ExamStudentConflictsPerExam(model).report().save(new File(outDir, outName + ".sconfex.csv")); 150 151 new ExamStudentDirectConflicts(model).report().save(new File(outDir, outName + ".sdir.csv")); 152 153 new ExamStudentBackToBackConflicts(model).report().save(new File(outDir, outName + ".sbtb.csv")); 154 155 new ExamStudentMoreTwoADay(model).report().save(new File(outDir, outName + ".sm2d.csv")); 156 157 new ExamPeriodUsage(model).report().save(new File(outDir, outName + ".per.csv")); 158 159 new ExamRoomSchedule(model).report().save(new File(outDir, outName + ".schdr.csv")); 160 161 new ExamRoomSplit(model).report().save(new File(outDir, outName + ".rsplit.csv")); 162 163 new ExamNbrMeetingsPerDay(model).report().save(new File(outDir, outName + ".distmpd.csv")); 164 165 new ExamStudentConflictsBySectionCourse(model).report().save(new File(outDir, outName + ".sconfcs.csv")); 166 } 167 168 public static class ShutdownHook extends Thread { 169 Solver<Exam, ExamPlacement> iSolver = null; 170 171 public ShutdownHook(Solver<Exam, ExamPlacement> solver) { 172 setName("ShutdownHook"); 173 iSolver = solver; 174 } 175 176 @Override 177 public void run() { 178 try { 179 if (iSolver.isRunning()) 180 iSolver.stopSolver(); 181 Solution<Exam, ExamPlacement> solution = iSolver.lastSolution(); 182 Progress.removeInstance(solution.getModel()); 183 if (solution.getBestInfo() == null) { 184 sLog.error("No best solution found."); 185 } else 186 solution.restoreBest(); 187 188 sLog.info("Best solution:" + ToolBox.dict2string(solution.getExtendedInfo(), 1)); 189 190 sLog.info("Best solution found after " + solution.getBestTime() + " seconds (" 191 + solution.getBestIteration() + " iterations)."); 192 sLog.info("Number of assigned variables is " + solution.getModel().nrAssignedVariables()); 193 sLog.info("Total value of the solution is " + solution.getModel().getTotalValue()); 194 195 File outFile = new File(iSolver.getProperties().getProperty("General.OutputFile", 196 iSolver.getProperties().getProperty("General.Output") + File.separator + "solution.xml")); 197 FileOutputStream fos = new FileOutputStream(outFile); 198 (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(((ExamModel) solution.getModel()).save()); 199 fos.flush(); 200 fos.close(); 201 202 if ("true".equals(System.getProperty("reports", "false"))) 203 createReports((ExamModel) solution.getModel(), outFile.getParentFile(), outFile.getName() 204 .substring(0, outFile.getName().lastIndexOf('.'))); 205 206 String baseName = new File(iSolver.getProperties().getProperty("General.Input")).getName(); 207 if (baseName.indexOf('.') > 0) 208 baseName = baseName.substring(0, baseName.lastIndexOf('.')); 209 addCSVLine(new File(outFile.getParentFile(), baseName + ".csv"), outFile.getName(), solution); 210 211 } catch (Exception e) { 212 e.printStackTrace(); 213 } 214 } 215 } 216 217 private static int getMinPenalty(ExamRoom r) { 218 int min = Integer.MAX_VALUE; 219 for (ExamPeriod p : ((ExamModel) r.getModel()).getPeriods()) { 220 if (r.isAvailable(p)) { 221 min = Math.min(min, r.getPenalty(p)); 222 } 223 } 224 return min; 225 } 226 227 private static int getMaxPenalty(ExamRoom r) { 228 int max = Integer.MIN_VALUE; 229 for (ExamPeriod p : ((ExamModel) r.getModel()).getPeriods()) { 230 if (r.isAvailable(p)) { 231 max = Math.max(max, r.getPenalty(p)); 232 } 233 } 234 return max; 235 } 236 237 private static void addCSVLine(File file, String instance, Solution<Exam, ExamPlacement> solution) { 238 try { 239 ExamModel model = (ExamModel) solution.getModel(); 240 boolean ex = file.exists(); 241 PrintWriter pw = new PrintWriter(new FileWriter(file, true)); 242 boolean mpp = ((PerturbationPenalty)model.getCriterion(PerturbationPenalty.class)).isMPP(); 243 int largeSize = ((LargeExamsPenalty)model.getCriterion(LargeExamsPenalty.class)).getLargeSize(); 244 if (!ex) { 245 pw.println("SEED," + "DC,sM2D,BTB," + (model.getBackToBackDistance() < 0 ? "" : "dBTB,") 246 + "iDC,iM2D,iBTB," + (model.getBackToBackDistance() < 0 ? "" : "diBTB,") 247 + "PP,@P,RSz,RSp,RD,RP,DP," + (largeSize >= 0 ? ",LP" : "") 248 + (mpp ? ",IP" : "") + ",INSTANCE"); 249 int minPeriodPenalty = 0, maxPeriodPenalty = 0; 250 int minRoomPenalty = 0, maxRoomPenalty = 0; 251 int nrLargeExams = 0; 252 for (Exam exam : model.variables()) { 253 if (largeSize >= 0 && exam.getSize() >= largeSize) 254 nrLargeExams++; 255 if (!exam.getPeriodPlacements().isEmpty()) { 256 int minPenalty = Integer.MAX_VALUE, maxPenalty = Integer.MIN_VALUE; 257 for (ExamPeriodPlacement periodPlacement : exam.getPeriodPlacements()) { 258 minPenalty = Math.min(minPenalty, periodPlacement.getPenalty()); 259 maxPenalty = Math.max(maxPenalty, periodPlacement.getPenalty()); 260 } 261 minPeriodPenalty += minPenalty; 262 maxPeriodPenalty += maxPenalty; 263 } 264 if (!exam.getRoomPlacements().isEmpty()) { 265 int minPenalty = Integer.MAX_VALUE, maxPenalty = Integer.MIN_VALUE; 266 for (ExamRoomPlacement roomPlacement : exam.getRoomPlacements()) { 267 minPenalty = Math.min(minPenalty, roomPlacement.getPenalty() 268 + getMinPenalty(roomPlacement.getRoom())); 269 maxPenalty = Math.max(maxPenalty, roomPlacement.getPenalty() 270 + getMaxPenalty(roomPlacement.getRoom())); 271 } 272 minRoomPenalty += minPenalty; 273 maxRoomPenalty += maxPenalty; 274 } 275 } 276 int maxDistributionPenalty = 0; 277 for (ExamDistributionConstraint dc : model.getDistributionConstraints()) { 278 if (dc.isHard()) 279 continue; 280 maxDistributionPenalty += dc.getWeight(); 281 } 282 int nrStudentExams = 0; 283 for (ExamStudent student : model.getStudents()) { 284 nrStudentExams += student.variables().size(); 285 } 286 int nrInstructorExams = 0; 287 for (ExamInstructor instructor : model.getInstructors()) { 288 nrInstructorExams += instructor.variables().size(); 289 } 290 pw 291 .println("MIN," + "#EX,#RM,#PER," + (model.getBackToBackDistance() < 0 ? "" : ",") 292 + "#STD,#STDX,," + (model.getBackToBackDistance() < 0 ? "" : ",") + minPeriodPenalty 293 + ",#INS,#INSX,,," + minRoomPenalty + ",0," + (largeSize >= 0 ? ",0" : "") 294 + (mpp ? "," : "")); 295 pw.println("MAX," + model.variables().size() + "," + model.getRooms().size() + "," 296 + model.getPeriods().size() + "," + (model.getBackToBackDistance() < 0 ? "" : ",") 297 + model.getStudents().size() + "," + nrStudentExams + ",," 298 + (model.getBackToBackDistance() < 0 ? "" : ",") + maxPeriodPenalty + "," 299 + model.getInstructors().size() + "," + nrInstructorExams + ",,," + maxRoomPenalty + "," 300 + maxDistributionPenalty + "," + (largeSize >= 0 ? "," + nrLargeExams : "") 301 + (mpp ? "," : "")); 302 } 303 DecimalFormat df = new DecimalFormat("0.00"); 304 pw.println(ToolBox.getSeed() 305 + "," 306 + (model.getCriterion(StudentDirectConflicts.class).getValue() + model.getCriterion(StudentNotAvailableConflicts.class).getValue()) 307 + "," 308 + model.getCriterion(StudentMoreThan2ADayConflicts.class).getValue() 309 + "," 310 + model.getCriterion(StudentBackToBackConflicts.class).getValue() 311 + "," 312 + (model.getBackToBackDistance() < 0 ? "" : model.getCriterion(StudentDistanceBackToBackConflicts.class).getValue() + ",") 313 + (model.getCriterion(InstructorDirectConflicts.class).getValue() + model.getCriterion(InstructorNotAvailableConflicts.class).getValue()) 314 + "," 315 + model.getCriterion(InstructorMoreThan2ADayConflicts.class).getValue() 316 + "," 317 + model.getCriterion(InstructorBackToBackConflicts.class).getValue() 318 + "," 319 + (model.getBackToBackDistance() < 0 ? "" : model.getCriterion(InstructorDistanceBackToBackConflicts.class).getValue() + ",") 320 + model.getCriterion(PeriodPenalty.class).getWeight() 321 + "," 322 + model.getCriterion(ExamRotationPenalty.class).getValue() 323 + "," 324 + df.format(model.getCriterion(RoomSizePenalty.class).getValue() / model.nrAssignedVariables()) 325 + "," 326 + model.getCriterion(RoomSplitPenalty.class).getValue() 327 + "," 328 + df.format(model.getCriterion(RoomSplitDistancePenalty.class).getValue() / model.getCriterion(RoomSplitPenalty.class).getValue()) 329 + "," 330 + model.getCriterion(RoomPenalty.class).getValue() 331 + "," 332 + model.getCriterion(DistributionPenalty.class).getValue() 333 + (largeSize >= 0 ? "," + model.getCriterion(LargeExamsPenalty.class).getValue() : "") 334 + (mpp ? "," 335 + df.format(model.getCriterion(PerturbationPenalty.class).getValue() / model.nrAssignedVariables()) 336 : "") + "," + instance); 337 pw.flush(); 338 pw.close(); 339 } catch (Exception e) { 340 sLog.error("Unable to add CSV line to " + file, e); 341 } 342 } 343 344 /** 345 * Main program 346 * 347 * @param args 348 * problem property file, input file (optional, may be set by 349 * General.Input property), output file (optional, may be set by 350 * General.OutputFile property) 351 */ 352 public static void main(String[] args) { 353 try { 354 DataProperties cfg = new DataProperties(); 355 cfg.setProperty("Termination.StopWhenComplete", "false"); 356 cfg.setProperty("Termination.TimeOut", "1800"); 357 cfg.setProperty("General.SaveBestUnassigned", "-1"); 358 cfg.setProperty("Neighbour.Class", "net.sf.cpsolver.exam.heuristics.ExamNeighbourSelection"); 359 if (args.length >= 1) { 360 cfg.load(new FileInputStream(args[0])); 361 } 362 cfg.putAll(System.getProperties()); 363 364 File inputFile = new File("c:\\test\\exam\\exam1070.xml"); 365 if (args.length >= 2) { 366 inputFile = new File(args[1]); 367 } 368 ToolBox.setSeed(cfg.getPropertyLong("General.Seed", Math.round(Long.MAX_VALUE * Math.random()))); 369 370 cfg.setProperty("General.Input", inputFile.toString()); 371 372 String outName = inputFile.getName(); 373 if (outName.indexOf('.') >= 0) 374 outName = outName.substring(0, outName.lastIndexOf('.')) + "s.xml"; 375 File outFile = new File(inputFile.getParentFile(), outName); 376 if (args.length >= 3) { 377 outFile = new File(args[2]); 378 if (outFile.exists() && outFile.isDirectory()) 379 outFile = new File(outFile, outName); 380 if (!outFile.exists() && !outFile.getName().endsWith(".xml")) 381 outFile = new File(outFile, outName); 382 } 383 if (outFile.getParentFile() != null) 384 outFile.getParentFile().mkdirs(); 385 cfg.setProperty("General.OutputFile", outFile.toString()); 386 cfg.setProperty("General.Output", outFile.getParent()); 387 388 String logName = outFile.getName(); 389 if (logName.indexOf('.') >= 0) 390 logName = logName.substring(0, logName.lastIndexOf('.')) + ".log"; 391 setupLogging(new File(outFile.getParent(), logName), "true".equals(System.getProperty("debug", "false"))); 392 393 ExamModel model = new ExamModel(cfg); 394 395 Document document = (new SAXReader()).read(new File(cfg.getProperty("General.Input"))); 396 model.load(document); 397 398 sLog.info("Loaded model: " + ToolBox.dict2string(model.getExtendedInfo(), 2)); 399 400 Solver<Exam, ExamPlacement> solver = new Solver<Exam, ExamPlacement>(cfg); 401 solver.setInitalSolution(new Solution<Exam, ExamPlacement>(model)); 402 403 solver.currentSolution().addSolutionListener(new SolutionListener<Exam, ExamPlacement>() { 404 @Override 405 public void solutionUpdated(Solution<Exam, ExamPlacement> solution) { 406 } 407 408 @Override 409 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) { 410 } 411 412 @Override 413 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, 414 Collection<Exam> variables) { 415 } 416 417 @Override 418 public void bestCleared(Solution<Exam, ExamPlacement> solution) { 419 } 420 421 @Override 422 public void bestSaved(Solution<Exam, ExamPlacement> solution) { 423 ExamModel m = (ExamModel) solution.getModel(); 424 if (sLog.isInfoEnabled()) { 425 sLog.info("**BEST[" 426 + solution.getIteration() 427 + "]** " 428 + (m.nrUnassignedVariables() > 0 ? "V:" + m.nrAssignedVariables() + "/" 429 + m.variables().size() + " - " : "") + "T:" 430 + new DecimalFormat("0.00").format(m.getTotalValue()) + " (" + m + ")"); 431 } 432 } 433 434 @Override 435 public void bestRestored(Solution<Exam, ExamPlacement> solution) { 436 } 437 }); 438 439 Runtime.getRuntime().addShutdownHook(new ShutdownHook(solver)); 440 441 solver.start(); 442 try { 443 solver.getSolverThread().join(); 444 } catch (InterruptedException e) { 445 } 446 } catch (Exception e) { 447 e.printStackTrace(); 448 } 449 } 450 }