001 package net.sf.cpsolver.exam;
002
003 import java.io.File;
004 import java.io.IOException;
005 import java.io.PrintWriter;
006 import java.util.ArrayList;
007 import java.util.HashMap;
008 import java.util.HashSet;
009 import java.util.List;
010 import java.util.Locale;
011 import java.util.Map;
012 import java.util.Set;
013
014 import net.sf.cpsolver.exam.model.Exam;
015 import net.sf.cpsolver.exam.model.ExamModel;
016 import net.sf.cpsolver.exam.model.ExamRoom;
017 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
018 import net.sf.cpsolver.exam.model.ExamStudent;
019 import net.sf.cpsolver.ifs.util.DataProperties;
020 import net.sf.cpsolver.ifs.util.Progress;
021 import net.sf.cpsolver.ifs.util.ToolBox;
022
023 import 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 Tomas Muller<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 */
054 public 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 }