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