001package org.cpsolver.studentsct;
002
003import java.io.BufferedReader;
004import java.io.File;
005import java.io.FileInputStream;
006import java.io.FileOutputStream;
007import java.io.FileReader;
008import java.io.FileWriter;
009import java.io.IOException;
010import java.io.PrintWriter;
011import java.text.DecimalFormat;
012import java.util.ArrayList;
013import java.util.Collection;
014import java.util.Collections;
015import java.util.Comparator;
016import java.util.Date;
017import java.util.HashSet;
018import java.util.HashMap;
019import java.util.Iterator;
020import java.util.List;
021import java.util.Map;
022import java.util.Set;
023import java.util.StringTokenizer;
024import java.util.TreeSet;
025
026
027import org.apache.log4j.ConsoleAppender;
028import org.apache.log4j.FileAppender;
029import org.apache.log4j.Level;
030import org.apache.log4j.Logger;
031import org.apache.log4j.PatternLayout;
032import org.cpsolver.ifs.assignment.Assignment;
033import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
034import org.cpsolver.ifs.assignment.EmptyAssignment;
035import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection;
036import org.cpsolver.ifs.model.Neighbour;
037import org.cpsolver.ifs.solution.Solution;
038import org.cpsolver.ifs.solution.SolutionListener;
039import org.cpsolver.ifs.solver.ParallelSolver;
040import org.cpsolver.ifs.solver.Solver;
041import org.cpsolver.ifs.solver.SolverListener;
042import org.cpsolver.ifs.util.DataProperties;
043import org.cpsolver.ifs.util.JProf;
044import org.cpsolver.ifs.util.Progress;
045import org.cpsolver.ifs.util.ProgressWriter;
046import org.cpsolver.ifs.util.ToolBox;
047import org.cpsolver.studentsct.check.CourseLimitCheck;
048import org.cpsolver.studentsct.check.InevitableStudentConflicts;
049import org.cpsolver.studentsct.check.OverlapCheck;
050import org.cpsolver.studentsct.check.SectionLimitCheck;
051import org.cpsolver.studentsct.extension.DistanceConflict;
052import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
053import org.cpsolver.studentsct.filter.CombinedStudentFilter;
054import org.cpsolver.studentsct.filter.FreshmanStudentFilter;
055import org.cpsolver.studentsct.filter.RandomStudentFilter;
056import org.cpsolver.studentsct.filter.ReverseStudentFilter;
057import org.cpsolver.studentsct.filter.StudentFilter;
058import org.cpsolver.studentsct.heuristics.StudentSctNeighbourSelection;
059import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
060import org.cpsolver.studentsct.heuristics.selection.OnlineSelection;
061import org.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
062import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour;
063import org.cpsolver.studentsct.heuristics.studentord.StudentOrder;
064import org.cpsolver.studentsct.heuristics.studentord.StudentRandomOrder;
065import org.cpsolver.studentsct.model.AcademicAreaCode;
066import org.cpsolver.studentsct.model.Course;
067import org.cpsolver.studentsct.model.CourseRequest;
068import org.cpsolver.studentsct.model.Enrollment;
069import org.cpsolver.studentsct.model.Offering;
070import org.cpsolver.studentsct.model.Request;
071import org.cpsolver.studentsct.model.Student;
072import org.cpsolver.studentsct.report.CourseConflictTable;
073import org.cpsolver.studentsct.report.DistanceConflictTable;
074import org.cpsolver.studentsct.report.RequestGroupTable;
075import org.cpsolver.studentsct.report.SectionConflictTable;
076import org.cpsolver.studentsct.report.TimeOverlapConflictTable;
077import org.cpsolver.studentsct.report.UnbalancedSectionsTable;
078import org.dom4j.Document;
079import org.dom4j.DocumentHelper;
080import org.dom4j.Element;
081import org.dom4j.io.OutputFormat;
082import org.dom4j.io.SAXReader;
083import org.dom4j.io.XMLWriter;
084
085/**
086 * A main class for running of the student sectioning solver from command line. <br>
087 * <br>
088 * Usage:<br>
089 * java -Xmx1024m -jar studentsct-1.1.jar config.properties [input_file]
090 * [output_folder] [batch|online|simple]<br>
091 * <br>
092 * Modes:<br>
093 * &nbsp;&nbsp;batch ... batch sectioning mode (default mode -- IFS solver with
094 * {@link StudentSctNeighbourSelection} is used)<br>
095 * &nbsp;&nbsp;online ... online sectioning mode (students are sectioned one by
096 * one, sectioning info (expected/held space) is used)<br>
097 * &nbsp;&nbsp;simple ... simple sectioning mode (students are sectioned one by
098 * one, sectioning info is not used)<br>
099 * See http://www.unitime.org for example configuration files and benchmark data
100 * sets.<br>
101 * <br>
102 * 
103 * The test does the following steps:
104 * <ul>
105 * <li>Provided property file is loaded (see {@link DataProperties}).
106 * <li>Output folder is created (General.Output property) and logging is setup
107 * (using log4j).
108 * <li>Input data are loaded from the given XML file (calling
109 * {@link StudentSectioningXMLLoader#load()}).
110 * <li>Solver is executed (see {@link Solver}).
111 * <li>Resultant solution is saved to an XML file (calling
112 * {@link StudentSectioningXMLSaver#save()}.
113 * </ul>
114 * Also, a log and some reports (e.g., {@link CourseConflictTable} and
115 * {@link DistanceConflictTable}) are created in the output folder.
116 * 
117 * <br>
118 * <br>
119 * Parameters:
120 * <table border='1' summary='Related Solver Parameters'>
121 * <tr>
122 * <th>Parameter</th>
123 * <th>Type</th>
124 * <th>Comment</th>
125 * </tr>
126 * <tr>
127 * <td>Test.LastLikeCourseDemands</td>
128 * <td>{@link String}</td>
129 * <td>Load last-like course demands from the given XML file (in the format that
130 * is being used for last like course demand table in the timetabling
131 * application)</td>
132 * </tr>
133 * <tr>
134 * <td>Test.StudentInfos</td>
135 * <td>{@link String}</td>
136 * <td>Load last-like course demands from the given XML file (in the format that
137 * is being used for last like course demand table in the timetabling
138 * application)</td>
139 * </tr>
140 * <tr>
141 * <td>Test.CrsReq</td>
142 * <td>{@link String}</td>
143 * <td>Load student requests from the given semi-colon separated list files (in
144 * the format that is being used by the old MSF system)</td>
145 * </tr>
146 * <tr>
147 * <td>Test.EtrChk</td>
148 * <td>{@link String}</td>
149 * <td>Load student information (academic area, classification, major, minor)
150 * from the given semi-colon separated list files (in the format that is being
151 * used by the old MSF system)</td>
152 * </tr>
153 * <tr>
154 * <td>Sectioning.UseStudentPreferencePenalties</td>
155 * <td>{@link Boolean}</td>
156 * <td>If true, {@link StudentPreferencePenalties} are used (applicable only for
157 * online sectioning)</td>
158 * </tr>
159 * <tr>
160 * <td>Test.StudentOrder</td>
161 * <td>{@link String}</td>
162 * <td>A class that is used for ordering of students (must be an interface of
163 * {@link StudentOrder}, default is {@link StudentRandomOrder}, not applicable
164 * only for batch sectioning)</td>
165 * </tr>
166 * <tr>
167 * <td>Test.CombineStudents</td>
168 * <td>{@link File}</td>
169 * <td>If provided, students are combined from the input file (last-like
170 * students) and the provided file (real students). Real non-freshmen students
171 * are taken from real data, last-like data are loaded on top of the real data
172 * (all students, but weighted to occupy only the remaining space).</td>
173 * </tr>
174 * <tr>
175 * <td>Test.CombineStudentsLastLike</td>
176 * <td>{@link File}</td>
177 * <td>If provided (together with Test.CombineStudents), students are combined
178 * from the this file (last-like students) and Test.CombineStudents file (real
179 * students). Real non-freshmen students are taken from real data, last-like
180 * data are loaded on top of the real data (all students, but weighted to occupy
181 * only the remaining space).</td>
182 * </tr>
183 * <tr>
184 * <td>Test.CombineAcceptProb</td>
185 * <td>{@link Double}</td>
186 * <td>Used in combining students, probability of a non-freshmen real student to
187 * be taken into the combined file (default is 1.0 -- all real non-freshmen
188 * students are taken).</td>
189 * </tr>
190 * <tr>
191 * <td>Test.FixPriorities</td>
192 * <td>{@link Boolean}</td>
193 * <td>If true, course/free time request priorities are corrected (to go from
194 * zero, without holes or duplicates).</td>
195 * </tr>
196 * <tr>
197 * <td>Test.ExtraStudents</td>
198 * <td>{@link File}</td>
199 * <td>If provided, students are loaded from the given file on top of the
200 * students loaded from the ordinary input file (students with the same id are
201 * skipped).</td>
202 * </tr>
203 * </table>
204 * <br>
205 * <br>
206 * 
207 * @version StudentSct 1.3 (Student Sectioning)<br>
208 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
209 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
210 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
211 * <br>
212 *          This library is free software; you can redistribute it and/or modify
213 *          it under the terms of the GNU Lesser General Public License as
214 *          published by the Free Software Foundation; either version 3 of the
215 *          License, or (at your option) any later version. <br>
216 * <br>
217 *          This library is distributed in the hope that it will be useful, but
218 *          WITHOUT ANY WARRANTY; without even the implied warranty of
219 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
220 *          Lesser General Public License for more details. <br>
221 * <br>
222 *          You should have received a copy of the GNU Lesser General Public
223 *          License along with this library; if not see
224 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
225 */
226
227public class Test {
228    private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(Test.class);
229    private static java.text.SimpleDateFormat sDateFormat = new java.text.SimpleDateFormat("yyMMdd_HHmmss",
230            java.util.Locale.US);
231    private static DecimalFormat sDF = new DecimalFormat("0.000");
232
233    /** Load student sectioning model 
234     * @param cfg solver configuration
235     * @return loaded solution
236     **/
237    public static Solution<Request, Enrollment> load(DataProperties cfg) {
238        StudentSectioningModel model = null;
239        Assignment<Request, Enrollment> assignment = null;
240        try {
241            if (cfg.getProperty("Test.CombineStudents") == null) {
242                model = new StudentSectioningModel(cfg);
243                assignment = new DefaultSingleAssignment<Request, Enrollment>();
244                new StudentSectioningXMLLoader(model, assignment).load();
245            } else {
246                Solution<Request, Enrollment> solution = combineStudents(cfg,
247                        new File(cfg.getProperty("Test.CombineStudentsLastLike", cfg.getProperty("General.Input", "." + File.separator + "solution.xml"))),
248                        new File(cfg.getProperty("Test.CombineStudents")));
249                model = (StudentSectioningModel)solution.getModel();
250                assignment = solution.getAssignment();
251            }
252            if (cfg.getProperty("Test.ExtraStudents") != null) {
253                StudentSectioningXMLLoader extra = new StudentSectioningXMLLoader(model, assignment);
254                extra.setInputFile(new File(cfg.getProperty("Test.ExtraStudents")));
255                extra.setLoadOfferings(false);
256                extra.setLoadStudents(true);
257                extra.setStudentFilter(new ExtraStudentFilter(model));
258                extra.load();
259            }
260            if (cfg.getProperty("Test.LastLikeCourseDemands") != null)
261                loadLastLikeCourseDemandsXml(model, new File(cfg.getProperty("Test.LastLikeCourseDemands")));
262            if (cfg.getProperty("Test.StudentInfos") != null)
263                loadStudentInfoXml(model, new File(cfg.getProperty("Test.StudentInfos")));
264            if (cfg.getProperty("Test.CrsReq") != null)
265                loadCrsReqFiles(model, cfg.getProperty("Test.CrsReq"));
266        } catch (Exception e) {
267            sLog.error("Unable to load model, reason: " + e.getMessage(), e);
268            return null;
269        }
270        if (cfg.getPropertyBoolean("Debug.DistanceConflict", false))
271            DistanceConflict.sDebug = true;
272        if (cfg.getPropertyBoolean("Debug.BranchBoundSelection", false))
273            BranchBoundSelection.sDebug = true;
274        if (cfg.getPropertyBoolean("Debug.SwapStudentsSelection", false))
275            SwapStudentSelection.sDebug = true;
276        if (cfg.getPropertyBoolean("Debug.TimeOverlaps", false))
277            TimeOverlapsCounter.sDebug = true;
278        if (cfg.getProperty("CourseRequest.SameTimePrecise") != null)
279            CourseRequest.sSameTimePrecise = cfg.getPropertyBoolean("CourseRequest.SameTimePrecise", false);
280        Logger.getLogger(BacktrackNeighbourSelection.class).setLevel(
281                cfg.getPropertyBoolean("Debug.BacktrackNeighbourSelection", false) ? Level.DEBUG : Level.INFO);
282        if (cfg.getPropertyBoolean("Test.FixPriorities", false))
283            fixPriorities(model);
284        return new Solution<Request, Enrollment>(model, assignment);
285    }
286
287    /** Batch sectioning test 
288     * @param cfg solver configuration
289     * @return resultant solution
290     **/
291    public static Solution<Request, Enrollment> batchSectioning(DataProperties cfg) {
292        Solution<Request, Enrollment> solution = load(cfg);
293        if (solution == null)
294            return null;
295        StudentSectioningModel model = (StudentSectioningModel)solution.getModel();
296
297        if (cfg.getPropertyBoolean("Test.ComputeSectioningInfo", true))
298            model.clearOnlineSectioningInfos();
299        
300        Progress.getInstance(model).addProgressListener(new ProgressWriter(System.out));
301
302        solve(solution, cfg);
303
304        return solution;
305    }
306
307    /** Online sectioning test 
308     * @param cfg solver configuration
309     * @return resultant solution
310     * @throws Exception thrown when the sectioning fails
311     **/
312    public static Solution<Request, Enrollment> onlineSectioning(DataProperties cfg) throws Exception {
313        Solution<Request, Enrollment> solution = load(cfg);
314        if (solution == null)
315            return null;
316        StudentSectioningModel model = (StudentSectioningModel)solution.getModel();
317        Assignment<Request, Enrollment> assignment = solution.getAssignment();
318
319        solution.addSolutionListener(new TestSolutionListener());
320        double startTime = JProf.currentTimeSec();
321
322        Solver<Request, Enrollment> solver = new Solver<Request, Enrollment>(cfg);
323        solver.setInitalSolution(solution);
324        solver.initSolver();
325
326        OnlineSelection onlineSelection = new OnlineSelection(cfg);
327        onlineSelection.init(solver);
328
329        double totalPenalty = 0, minPenalty = 0, maxPenalty = 0;
330        double minAvEnrlPenalty = 0, maxAvEnrlPenalty = 0;
331        double totalPrefPenalty = 0, minPrefPenalty = 0, maxPrefPenalty = 0;
332        double minAvEnrlPrefPenalty = 0, maxAvEnrlPrefPenalty = 0;
333        int nrChoices = 0, nrEnrollments = 0, nrCourseRequests = 0;
334        int chChoices = 0, chCourseRequests = 0, chStudents = 0;
335
336        int choiceLimit = model.getProperties().getPropertyInt("Test.ChoicesLimit", -1);
337
338        File outDir = new File(model.getProperties().getProperty("General.Output", "."));
339        outDir.mkdirs();
340        PrintWriter pw = new PrintWriter(new FileWriter(new File(outDir, "choices.csv")));
341
342        List<Student> students = model.getStudents();
343        try {
344            @SuppressWarnings("rawtypes")
345            Class studentOrdClass = Class.forName(model.getProperties().getProperty("Test.StudentOrder", StudentRandomOrder.class.getName()));
346            @SuppressWarnings("unchecked")
347            StudentOrder studentOrd = (StudentOrder) studentOrdClass.getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { model.getProperties() });
348            students = studentOrd.order(model.getStudents());
349        } catch (Exception e) {
350            sLog.error("Unable to reorder students, reason: " + e.getMessage(), e);
351        }
352        
353        ShutdownHook hook = new ShutdownHook(solver);
354        Runtime.getRuntime().addShutdownHook(hook);
355
356        for (Student student : students) {
357            if (student.nrAssignedRequests(assignment) > 0)
358                continue; // skip students with assigned courses (i.e., students
359                          // already assigned by a batch sectioning process)
360            sLog.info("Sectioning student: " + student);
361
362            BranchBoundSelection.Selection selection = onlineSelection.getSelection(assignment, student);
363            BranchBoundNeighbour neighbour = selection.select();
364            if (neighbour != null) {
365                StudentPreferencePenalties penalties = null;
366                if (selection instanceof OnlineSelection.EpsilonSelection) {
367                    OnlineSelection.EpsilonSelection epsSelection = (OnlineSelection.EpsilonSelection) selection;
368                    penalties = epsSelection.getPenalties();
369                    for (int i = 0; i < neighbour.getAssignment().length; i++) {
370                        Request r = student.getRequests().get(i);
371                        if (r instanceof CourseRequest) {
372                            nrCourseRequests++;
373                            chCourseRequests++;
374                            int chChoicesThisRq = 0;
375                            CourseRequest request = (CourseRequest) r;
376                            for (Enrollment x : request.getAvaiableEnrollments(assignment)) {
377                                nrEnrollments++;
378                                if (epsSelection.isAllowed(i, x)) {
379                                    nrChoices++;
380                                    if (choiceLimit <= 0 || chChoicesThisRq < choiceLimit) {
381                                        chChoices++;
382                                        chChoicesThisRq++;
383                                    }
384                                }
385                            }
386                        }
387                    }
388                    chStudents++;
389                    if (chStudents == 100) {
390                        pw.println(sDF.format(((double) chChoices) / chCourseRequests));
391                        pw.flush();
392                        chStudents = 0;
393                        chChoices = 0;
394                        chCourseRequests = 0;
395                    }
396                }
397                for (int i = 0; i < neighbour.getAssignment().length; i++) {
398                    if (neighbour.getAssignment()[i] == null)
399                        continue;
400                    Enrollment enrollment = neighbour.getAssignment()[i];
401                    if (enrollment.getRequest() instanceof CourseRequest) {
402                        CourseRequest request = (CourseRequest) enrollment.getRequest();
403                        double[] avEnrlMinMax = getMinMaxAvailableEnrollmentPenalty(assignment, request);
404                        minAvEnrlPenalty += avEnrlMinMax[0];
405                        maxAvEnrlPenalty += avEnrlMinMax[1];
406                        totalPenalty += enrollment.getPenalty();
407                        minPenalty += request.getMinPenalty();
408                        maxPenalty += request.getMaxPenalty();
409                        if (penalties != null) {
410                            double[] avEnrlPrefMinMax = penalties.getMinMaxAvailableEnrollmentPenalty(assignment, enrollment.getRequest());
411                            minAvEnrlPrefPenalty += avEnrlPrefMinMax[0];
412                            maxAvEnrlPrefPenalty += avEnrlPrefMinMax[1];
413                            totalPrefPenalty += penalties.getPenalty(enrollment);
414                            minPrefPenalty += penalties.getMinPenalty(enrollment.getRequest());
415                            maxPrefPenalty += penalties.getMaxPenalty(enrollment.getRequest());
416                        }
417                    }
418                }
419                neighbour.assign(assignment, solution.getIteration());
420                sLog.info("Student " + student + " enrolls into " + neighbour);
421                onlineSelection.updateSpace(assignment, student);
422            } else {
423                sLog.warn("No solution found.");
424            }
425            solution.update(JProf.currentTimeSec() - startTime);
426        }
427
428        if (chCourseRequests > 0)
429            pw.println(sDF.format(((double) chChoices) / chCourseRequests));
430
431        pw.flush();
432        pw.close();
433        
434        HashMap<String, String> extra = new HashMap<String, String>();
435        sLog.info("Overall penalty is " + getPerc(totalPenalty, minPenalty, maxPenalty) + "% ("
436                + sDF.format(totalPenalty) + "/" + sDF.format(minPenalty) + ".." + sDF.format(maxPenalty) + ")");
437        extra.put("Overall penalty", getPerc(totalPenalty, minPenalty, maxPenalty) + "% (" + sDF.format(totalPenalty)
438                + "/" + sDF.format(minPenalty) + ".." + sDF.format(maxPenalty) + ")");
439        extra.put("Overall available enrollment penalty", getPerc(totalPenalty, minAvEnrlPenalty, maxAvEnrlPenalty)
440                + "% (" + sDF.format(totalPenalty) + "/" + sDF.format(minAvEnrlPenalty) + ".." + sDF.format(maxAvEnrlPenalty) + ")");
441        if (onlineSelection.isUseStudentPrefPenalties()) {
442            sLog.info("Overall preference penalty is " + getPerc(totalPrefPenalty, minPrefPenalty, maxPrefPenalty)
443                    + "% (" + sDF.format(totalPrefPenalty) + "/" + sDF.format(minPrefPenalty) + ".." + sDF.format(maxPrefPenalty) + ")");
444            extra.put("Overall preference penalty", getPerc(totalPrefPenalty, minPrefPenalty, maxPrefPenalty) + "% ("
445                    + sDF.format(totalPrefPenalty) + "/" + sDF.format(minPrefPenalty) + ".." + sDF.format(maxPrefPenalty) + ")");
446            extra.put("Overall preference available enrollment penalty", getPerc(totalPrefPenalty,
447                    minAvEnrlPrefPenalty, maxAvEnrlPrefPenalty)
448                    + "% (" + sDF.format(totalPrefPenalty) + "/" + sDF.format(minAvEnrlPrefPenalty) + ".." + sDF.format(maxAvEnrlPrefPenalty) + ")");
449            extra.put("Average number of choices", sDF.format(((double) nrChoices) / nrCourseRequests) + " ("
450                    + nrChoices + "/" + nrCourseRequests + ")");
451            extra.put("Average number of enrollments", sDF.format(((double) nrEnrollments) / nrCourseRequests) + " ("
452                    + nrEnrollments + "/" + nrCourseRequests + ")");
453        }
454        hook.setExtra(extra);
455
456        return solution;
457    }
458
459    /**
460     * Minimum and maximum enrollment penalty, i.e.,
461     * {@link Enrollment#getPenalty()} of all enrollments
462     * @param request a course request
463     * @return minimum and maximum of the enrollment penalty
464     */
465    public static double[] getMinMaxEnrollmentPenalty(CourseRequest request) {
466        List<Enrollment> enrollments = request.values(new EmptyAssignment<Request, Enrollment>());
467        if (enrollments.isEmpty())
468            return new double[] { 0, 0 };
469        double min = Double.MAX_VALUE, max = Double.MIN_VALUE;
470        for (Enrollment enrollment : enrollments) {
471            double penalty = enrollment.getPenalty();
472            min = Math.min(min, penalty);
473            max = Math.max(max, penalty);
474        }
475        return new double[] { min, max };
476    }
477
478    /**
479     * Minimum and maximum available enrollment penalty, i.e.,
480     * {@link Enrollment#getPenalty()} of all available enrollments
481     * @param assignment current assignment
482     * @param request a course request
483     * @return minimum and maximum of the available enrollment penalty
484     */
485    public static double[] getMinMaxAvailableEnrollmentPenalty(Assignment<Request, Enrollment> assignment, CourseRequest request) {
486        List<Enrollment> enrollments = request.getAvaiableEnrollments(assignment);
487        if (enrollments.isEmpty())
488            return new double[] { 0, 0 };
489        double min = Double.MAX_VALUE, max = Double.MIN_VALUE;
490        for (Enrollment enrollment : enrollments) {
491            double penalty = enrollment.getPenalty();
492            min = Math.min(min, penalty);
493            max = Math.max(max, penalty);
494        }
495        return new double[] { min, max };
496    }
497
498    /**
499     * Compute percentage
500     * 
501     * @param value
502     *            current value
503     * @param min
504     *            minimal bound
505     * @param max
506     *            maximal bound
507     * @return (value-min)/(max-min)
508     */
509    public static String getPerc(double value, double min, double max) {
510        if (max == min)
511            return sDF.format(100.0);
512        return sDF.format(100.0 - 100.0 * (value - min) / (max - min));
513    }
514
515    /**
516     * Print some information about the solution
517     * 
518     * @param solution
519     *            given solution
520     * @param computeTables
521     *            true, if reports {@link CourseConflictTable} and
522     *            {@link DistanceConflictTable} are to be computed as well
523     * @param computeSectInfos
524     *            true, if online sectioning infou is to be computed as well
525     *            (see
526     *            {@link StudentSectioningModel#computeOnlineSectioningInfos(Assignment)})
527     * @param runChecks
528     *            true, if checks {@link OverlapCheck} and
529     *            {@link SectionLimitCheck} are to be performed as well
530     */
531    public static void printInfo(Solution<Request, Enrollment> solution, boolean computeTables, boolean computeSectInfos, boolean runChecks) {
532        StudentSectioningModel model = (StudentSectioningModel) solution.getModel();
533
534        if (computeTables) {
535            if (solution.getModel().assignedVariables(solution.getAssignment()).size() > 0) {
536                try {
537                    File outDir = new File(model.getProperties().getProperty("General.Output", "."));
538                    outDir.mkdirs();
539                    CourseConflictTable cct = new CourseConflictTable((StudentSectioningModel) solution.getModel());
540                    cct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "conflicts-lastlike.csv"));
541                    cct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "conflicts-real.csv"));
542
543                    DistanceConflictTable dct = new DistanceConflictTable((StudentSectioningModel) solution.getModel());
544                    dct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "distances-lastlike.csv"));
545                    dct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "distances-real.csv"));
546                    
547                    SectionConflictTable sct = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.OVERLAPS);
548                    sct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "time-conflicts-lastlike.csv"));
549                    sct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "time-conflicts-real.csv"));
550                    
551                    SectionConflictTable ust = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.UNAVAILABILITIES);
552                    ust.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "availability-conflicts-lastlike.csv"));
553                    ust.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "availability-conflicts-real.csv"));
554                    
555                    SectionConflictTable ct = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.OVERLAPS_AND_UNAVAILABILITIES);
556                    ct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "section-conflicts-lastlike.csv"));
557                    ct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "section-conflicts-real.csv"));
558                    
559                    UnbalancedSectionsTable ubt = new UnbalancedSectionsTable((StudentSectioningModel) solution.getModel());
560                    ubt.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "unbalanced-lastlike.csv"));
561                    ubt.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "unbalanced-real.csv"));
562                    
563                    TimeOverlapConflictTable toc = new TimeOverlapConflictTable((StudentSectioningModel) solution.getModel());
564                    toc.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "time-overlaps-lastlike.csv"));
565                    toc.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "time-overlaps-real.csv"));
566                    
567                    RequestGroupTable rqt = new RequestGroupTable((StudentSectioningModel) solution.getModel());
568                    rqt.create(solution.getAssignment(), model.getProperties()).save(new File(outDir, "request-groups.csv"));
569                } catch (IOException e) {
570                    sLog.error(e.getMessage(), e);
571                }
572            }
573
574            solution.saveBest();
575        }
576
577        if (computeSectInfos)
578            model.computeOnlineSectioningInfos(solution.getAssignment());
579
580        if (runChecks) {
581            try {
582                if (model.getProperties().getPropertyBoolean("Test.InevitableStudentConflictsCheck", false)) {
583                    InevitableStudentConflicts ch = new InevitableStudentConflicts(model);
584                    if (!ch.check(solution.getAssignment()))
585                        ch.getCSVFile().save(
586                                new File(new File(model.getProperties().getProperty("General.Output", ".")),
587                                        "inevitable-conflicts.csv"));
588                }
589            } catch (IOException e) {
590                sLog.error(e.getMessage(), e);
591            }
592            new OverlapCheck(model).check(solution.getAssignment());
593            new SectionLimitCheck(model).check(solution.getAssignment());
594            try {
595                CourseLimitCheck ch = new CourseLimitCheck(model);
596                if (!ch.check())
597                    ch.getCSVFile().save(
598                            new File(new File(model.getProperties().getProperty("General.Output", ".")),
599                                    "course-limits.csv"));
600            } catch (IOException e) {
601                sLog.error(e.getMessage(), e);
602            }
603        }
604
605        sLog.info("Best solution found after " + solution.getBestTime() + " seconds (" + solution.getBestIteration()
606                + " iterations).");
607        sLog.info("Info: " + ToolBox.dict2string(solution.getExtendedInfo(), 2));
608    }
609
610    /** Solve the student sectioning problem using IFS solver 
611     * @param solution current solution
612     * @param cfg solver configuration
613     * @return resultant solution
614     **/
615    public static Solution<Request, Enrollment> solve(Solution<Request, Enrollment> solution, DataProperties cfg) {
616        int nrSolvers = cfg.getPropertyInt("Parallel.NrSolvers", 1);
617        Solver<Request, Enrollment> solver = (nrSolvers == 1 ? new Solver<Request, Enrollment>(cfg) : new ParallelSolver<Request, Enrollment>(cfg));
618        solver.setInitalSolution(solution);
619        if (cfg.getPropertyBoolean("Test.Verbose", false)) {
620            solver.addSolverListener(new SolverListener<Request, Enrollment>() {
621                @Override
622                public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
623                    return true;
624                }
625
626                @Override
627                public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
628                    return true;
629                }
630
631                @Override
632                public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
633                    sLog.debug("Select[" + iteration + "]: " + neighbour);
634                    return true;
635                }
636
637                @Override
638                public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
639                    sLog.debug("Failed[" + iteration + "]: " + neighbour);
640                }
641            });
642        }
643        solution.addSolutionListener(new TestSolutionListener());
644        
645        Runtime.getRuntime().addShutdownHook(new ShutdownHook(solver));
646
647        solver.start();
648        try {
649            solver.getSolverThread().join();
650        } catch (InterruptedException e) {
651        }
652
653        return solution;
654    }
655
656    /**
657     * Compute last-like student weight for the given course
658     * 
659     * @param course
660     *            given course
661     * @param real
662     *            number of real students for the course
663     * @param lastLike
664     *            number of last-like students for the course
665     * @return weight of a student request for the given course
666     */
667    public static double getLastLikeStudentWeight(Course course, int real, int lastLike) {
668        int projected = course.getProjected();
669        int limit = course.getLimit();
670        if (course.getLimit() < 0) {
671            sLog.debug("  -- Course " + course.getName() + " is unlimited.");
672            return 1.0;
673        }
674        if (projected <= 0) {
675            sLog.warn("  -- No projected demand for course " + course.getName() + ", using course limit (" + limit
676                    + ")");
677            projected = limit;
678        } else if (limit < projected) {
679            sLog.warn("  -- Projected number of students is over course limit for course " + course.getName() + " ("
680                    + Math.round(projected) + ">" + limit + ")");
681            projected = limit;
682        }
683        if (lastLike == 0) {
684            sLog.warn("  -- No last like info for course " + course.getName());
685            return 1.0;
686        }
687        double weight = ((double) Math.max(0, projected - real)) / lastLike;
688        sLog.debug("  -- last like student weight for " + course.getName() + " is " + weight + " (lastLike=" + lastLike
689                + ", real=" + real + ", projected=" + projected + ")");
690        return weight;
691    }
692
693    /**
694     * Load last-like students from an XML file (the one that is used to load
695     * last like course demands table in the timetabling application)
696     * @param model problem model
697     * @param xml an XML file
698     */
699    public static void loadLastLikeCourseDemandsXml(StudentSectioningModel model, File xml) {
700        try {
701            Document document = (new SAXReader()).read(xml);
702            Element root = document.getRootElement();
703            HashMap<Course, List<Request>> requests = new HashMap<Course, List<Request>>();
704            long reqId = 0;
705            for (Iterator<?> i = root.elementIterator("student"); i.hasNext();) {
706                Element studentEl = (Element) i.next();
707                Student student = new Student(Long.parseLong(studentEl.attributeValue("externalId")));
708                student.setDummy(true);
709                int priority = 0;
710                HashSet<Course> reqCourses = new HashSet<Course>();
711                for (Iterator<?> j = studentEl.elementIterator("studentCourse"); j.hasNext();) {
712                    Element courseEl = (Element) j.next();
713                    String subjectArea = courseEl.attributeValue("subject");
714                    String courseNbr = courseEl.attributeValue("courseNumber");
715                    Course course = null;
716                    offerings: for (Offering offering : model.getOfferings()) {
717                        for (Course c : offering.getCourses()) {
718                            if (c.getSubjectArea().equals(subjectArea) && c.getCourseNumber().equals(courseNbr)) {
719                                course = c;
720                                break offerings;
721                            }
722                        }
723                    }
724                    if (course == null && courseNbr.charAt(courseNbr.length() - 1) >= 'A'
725                            && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') {
726                        String courseNbrNoSfx = courseNbr.substring(0, courseNbr.length() - 1);
727                        offerings: for (Offering offering : model.getOfferings()) {
728                            for (Course c : offering.getCourses()) {
729                                if (c.getSubjectArea().equals(subjectArea)
730                                        && c.getCourseNumber().equals(courseNbrNoSfx)) {
731                                    course = c;
732                                    break offerings;
733                                }
734                            }
735                        }
736                    }
737                    if (course == null) {
738                        sLog.warn("Course " + subjectArea + " " + courseNbr + " not found.");
739                    } else {
740                        if (!reqCourses.add(course)) {
741                            sLog.warn("Course " + subjectArea + " " + courseNbr + " already requested.");
742                        } else {
743                            List<Course> courses = new ArrayList<Course>(1);
744                            courses.add(course);
745                            CourseRequest request = new CourseRequest(reqId++, priority++, false, student, courses, false, null);
746                            List<Request> requestsThisCourse = requests.get(course);
747                            if (requestsThisCourse == null) {
748                                requestsThisCourse = new ArrayList<Request>();
749                                requests.put(course, requestsThisCourse);
750                            }
751                            requestsThisCourse.add(request);
752                        }
753                    }
754                }
755                if (!student.getRequests().isEmpty())
756                    model.addStudent(student);
757            }
758            for (Map.Entry<Course, List<Request>> entry : requests.entrySet()) {
759                Course course = entry.getKey();
760                List<Request> requestsThisCourse = entry.getValue();
761                double weight = getLastLikeStudentWeight(course, 0, requestsThisCourse.size());
762                for (Request request : requestsThisCourse) {
763                    request.setWeight(weight);
764                }
765            }
766        } catch (Exception e) {
767            sLog.error(e.getMessage(), e);
768        }
769    }
770
771    /**
772     * Load course request from the given files (in the format being used by the
773     * old MSF system)
774     * 
775     * @param model
776     *            student sectioning model (with offerings loaded)
777     * @param files
778     *            semi-colon separated list of files to be loaded
779     */
780    public static void loadCrsReqFiles(StudentSectioningModel model, String files) {
781        try {
782            boolean lastLike = model.getProperties().getPropertyBoolean("Test.CrsReqIsLastLike", true);
783            boolean shuffleIds = model.getProperties().getPropertyBoolean("Test.CrsReqShuffleStudentIds", true);
784            boolean tryWithoutSuffix = model.getProperties().getPropertyBoolean("Test.CrsReqTryWithoutSuffix", false);
785            HashMap<Long, Student> students = new HashMap<Long, Student>();
786            long reqId = 0;
787            for (StringTokenizer stk = new StringTokenizer(files, ";"); stk.hasMoreTokens();) {
788                String file = stk.nextToken();
789                sLog.debug("Loading " + file + " ...");
790                BufferedReader in = new BufferedReader(new FileReader(file));
791                String line;
792                int lineIndex = 0;
793                while ((line = in.readLine()) != null) {
794                    lineIndex++;
795                    if (line.length() <= 150)
796                        continue;
797                    char code = line.charAt(13);
798                    if (code == 'H' || code == 'T')
799                        continue; // skip header and tail
800                    long studentId = Long.parseLong(line.substring(14, 23));
801                    Student student = students.get(new Long(studentId));
802                    if (student == null) {
803                        student = new Student(studentId);
804                        if (lastLike)
805                            student.setDummy(true);
806                        students.put(new Long(studentId), student);
807                        sLog.debug("  -- loading student " + studentId + " ...");
808                    } else
809                        sLog.debug("  -- updating student " + studentId + " ...");
810                    line = line.substring(150);
811                    while (line.length() >= 20) {
812                        String subjectArea = line.substring(0, 4).trim();
813                        String courseNbr = line.substring(4, 8).trim();
814                        if (subjectArea.length() == 0 || courseNbr.length() == 0) {
815                            line = line.substring(20);
816                            continue;
817                        }
818                        /*
819                         * // UNUSED String instrSel = line.substring(8,10);
820                         * //ZZ - Remove previous instructor selection char
821                         * reqPDiv = line.charAt(10); //P - Personal preference;
822                         * C - Conflict resolution; //0 - (Zero) used by program
823                         * only, for change requests to reschedule division //
824                         * (used to reschedule canceled division) String reqDiv
825                         * = line.substring(11,13); //00 - Reschedule division
826                         * String reqSect = line.substring(13,15); //Contains
827                         * designator for designator-required courses String
828                         * credit = line.substring(15,19); char nameRaise =
829                         * line.charAt(19); //N - Name raise
830                         */
831                        char action = line.charAt(19); // A - Add; D - Drop; C -
832                                                       // Change
833                        sLog.debug("    -- requesting " + subjectArea + " " + courseNbr + " (action:" + action
834                                + ") ...");
835                        Course course = null;
836                        offerings: for (Offering offering : model.getOfferings()) {
837                            for (Course c : offering.getCourses()) {
838                                if (c.getSubjectArea().equals(subjectArea) && c.getCourseNumber().equals(courseNbr)) {
839                                    course = c;
840                                    break offerings;
841                                }
842                            }
843                        }
844                        if (course == null && tryWithoutSuffix && courseNbr.charAt(courseNbr.length() - 1) >= 'A'
845                                && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') {
846                            String courseNbrNoSfx = courseNbr.substring(0, courseNbr.length() - 1);
847                            offerings: for (Offering offering : model.getOfferings()) {
848                                for (Course c : offering.getCourses()) {
849                                    if (c.getSubjectArea().equals(subjectArea)
850                                            && c.getCourseNumber().equals(courseNbrNoSfx)) {
851                                        course = c;
852                                        break offerings;
853                                    }
854                                }
855                            }
856                        }
857                        if (course == null) {
858                            if (courseNbr.charAt(courseNbr.length() - 1) >= 'A'
859                                    && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') {
860                            } else {
861                                sLog.warn("      -- course " + subjectArea + " " + courseNbr + " not found (file "
862                                        + file + ", line " + lineIndex + ")");
863                            }
864                        } else {
865                            CourseRequest courseRequest = null;
866                            for (Request request : student.getRequests()) {
867                                if (request instanceof CourseRequest
868                                        && ((CourseRequest) request).getCourses().contains(course)) {
869                                    courseRequest = (CourseRequest) request;
870                                    break;
871                                }
872                            }
873                            if (action == 'A') {
874                                if (courseRequest == null) {
875                                    List<Course> courses = new ArrayList<Course>(1);
876                                    courses.add(course);
877                                    courseRequest = new CourseRequest(reqId++, student.getRequests().size(), false, student, courses, false, null);
878                                } else {
879                                    sLog.warn("      -- request for course " + course + " is already present");
880                                }
881                            } else if (action == 'D') {
882                                if (courseRequest == null) {
883                                    sLog.warn("      -- request for course " + course
884                                            + " is not present -- cannot be dropped");
885                                } else {
886                                    student.getRequests().remove(courseRequest);
887                                }
888                            } else if (action == 'C') {
889                                if (courseRequest == null) {
890                                    sLog.warn("      -- request for course " + course
891                                            + " is not present -- cannot be changed");
892                                } else {
893                                    // ?
894                                }
895                            } else {
896                                sLog.warn("      -- unknown action " + action);
897                            }
898                        }
899                        line = line.substring(20);
900                    }
901                }
902                in.close();
903            }
904            HashMap<Course, List<Request>> requests = new HashMap<Course, List<Request>>();
905            Set<Long> studentIds = new HashSet<Long>();
906            for (Student student: students.values()) {
907                if (!student.getRequests().isEmpty())
908                    model.addStudent(student);
909                if (shuffleIds) {
910                    long newId = -1;
911                    while (true) {
912                        newId = 1 + (long) (999999999L * Math.random());
913                        if (studentIds.add(new Long(newId)))
914                            break;
915                    }
916                    student.setId(newId);
917                }
918                if (student.isDummy()) {
919                    for (Request request : student.getRequests()) {
920                        if (request instanceof CourseRequest) {
921                            Course course = ((CourseRequest) request).getCourses().get(0);
922                            List<Request> requestsThisCourse = requests.get(course);
923                            if (requestsThisCourse == null) {
924                                requestsThisCourse = new ArrayList<Request>();
925                                requests.put(course, requestsThisCourse);
926                            }
927                            requestsThisCourse.add(request);
928                        }
929                    }
930                }
931            }
932            Collections.sort(model.getStudents(), new Comparator<Student>() {
933                @Override
934                public int compare(Student o1, Student o2) {
935                    return Double.compare(o1.getId(), o2.getId());
936                }
937            });
938            for (Map.Entry<Course, List<Request>> entry : requests.entrySet()) {
939                Course course = entry.getKey();
940                List<Request> requestsThisCourse = entry.getValue();
941                double weight = getLastLikeStudentWeight(course, 0, requestsThisCourse.size());
942                for (Request request : requestsThisCourse) {
943                    request.setWeight(weight);
944                }
945            }
946            if (model.getProperties().getProperty("Test.EtrChk") != null) {
947                for (StringTokenizer stk = new StringTokenizer(model.getProperties().getProperty("Test.EtrChk"), ";"); stk
948                        .hasMoreTokens();) {
949                    String file = stk.nextToken();
950                    sLog.debug("Loading " + file + " ...");
951                    BufferedReader in = new BufferedReader(new FileReader(file));
952                    try {
953                        String line;
954                        while ((line = in.readLine()) != null) {
955                            if (line.length() < 55)
956                                continue;
957                            char code = line.charAt(12);
958                            if (code == 'H' || code == 'T')
959                                continue; // skip header and tail
960                            if (code == 'D' || code == 'K')
961                                continue; // skip delete nad cancel
962                            long studentId = Long.parseLong(line.substring(2, 11));
963                            Student student = students.get(new Long(studentId));
964                            if (student == null) {
965                                sLog.info("  -- student " + studentId + " not found");
966                                continue;
967                            }
968                            sLog.info("  -- reading student " + studentId);
969                            String area = line.substring(15, 18).trim();
970                            if (area.length() == 0)
971                                continue;
972                            String clasf = line.substring(18, 20).trim();
973                            String major = line.substring(21, 24).trim();
974                            String minor = line.substring(24, 27).trim();
975                            student.getAcademicAreaClasiffications().clear();
976                            student.getMajors().clear();
977                            student.getMinors().clear();
978                            student.getAcademicAreaClasiffications().add(new AcademicAreaCode(area, clasf));
979                            if (major.length() > 0)
980                                student.getMajors().add(new AcademicAreaCode(area, major));
981                            if (minor.length() > 0)
982                                student.getMinors().add(new AcademicAreaCode(area, minor));
983                        }
984                    } finally {
985                        in.close();
986                    }
987                }
988            }
989            int without = 0;
990            for (Student student: students.values()) {
991                if (student.getAcademicAreaClasiffications().isEmpty())
992                    without++;
993            }
994            fixPriorities(model);
995            sLog.info("Students without academic area: " + without);
996        } catch (Exception e) {
997            sLog.error(e.getMessage(), e);
998        }
999    }
1000
1001    public static void fixPriorities(StudentSectioningModel model) {
1002        for (Student student : model.getStudents()) {
1003            Collections.sort(student.getRequests(), new Comparator<Request>() {
1004                @Override
1005                public int compare(Request r1, Request r2) {
1006                    int cmp = Double.compare(r1.getPriority(), r2.getPriority());
1007                    if (cmp != 0)
1008                        return cmp;
1009                    return Double.compare(r1.getId(), r2.getId());
1010                }
1011            });
1012            int priority = 0;
1013            for (Request request : student.getRequests()) {
1014                if (priority != request.getPriority()) {
1015                    sLog.debug("Change priority of " + request + " to " + priority);
1016                    request.setPriority(priority);
1017                }
1018            }
1019        }
1020    }
1021
1022    /** Load student infos from a given XML file. 
1023     * @param model problem model
1024     * @param xml an XML file
1025     **/
1026    public static void loadStudentInfoXml(StudentSectioningModel model, File xml) {
1027        try {
1028            sLog.info("Loading student infos from " + xml);
1029            Document document = (new SAXReader()).read(xml);
1030            Element root = document.getRootElement();
1031            HashMap<Long, Student> studentTable = new HashMap<Long, Student>();
1032            for (Student student : model.getStudents()) {
1033                studentTable.put(new Long(student.getId()), student);
1034            }
1035            for (Iterator<?> i = root.elementIterator("student"); i.hasNext();) {
1036                Element studentEl = (Element) i.next();
1037                Student student = studentTable.get(Long.valueOf(studentEl.attributeValue("externalId")));
1038                if (student == null) {
1039                    sLog.debug(" -- student " + studentEl.attributeValue("externalId") + " not found");
1040                    continue;
1041                }
1042                sLog.debug(" -- loading info for student " + student);
1043                student.getAcademicAreaClasiffications().clear();
1044                if (studentEl.element("studentAcadAreaClass") != null)
1045                    for (Iterator<?> j = studentEl.element("studentAcadAreaClass").elementIterator("acadAreaClass"); j
1046                            .hasNext();) {
1047                        Element studentAcadAreaClassElement = (Element) j.next();
1048                        student.getAcademicAreaClasiffications().add(
1049                                new AcademicAreaCode(studentAcadAreaClassElement.attributeValue("academicArea"),
1050                                        studentAcadAreaClassElement.attributeValue("academicClass")));
1051                    }
1052                sLog.debug("   -- acad areas classifs " + student.getAcademicAreaClasiffications());
1053                student.getMajors().clear();
1054                if (studentEl.element("studentMajors") != null)
1055                    for (Iterator<?> j = studentEl.element("studentMajors").elementIterator("major"); j.hasNext();) {
1056                        Element studentMajorElement = (Element) j.next();
1057                        student.getMajors().add(
1058                                new AcademicAreaCode(studentMajorElement.attributeValue("academicArea"),
1059                                        studentMajorElement.attributeValue("code")));
1060                    }
1061                sLog.debug("   -- majors " + student.getMajors());
1062                student.getMinors().clear();
1063                if (studentEl.element("studentMinors") != null)
1064                    for (Iterator<?> j = studentEl.element("studentMinors").elementIterator("minor"); j.hasNext();) {
1065                        Element studentMinorElement = (Element) j.next();
1066                        student.getMinors().add(
1067                                new AcademicAreaCode(studentMinorElement.attributeValue("academicArea", ""),
1068                                        studentMinorElement.attributeValue("code", "")));
1069                    }
1070                sLog.debug("   -- minors " + student.getMinors());
1071            }
1072        } catch (Exception e) {
1073            sLog.error(e.getMessage(), e);
1074        }
1075    }
1076
1077    /** Save solution info as XML 
1078     * @param solution current solution
1079     * @param extra solution extra info
1080     * @param file file to write
1081     **/
1082    public static void saveInfoToXML(Solution<Request, Enrollment> solution, Map<String, String> extra, File file) {
1083        FileOutputStream fos = null;
1084        try {
1085            Document document = DocumentHelper.createDocument();
1086            document.addComment("Solution Info");
1087
1088            Element root = document.addElement("info");
1089            TreeSet<Map.Entry<String, String>> entrySet = new TreeSet<Map.Entry<String, String>>(
1090                    new Comparator<Map.Entry<String, String>>() {
1091                        @Override
1092                        public int compare(Map.Entry<String, String> e1, Map.Entry<String, String> e2) {
1093                            return e1.getKey().compareTo(e2.getKey());
1094                        }
1095                    });
1096            entrySet.addAll(solution.getExtendedInfo().entrySet());
1097            if (extra != null)
1098                entrySet.addAll(extra.entrySet());
1099            for (Map.Entry<String, String> entry : entrySet) {
1100                root.addElement("property").addAttribute("name", entry.getKey()).setText(entry.getValue());
1101            }
1102
1103            fos = new FileOutputStream(file);
1104            (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(document);
1105            fos.flush();
1106            fos.close();
1107            fos = null;
1108        } catch (Exception e) {
1109            sLog.error("Unable to save info, reason: " + e.getMessage(), e);
1110        } finally {
1111            try {
1112                if (fos != null)
1113                    fos.close();
1114            } catch (IOException e) {
1115            }
1116        }
1117    }
1118
1119    private static void fixWeights(StudentSectioningModel model) {
1120        HashMap<Course, Integer> lastLike = new HashMap<Course, Integer>();
1121        HashMap<Course, Integer> real = new HashMap<Course, Integer>();
1122        HashSet<Long> lastLikeIds = new HashSet<Long>();
1123        HashSet<Long> realIds = new HashSet<Long>();
1124        for (Student student : model.getStudents()) {
1125            if (student.isDummy()) {
1126                if (!lastLikeIds.add(new Long(student.getId()))) {
1127                    sLog.error("Two last-like student with id " + student.getId());
1128                }
1129            } else {
1130                if (!realIds.add(new Long(student.getId()))) {
1131                    sLog.error("Two real student with id " + student.getId());
1132                }
1133            }
1134            for (Request request : student.getRequests()) {
1135                if (request instanceof CourseRequest) {
1136                    CourseRequest courseRequest = (CourseRequest) request;
1137                    Course course = courseRequest.getCourses().get(0);
1138                    Integer cnt = (student.isDummy() ? lastLike : real).get(course);
1139                    (student.isDummy() ? lastLike : real).put(course, new Integer(
1140                            (cnt == null ? 0 : cnt.intValue()) + 1));
1141                }
1142            }
1143        }
1144        for (Student student : new ArrayList<Student>(model.getStudents())) {
1145            if (student.isDummy() && realIds.contains(new Long(student.getId()))) {
1146                sLog.warn("There is both last-like and real student with id " + student.getId());
1147                long newId = -1;
1148                while (true) {
1149                    newId = 1 + (long) (999999999L * Math.random());
1150                    if (!realIds.contains(new Long(newId)) && !lastLikeIds.contains(new Long(newId)))
1151                        break;
1152                }
1153                lastLikeIds.remove(new Long(student.getId()));
1154                lastLikeIds.add(new Long(newId));
1155                student.setId(newId);
1156                sLog.warn("  -- last-like student id changed to " + student.getId());
1157            }
1158            for (Request request : new ArrayList<Request>(student.getRequests())) {
1159                if (!student.isDummy()) {
1160                    request.setWeight(1.0);
1161                    continue;
1162                }
1163                if (request instanceof CourseRequest) {
1164                    CourseRequest courseRequest = (CourseRequest) request;
1165                    Course course = courseRequest.getCourses().get(0);
1166                    Integer lastLikeCnt = lastLike.get(course);
1167                    Integer realCnt = real.get(course);
1168                    courseRequest.setWeight(getLastLikeStudentWeight(course, realCnt == null ? 0 : realCnt.intValue(),
1169                            lastLikeCnt == null ? 0 : lastLikeCnt.intValue()));
1170                } else
1171                    request.setWeight(1.0);
1172                if (request.getWeight() <= 0.0) {
1173                    model.removeVariable(request);
1174                    student.getRequests().remove(request);
1175                }
1176            }
1177            if (student.getRequests().isEmpty()) {
1178                model.getStudents().remove(student);
1179            }
1180        }
1181    }
1182
1183    /** Combine students from the provided two files 
1184     * @param cfg solver configuration
1185     * @param lastLikeStudentData a file containing last-like student data
1186     * @param realStudentData a file containing real student data
1187     * @return combined solution
1188     **/
1189    public static Solution<Request, Enrollment> combineStudents(DataProperties cfg, File lastLikeStudentData, File realStudentData) {
1190        try {
1191            RandomStudentFilter rnd = new RandomStudentFilter(1.0);
1192
1193            StudentSectioningModel model = null;
1194            Assignment<Request, Enrollment> assignment = new DefaultSingleAssignment<Request, Enrollment>();
1195
1196            for (StringTokenizer stk = new StringTokenizer(cfg.getProperty("Test.CombineAcceptProb", "1.0"), ","); stk.hasMoreTokens();) {
1197                double acceptProb = Double.parseDouble(stk.nextToken());
1198                sLog.info("Test.CombineAcceptProb=" + acceptProb);
1199                rnd.setProbability(acceptProb);
1200
1201                StudentFilter batchFilter = new CombinedStudentFilter(new ReverseStudentFilter(
1202                        new FreshmanStudentFilter()), rnd, CombinedStudentFilter.OP_AND);
1203
1204                model = new StudentSectioningModel(cfg);
1205                StudentSectioningXMLLoader loader = new StudentSectioningXMLLoader(model, assignment);
1206                loader.setLoadStudents(false);
1207                loader.load();
1208
1209                StudentSectioningXMLLoader lastLikeLoader = new StudentSectioningXMLLoader(model, assignment);
1210                lastLikeLoader.setInputFile(lastLikeStudentData);
1211                lastLikeLoader.setLoadOfferings(false);
1212                lastLikeLoader.setLoadStudents(true);
1213                lastLikeLoader.load();
1214
1215                StudentSectioningXMLLoader realLoader = new StudentSectioningXMLLoader(model, assignment);
1216                realLoader.setInputFile(realStudentData);
1217                realLoader.setLoadOfferings(false);
1218                realLoader.setLoadStudents(true);
1219                realLoader.setStudentFilter(batchFilter);
1220                realLoader.load();
1221
1222                fixWeights(model);
1223
1224                fixPriorities(model);
1225
1226                Solver<Request, Enrollment> solver = new Solver<Request, Enrollment>(model.getProperties());
1227                solver.setInitalSolution(model);
1228                new StudentSectioningXMLSaver(solver).save(new File(new File(model.getProperties().getProperty(
1229                        "General.Output", ".")), "solution-r" + ((int) (100.0 * acceptProb)) + ".xml"));
1230
1231            }
1232
1233            return model == null ? null : new Solution<Request, Enrollment>(model, assignment);
1234
1235        } catch (Exception e) {
1236            sLog.error("Unable to combine students, reason: " + e.getMessage(), e);
1237            return null;
1238        }
1239    }
1240    
1241    /**
1242     * Setup log4j logging
1243     * 
1244     * @param logFile  log file
1245     */
1246    public static void setupLogging(File logFile) {
1247        Logger root = Logger.getRootLogger();
1248        ConsoleAppender console = new ConsoleAppender(new PatternLayout("[%t] %m%n"));
1249        console.setThreshold(Level.INFO);
1250        root.addAppender(console);
1251        if (logFile != null) {
1252            try {
1253                FileAppender file = new FileAppender(new PatternLayout("%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n"), logFile.getPath(), false);
1254                file.setThreshold(Level.DEBUG);
1255                root.addAppender(file);
1256            } catch (IOException e) {
1257                sLog.fatal("Unable to configure logging, reason: " + e.getMessage(), e);
1258            }
1259        }
1260    }
1261
1262    /** Main 
1263     * @param args program arguments
1264     **/
1265    public static void main(String[] args) {
1266        try {
1267            DataProperties cfg = new DataProperties();
1268            cfg.setProperty("Termination.Class", "org.cpsolver.ifs.termination.GeneralTerminationCondition");
1269            cfg.setProperty("Termination.StopWhenComplete", "true");
1270            cfg.setProperty("Termination.TimeOut", "600");
1271            cfg.setProperty("Comparator.Class", "org.cpsolver.ifs.solution.GeneralSolutionComparator");
1272            cfg.setProperty("Value.Class", "org.cpsolver.studentsct.heuristics.EnrollmentSelection");// org.cpsolver.ifs.heuristics.GeneralValueSelection
1273            cfg.setProperty("Value.WeightConflicts", "1.0");
1274            cfg.setProperty("Value.WeightNrAssignments", "0.0");
1275            cfg.setProperty("Variable.Class", "org.cpsolver.ifs.heuristics.GeneralVariableSelection");
1276            cfg.setProperty("Neighbour.Class", "org.cpsolver.studentsct.heuristics.StudentSctNeighbourSelection");
1277            cfg.setProperty("General.SaveBestUnassigned", "0");
1278            cfg.setProperty("Extensions.Classes",
1279                    "org.cpsolver.ifs.extension.ConflictStatistics;org.cpsolver.studentsct.extension.DistanceConflict" +
1280                    ";org.cpsolver.studentsct.extension.TimeOverlapsCounter");
1281            cfg.setProperty("Data.Initiative", "puWestLafayetteTrdtn");
1282            cfg.setProperty("Data.Term", "Fal");
1283            cfg.setProperty("Data.Year", "2007");
1284            cfg.setProperty("General.Input", "pu-sectll-fal07-s.xml");
1285            if (args.length >= 1) {
1286                cfg.load(new FileInputStream(args[0]));
1287            }
1288            cfg.putAll(System.getProperties());
1289
1290            if (args.length >= 2) {
1291                cfg.setProperty("General.Input", args[1]);
1292            }
1293
1294            File outDir = null;
1295            if (args.length >= 3) {
1296                outDir = new File(args[2], sDateFormat.format(new Date()));
1297            } else if (cfg.getProperty("General.Output") != null) {
1298                outDir = new File(cfg.getProperty("General.Output", "."), sDateFormat.format(new Date()));
1299            } else {
1300                outDir = new File(System.getProperty("user.home", ".") + File.separator + "Sectioning-Test" + File.separator + (sDateFormat.format(new Date())));
1301            }
1302            outDir.mkdirs();
1303            setupLogging(new File(outDir, "debug.log"));
1304            cfg.setProperty("General.Output", outDir.getAbsolutePath());
1305
1306            if (args.length >= 4 && "online".equals(args[3])) {
1307                onlineSectioning(cfg);
1308            } else if (args.length >= 4 && "simple".equals(args[3])) {
1309                cfg.setProperty("Sectioning.UseOnlinePenalties", "false");
1310                onlineSectioning(cfg);
1311            } else {
1312                batchSectioning(cfg);
1313            }
1314        } catch (Exception e) {
1315            sLog.error(e.getMessage(), e);
1316            e.printStackTrace();
1317        }
1318    }
1319
1320    public static class ExtraStudentFilter implements StudentFilter {
1321        HashSet<Long> iIds = new HashSet<Long>();
1322
1323        public ExtraStudentFilter(StudentSectioningModel model) {
1324            for (Student student : model.getStudents()) {
1325                iIds.add(new Long(student.getId()));
1326            }
1327        }
1328
1329        @Override
1330        public boolean accept(Student student) {
1331            return !iIds.contains(new Long(student.getId()));
1332        }
1333    }
1334
1335    public static class TestSolutionListener implements SolutionListener<Request, Enrollment> {
1336        @Override
1337        public void solutionUpdated(Solution<Request, Enrollment> solution) {
1338            StudentSectioningModel m = (StudentSectioningModel) solution.getModel();
1339            if (m.getTimeOverlaps() != null && TimeOverlapsCounter.sDebug)
1340                m.getTimeOverlaps().checkTotalNrConflicts(solution.getAssignment());
1341            if (m.getDistanceConflict() != null && DistanceConflict.sDebug)
1342                m.getDistanceConflict().checkAllConflicts(solution.getAssignment());
1343        }
1344
1345        @Override
1346        public void getInfo(Solution<Request, Enrollment> solution, Map<String, String> info) {
1347        }
1348
1349        @Override
1350        public void getInfo(Solution<Request, Enrollment> solution, Map<String, String> info, Collection<Request> variables) {
1351        }
1352
1353        @Override
1354        public void bestCleared(Solution<Request, Enrollment> solution) {
1355        }
1356
1357        @Override
1358        public void bestSaved(Solution<Request, Enrollment> solution) {
1359            sLog.info("**BEST** " + ((StudentSectioningModel)solution.getModel()).toString(solution.getAssignment()) + ", TM:" + sDF.format(solution.getTime() / 3600.0) + "h" +
1360                    (solution.getFailedIterations() > 0 ? ", F:" + sDF.format(100.0 * solution.getFailedIterations() / solution.getIteration()) + "%" : ""));
1361        }
1362
1363        @Override
1364        public void bestRestored(Solution<Request, Enrollment> solution) {
1365        }
1366    }
1367    
1368    private static class ShutdownHook extends Thread {
1369        Solver<Request, Enrollment> iSolver = null;
1370        Map<String, String> iExtra = null;
1371
1372        private ShutdownHook(Solver<Request, Enrollment> solver) {
1373            setName("ShutdownHook");
1374            iSolver = solver;
1375        }
1376        
1377        void setExtra(Map<String, String> extra) { iExtra = extra; }
1378        
1379        @Override
1380        public void run() {
1381            try {
1382                if (iSolver.isRunning()) iSolver.stopSolver();
1383                Solution<Request, Enrollment> solution = iSolver.lastSolution();
1384                solution.restoreBest();
1385                DataProperties cfg = iSolver.getProperties();
1386                
1387                printInfo(solution,
1388                        cfg.getPropertyBoolean("Test.CreateReports", true),
1389                        cfg.getPropertyBoolean("Test.ComputeSectioningInfo", true),
1390                        cfg.getPropertyBoolean("Test.RunChecks", true));
1391
1392                try {
1393                    new StudentSectioningXMLSaver(iSolver).save(new File(new File(cfg.getProperty("General.Output", ".")), "solution.xml"));
1394                } catch (Exception e) {
1395                    sLog.error("Unable to save solution, reason: " + e.getMessage(), e);
1396                }
1397                
1398                saveInfoToXML(solution, iExtra, new File(new File(cfg.getProperty("General.Output", ".")), "info.xml"));
1399                
1400                Progress.removeInstance(solution.getModel());
1401            } catch (Throwable t) {
1402                sLog.error("Test failed.", t);
1403            }
1404        }
1405    }
1406
1407}