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