001package net.sf.cpsolver.exam; 002 003import java.io.File; 004import java.io.IOException; 005import java.io.PrintWriter; 006import java.util.ArrayList; 007import java.util.HashMap; 008import java.util.HashSet; 009import java.util.List; 010import java.util.Locale; 011import java.util.Map; 012import java.util.Set; 013 014import net.sf.cpsolver.exam.model.Exam; 015import net.sf.cpsolver.exam.model.ExamModel; 016import net.sf.cpsolver.exam.model.ExamRoom; 017import net.sf.cpsolver.exam.model.ExamRoomPlacement; 018import net.sf.cpsolver.exam.model.ExamStudent; 019import net.sf.cpsolver.ifs.util.DataProperties; 020import net.sf.cpsolver.ifs.util.Progress; 021import net.sf.cpsolver.ifs.util.ToolBox; 022 023import org.dom4j.io.SAXReader; 024 025/** 026 * A simple program that prints a few statistics about the given examination problem in the format of the MISTA 2013 paper 027 * (entitled Real-life Examination Timetabling). 028 * It outputs data for the Table 1 (characteristics of the data sets) and Table 2 (number of rooms and exams of a certain size). 029 * <br> 030 * Usage: 031 * <code>java -cp cpsolver-all-1.2.jar net.sf.cpsolver.exam.MistaTables problem1.xml problem2.xml ...</code> 032 * <br> 033 * <br> 034 * 035 * @version ExamTT 1.2 (Examination Timetabling)<br> 036 * Copyright (C) 2008 - 2010 Tomáš Müller<br> 037 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 038 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 039 * <br> 040 * This library is free software; you can redistribute it and/or modify 041 * it under the terms of the GNU Lesser General Public License as 042 * published by the Free Software Foundation; either version 3 of the 043 * License, or (at your option) any later version. <br> 044 * <br> 045 * This library is distributed in the hope that it will be useful, but 046 * WITHOUT ANY WARRANTY; without even the implied warranty of 047 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 048 * Lesser General Public License for more details. <br> 049 * <br> 050 * You should have received a copy of the GNU Lesser General Public 051 * License along with this library; if not see 052 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 053 */ 054public class MistaTables { 055 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(MistaTables.class); 056 private static java.text.DecimalFormat sNF = new java.text.DecimalFormat("###,##0", new java.text.DecimalFormatSymbols(Locale.US)); 057 private static java.text.DecimalFormat sDF = new java.text.DecimalFormat("###,##0.000", new java.text.DecimalFormatSymbols(Locale.US)); 058 059 public static void main(String[] args) { 060 try { 061 ToolBox.configureLogging(); 062 DataProperties config = new DataProperties(); 063 064 Table[] tables = new Table[] { new Problems(), new Rooms() }; 065 066 for (int i = 0; i < args.length; i++) { 067 File file = new File(args[i]); 068 sLog.info("Loading " + file); 069 ExamModel model = new ExamModel(config); 070 model.load(new SAXReader().read(file)); 071 072 String name = file.getName(); 073 if (name.contains(".")) 074 name = name.substring(0, name.indexOf('.')); 075 076 for (Table table: tables) 077 table.add(name, model); 078 079 Progress.removeInstance(model); 080 } 081 082 sLog.info("Saving tables..."); 083 File output = new File("tables"); output.mkdir(); 084 for (Table table: tables) 085 table.save(output); 086 087 sLog.info("All done."); 088 } catch (Exception e) { 089 sLog.error(e.getMessage(), e); 090 } 091 } 092 093 public static class Counter { 094 private double iTotal = 0.0, iMin = 0.0, iMax = 0.0, iTotalSquare = 0.0; 095 private int iCount = 0; 096 097 public Counter() { 098 } 099 100 public void inc(double value) { 101 if (iCount == 0) { 102 iTotal = value; 103 iMin = value; 104 iMax = value; 105 iTotalSquare = value * value; 106 } else { 107 iTotal += value; 108 iMin = Math.min(iMin, value); 109 iMax = Math.max(iMax, value); 110 iTotalSquare += value * value; 111 } 112 iCount ++; 113 } 114 115 public int count() { return iCount; } 116 public double sum() { return iTotal; } 117 public double min() { return iMin; } 118 public double max() { return iMax; } 119 public double rms() { return (iCount == 0 ? 0.0 : Math.sqrt(iTotalSquare / iCount) - Math.abs(avg())); } 120 public double avg() { return (iCount == 0 ? 0.0 : iTotal / iCount); } 121 122 @Override 123 public String toString() { 124 return sDF.format(sum()) + 125 " (min: " + sDF.format(min()) + 126 ", max: " + sDF.format(max()) + 127 ", avg: " + sDF.format(avg()) + 128 ", rms: " + sDF.format(rms()) + 129 ", cnt: " + count() + ")"; 130 } 131 } 132 133 public static abstract class Table { 134 private List<String> iProblems = new ArrayList<String>(); 135 private List<String> iProperties = new ArrayList<String>(); 136 private Map<String, Map<String, String>> iData = new HashMap<String, Map<String, String>>(); 137 138 public abstract void add(String problem, ExamModel model); 139 140 141 protected void add(String problem, String property, int value) { 142 add(problem, property, sNF.format(value)); 143 } 144 145 protected void add(String problem, String property, double value) { 146 add(problem, property, sDF.format(value)); 147 } 148 149 protected void add(String problem, String property, Counter value) { 150 add(problem, property, sDF.format(value.avg()) + " ?? " + sDF.format(value.rms())); 151 } 152 153 protected void add(String problem, String property, String value) { 154 if (!iProblems.contains(problem)) iProblems.add(problem); 155 if (!iProperties.contains(property)) iProperties.add(property); 156 Map<String, String> table = iData.get(problem); 157 if (table == null) { 158 table = new HashMap<String, String>(); 159 iData.put(problem, table); 160 } 161 table.put(property, value); 162 } 163 164 public void save(File folder) throws IOException { 165 PrintWriter pw = new PrintWriter(new File(folder, getClass().getSimpleName() + ".csv")); 166 167 pw.print("Problem"); 168 for (String problem: iProblems) pw.print(",\"" + problem + "\""); 169 pw.println(); 170 171 for (String property: iProperties) { 172 pw.print("\"" + property + "\""); 173 for (String problem: iProblems) { 174 String value = iData.get(problem).get(property); 175 pw.print("," + (value == null ? "" : "\"" + value + "\"")); 176 } 177 pw.println(); 178 } 179 180 pw.flush(); pw.close(); 181 } 182 } 183 184 public static class Problems extends Table { 185 @Override 186 public void add(String problem, ExamModel model) { 187 int enrollments = 0; 188 for (ExamStudent student: model.getStudents()) 189 enrollments += student.variables().size(); 190 191 int examSeating = 0; 192 int examsFixedInTime = 0, examsFixedInRoom = 0, examsLarge = 0, examsToSplit = 0, examsWithOriginalRoom = 0; 193 Counter avgPeriods = new Counter(), avgRooms = new Counter(), avgBigRooms = new Counter(); 194 double density = 0; 195 196 for (Exam exam: model.variables()) { 197 if (exam.hasAltSeating()) examSeating ++; 198 199 if (exam.getPeriodPlacements().size() <= 2) 200 examsFixedInTime ++; 201 if (exam.getRoomPlacements().size() <= 2) 202 examsFixedInRoom ++; 203 204 for (ExamRoomPlacement room: exam.getRoomPlacements()) { 205 if (room.getPenalty() < -2) { examsWithOriginalRoom ++; break; } 206 } 207 208 int bigEnoughRooms = 0; 209 for (ExamRoomPlacement room: exam.getRoomPlacements()) { 210 if (room.getSize(exam.hasAltSeating()) >= exam.getSize()) bigEnoughRooms ++; 211 } 212 213 if (bigEnoughRooms == 0) 214 examsToSplit ++; 215 216 if (exam.getSize() >= 600) 217 examsLarge ++; 218 219 avgPeriods.inc(exam.getPeriodPlacements().size()); 220 avgRooms.inc(exam.getRoomPlacements().size()); 221 avgBigRooms.inc(bigEnoughRooms); 222 223 density += exam.nrStudentCorrelatedExams(); 224 } 225 226 add(problem, "Exams", model.variables().size()); 227 add(problem, " with exam seating", examSeating); 228 add(problem, "Students", model.getStudents().size()); 229 add(problem, "Enrollments", enrollments); 230 add(problem, "Distribution constraints", model.getDistributionConstraints().size()); 231 232 add(problem, "Exams fixed in time", examsFixedInTime); 233 add(problem, "Exams fixed in room", examsFixedInRoom); 234 add(problem, "Large exams (600+)", examsLarge); 235 add(problem, "Exams needing a room split", examsToSplit); 236 add(problem, "Exams with original room", examsWithOriginalRoom); 237 add(problem, "Density", sDF.format(100.0 * density / (model.variables().size() * (model.variables().size() - 1))) + "%"); 238 239 add(problem, "Average periods", avgPeriods); 240 add(problem, "Average rooms", avgRooms); 241 add(problem, " that are big enough", avgBigRooms); 242 } 243 } 244 245 public static class Rooms extends Table { 246 @Override 247 public void add(String problem, ExamModel model) { 248 int[] sizes = new int[] { 0, 100, 200, 400, 600 }; 249 int[] nrRooms = new int[] { 0, 0, 0, 0, 0 }, nrRoomsAlt = new int[] { 0, 0, 0, 0, 0 }; 250 int[] nrExams = new int[] { 0, 0, 0, 0, 0 }, nrExamsAlt = new int[] { 0, 0, 0, 0, 0 }; 251 double[] density = new double[] { 0, 0, 0, 0, 0 }; 252 253 Set<ExamRoom> rooms = new HashSet<ExamRoom>(); 254 for (Exam exam: model.variables()) { 255 for (ExamRoomPlacement room: exam.getRoomPlacements()) { 256 if (rooms.add(room.getRoom())) { 257 for (int i = 0; i < sizes.length; i++) { 258 if (room.getRoom().getSize() >= sizes[i]) 259 nrRooms[i] ++; 260 if (room.getRoom().getAltSize() >= sizes[i]) 261 nrRoomsAlt[i] ++; 262 } 263 } 264 } 265 266 for (int i = 0; i < sizes.length; i++) { 267 if (exam.getSize() >= sizes[i]) { 268 nrExams[i] ++; 269 if (exam.hasAltSeating()) 270 nrExamsAlt[i] ++; 271 for (Exam x: exam.getStudentCorrelatedExams()) 272 if (x.getSize() >= sizes[i]) 273 density[i] ++; 274 } 275 } 276 } 277 278 for (int i = 0; i < sizes.length; i++) { 279 add(problem, "Rooms" + (sizes[i] == 0 ? "" : " (??? " + sizes[i] + " seats)"), sNF.format(nrRooms[i]) + (sizes[i] == 0 ? "" : " (" + sNF.format(nrRoomsAlt[i]) + ")")); 280 } 281 for (int i = 0; i < sizes.length; i++) { 282 add(problem, "Exams" + (sizes[i] == 0 ? "" : " (??? " + sizes[i] + " seats)"), sNF.format(nrExams[i]) + (sizes[i] == 0 ? "" : " (" + sNF.format(nrExamsAlt[i]) + ")")); 283 } 284 for (int i = 0; i < sizes.length; i++) { 285 add(problem, "Density" + (sizes[i] == 0 ? "" : " (??? " + sizes[i] + " seats)"), sDF.format(100.0 * density[i] / (nrExams[i] * (nrExams[i] - 1))) + "%"); 286 } 287 } 288 } 289 290}