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