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