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            solution.saveBest();
429        }
430
431        if (chCourseRequests > 0)
432            pw.println(sDF.format(((double) chChoices) / chCourseRequests));
433
434        pw.flush();
435        pw.close();
436        
437        HashMap<String, String> extra = new HashMap<String, String>();
438        sLog.info("Overall penalty is " + getPerc(totalPenalty, minPenalty, maxPenalty) + "% ("
439                + sDF.format(totalPenalty) + "/" + sDF.format(minPenalty) + ".." + sDF.format(maxPenalty) + ")");
440        extra.put("Overall penalty", getPerc(totalPenalty, minPenalty, maxPenalty) + "% (" + sDF.format(totalPenalty)
441                + "/" + sDF.format(minPenalty) + ".." + sDF.format(maxPenalty) + ")");
442        extra.put("Overall available enrollment penalty", getPerc(totalPenalty, minAvEnrlPenalty, maxAvEnrlPenalty)
443                + "% (" + sDF.format(totalPenalty) + "/" + sDF.format(minAvEnrlPenalty) + ".." + sDF.format(maxAvEnrlPenalty) + ")");
444        if (onlineSelection.isUseStudentPrefPenalties()) {
445            sLog.info("Overall preference penalty is " + getPerc(totalPrefPenalty, minPrefPenalty, maxPrefPenalty)
446                    + "% (" + sDF.format(totalPrefPenalty) + "/" + sDF.format(minPrefPenalty) + ".." + sDF.format(maxPrefPenalty) + ")");
447            extra.put("Overall preference penalty", getPerc(totalPrefPenalty, minPrefPenalty, maxPrefPenalty) + "% ("
448                    + sDF.format(totalPrefPenalty) + "/" + sDF.format(minPrefPenalty) + ".." + sDF.format(maxPrefPenalty) + ")");
449            extra.put("Overall preference available enrollment penalty", getPerc(totalPrefPenalty,
450                    minAvEnrlPrefPenalty, maxAvEnrlPrefPenalty)
451                    + "% (" + sDF.format(totalPrefPenalty) + "/" + sDF.format(minAvEnrlPrefPenalty) + ".." + sDF.format(maxAvEnrlPrefPenalty) + ")");
452            extra.put("Average number of choices", sDF.format(((double) nrChoices) / nrCourseRequests) + " ("
453                    + nrChoices + "/" + nrCourseRequests + ")");
454            extra.put("Average number of enrollments", sDF.format(((double) nrEnrollments) / nrCourseRequests) + " ("
455                    + nrEnrollments + "/" + nrCourseRequests + ")");
456        }
457        hook.setExtra(extra);
458
459        return solution;
460    }
461
462    /**
463     * Minimum and maximum enrollment penalty, i.e.,
464     * {@link Enrollment#getPenalty()} of all enrollments
465     * @param request a course request
466     * @return minimum and maximum of the enrollment penalty
467     */
468    public static double[] getMinMaxEnrollmentPenalty(CourseRequest request) {
469        List<Enrollment> enrollments = request.values(new EmptyAssignment<Request, Enrollment>());
470        if (enrollments.isEmpty())
471            return new double[] { 0, 0 };
472        double min = Double.MAX_VALUE, max = Double.MIN_VALUE;
473        for (Enrollment enrollment : enrollments) {
474            double penalty = enrollment.getPenalty();
475            min = Math.min(min, penalty);
476            max = Math.max(max, penalty);
477        }
478        return new double[] { min, max };
479    }
480
481    /**
482     * Minimum and maximum available enrollment penalty, i.e.,
483     * {@link Enrollment#getPenalty()} of all available enrollments
484     * @param assignment current assignment
485     * @param request a course request
486     * @return minimum and maximum of the available enrollment penalty
487     */
488    public static double[] getMinMaxAvailableEnrollmentPenalty(Assignment<Request, Enrollment> assignment, CourseRequest request) {
489        List<Enrollment> enrollments = request.getAvaiableEnrollments(assignment);
490        if (enrollments.isEmpty())
491            return new double[] { 0, 0 };
492        double min = Double.MAX_VALUE, max = Double.MIN_VALUE;
493        for (Enrollment enrollment : enrollments) {
494            double penalty = enrollment.getPenalty();
495            min = Math.min(min, penalty);
496            max = Math.max(max, penalty);
497        }
498        return new double[] { min, max };
499    }
500
501    /**
502     * Compute percentage
503     * 
504     * @param value
505     *            current value
506     * @param min
507     *            minimal bound
508     * @param max
509     *            maximal bound
510     * @return (value-min)/(max-min)
511     */
512    public static String getPerc(double value, double min, double max) {
513        if (max == min)
514            return sDF.format(100.0);
515        return sDF.format(100.0 - 100.0 * (value - min) / (max - min));
516    }
517
518    /**
519     * Print some information about the solution
520     * 
521     * @param solution
522     *            given solution
523     * @param computeTables
524     *            true, if reports {@link CourseConflictTable} and
525     *            {@link DistanceConflictTable} are to be computed as well
526     * @param computeSectInfos
527     *            true, if online sectioning infou is to be computed as well
528     *            (see
529     *            {@link StudentSectioningModel#computeOnlineSectioningInfos(Assignment)})
530     * @param runChecks
531     *            true, if checks {@link OverlapCheck} and
532     *            {@link SectionLimitCheck} are to be performed as well
533     */
534    public static void printInfo(Solution<Request, Enrollment> solution, boolean computeTables, boolean computeSectInfos, boolean runChecks) {
535        StudentSectioningModel model = (StudentSectioningModel) solution.getModel();
536
537        if (computeTables) {
538            if (solution.getModel().assignedVariables(solution.getAssignment()).size() > 0) {
539                try {
540                    File outDir = new File(model.getProperties().getProperty("General.Output", "."));
541                    outDir.mkdirs();
542                    CourseConflictTable cct = new CourseConflictTable((StudentSectioningModel) solution.getModel());
543                    cct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "conflicts-lastlike.csv"));
544                    cct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "conflicts-real.csv"));
545
546                    DistanceConflictTable dct = new DistanceConflictTable((StudentSectioningModel) solution.getModel());
547                    dct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "distances-lastlike.csv"));
548                    dct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "distances-real.csv"));
549                    
550                    SectionConflictTable sct = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.OVERLAPS);
551                    sct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "time-conflicts-lastlike.csv"));
552                    sct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "time-conflicts-real.csv"));
553                    
554                    SectionConflictTable ust = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.UNAVAILABILITIES);
555                    ust.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "availability-conflicts-lastlike.csv"));
556                    ust.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "availability-conflicts-real.csv"));
557                    
558                    SectionConflictTable ct = new SectionConflictTable((StudentSectioningModel) solution.getModel(), SectionConflictTable.Type.OVERLAPS_AND_UNAVAILABILITIES);
559                    ct.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "section-conflicts-lastlike.csv"));
560                    ct.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "section-conflicts-real.csv"));
561                    
562                    UnbalancedSectionsTable ubt = new UnbalancedSectionsTable((StudentSectioningModel) solution.getModel());
563                    ubt.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "unbalanced-lastlike.csv"));
564                    ubt.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "unbalanced-real.csv"));
565                    
566                    TimeOverlapConflictTable toc = new TimeOverlapConflictTable((StudentSectioningModel) solution.getModel());
567                    toc.createTable(solution.getAssignment(), true, false, true).save(new File(outDir, "time-overlaps-lastlike.csv"));
568                    toc.createTable(solution.getAssignment(), false, true, true).save(new File(outDir, "time-overlaps-real.csv"));
569                    
570                    RequestGroupTable rqt = new RequestGroupTable((StudentSectioningModel) solution.getModel());
571                    rqt.create(solution.getAssignment(), model.getProperties()).save(new File(outDir, "request-groups.csv"));
572                    
573                    RequestPriorityTable rpt = new RequestPriorityTable((StudentSectioningModel) solution.getModel());
574                    rpt.create(solution.getAssignment(), model.getProperties()).save(new File(outDir, "request-priorities.csv"));
575                    
576                    TableauReport tr = new TableauReport((StudentSectioningModel) solution.getModel());
577                    tr.create(solution.getAssignment(), model.getProperties()).save(new File(outDir, "tableau.csv"));
578                } catch (IOException e) {
579                    sLog.error(e.getMessage(), e);
580                }
581            }
582
583            solution.saveBest();
584        }
585
586        if (computeSectInfos)
587            model.computeOnlineSectioningInfos(solution.getAssignment());
588
589        if (runChecks) {
590            try {
591                if (model.getProperties().getPropertyBoolean("Test.InevitableStudentConflictsCheck", false)) {
592                    InevitableStudentConflicts ch = new InevitableStudentConflicts(model);
593                    if (!ch.check(solution.getAssignment()))
594                        ch.getCSVFile().save(
595                                new File(new File(model.getProperties().getProperty("General.Output", ".")),
596                                        "inevitable-conflicts.csv"));
597                }
598            } catch (IOException e) {
599                sLog.error(e.getMessage(), e);
600            }
601            new OverlapCheck(model).check(solution.getAssignment());
602            new SectionLimitCheck(model).check(solution.getAssignment());
603            try {
604                CourseLimitCheck ch = new CourseLimitCheck(model);
605                if (!ch.check())
606                    ch.getCSVFile().save(
607                            new File(new File(model.getProperties().getProperty("General.Output", ".")),
608                                    "course-limits.csv"));
609            } catch (IOException e) {
610                sLog.error(e.getMessage(), e);
611            }
612        }
613
614        sLog.info("Best solution found after " + solution.getBestTime() + " seconds (" + solution.getBestIteration()
615                + " iterations).");
616        sLog.info("Info: " + ToolBox.dict2string(solution.getExtendedInfo(), 2));
617    }
618
619    /** Solve the student sectioning problem using IFS solver 
620     * @param solution current solution
621     * @param cfg solver configuration
622     * @return resultant solution
623     **/
624    public static Solution<Request, Enrollment> solve(Solution<Request, Enrollment> solution, DataProperties cfg) {
625        int nrSolvers = cfg.getPropertyInt("Parallel.NrSolvers", 1);
626        Solver<Request, Enrollment> solver = (nrSolvers == 1 ? new Solver<Request, Enrollment>(cfg) : new ParallelSolver<Request, Enrollment>(cfg));
627        solver.setInitalSolution(solution);
628        if (cfg.getPropertyBoolean("Test.Verbose", false)) {
629            solver.addSolverListener(new SolverListener<Request, Enrollment>() {
630                @Override
631                public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
632                    return true;
633                }
634
635                @Override
636                public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
637                    return true;
638                }
639
640                @Override
641                public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
642                    sLog.debug("Select[" + iteration + "]: " + neighbour);
643                    return true;
644                }
645
646                @Override
647                public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
648                    sLog.debug("Failed[" + iteration + "]: " + neighbour);
649                }
650            });
651        }
652        solution.addSolutionListener(new TestSolutionListener());
653        
654        Runtime.getRuntime().addShutdownHook(new ShutdownHook(solver));
655
656        solver.start();
657        try {
658            solver.getSolverThread().join();
659        } catch (InterruptedException e) {
660        }
661
662        return solution;
663    }
664
665    /**
666     * Compute last-like student weight for the given course
667     * 
668     * @param course
669     *            given course
670     * @param real
671     *            number of real students for the course
672     * @param lastLike
673     *            number of last-like students for the course
674     * @return weight of a student request for the given course
675     */
676    public static double getLastLikeStudentWeight(Course course, int real, int lastLike) {
677        int projected = course.getProjected();
678        int limit = course.getLimit();
679        if (course.getLimit() < 0) {
680            sLog.debug("  -- Course " + course.getName() + " is unlimited.");
681            return 1.0;
682        }
683        if (projected <= 0) {
684            sLog.warn("  -- No projected demand for course " + course.getName() + ", using course limit (" + limit
685                    + ")");
686            projected = limit;
687        } else if (limit < projected) {
688            sLog.warn("  -- Projected number of students is over course limit for course " + course.getName() + " ("
689                    + Math.round(projected) + ">" + limit + ")");
690            projected = limit;
691        }
692        if (lastLike == 0) {
693            sLog.warn("  -- No last like info for course " + course.getName());
694            return 1.0;
695        }
696        double weight = ((double) Math.max(0, projected - real)) / lastLike;
697        sLog.debug("  -- last like student weight for " + course.getName() + " is " + weight + " (lastLike=" + lastLike
698                + ", real=" + real + ", projected=" + projected + ")");
699        return weight;
700    }
701
702    /**
703     * Load last-like students from an XML file (the one that is used to load
704     * last like course demands table in the timetabling application)
705     * @param model problem model
706     * @param xml an XML file
707     */
708    public static void loadLastLikeCourseDemandsXml(StudentSectioningModel model, File xml) {
709        try {
710            Document document = (new SAXReader()).read(xml);
711            Element root = document.getRootElement();
712            HashMap<Course, List<Request>> requests = new HashMap<Course, List<Request>>();
713            long reqId = 0;
714            for (Iterator<?> i = root.elementIterator("student"); i.hasNext();) {
715                Element studentEl = (Element) i.next();
716                Student student = new Student(Long.parseLong(studentEl.attributeValue("externalId")));
717                student.setDummy(true);
718                int priority = 0;
719                HashSet<Course> reqCourses = new HashSet<Course>();
720                for (Iterator<?> j = studentEl.elementIterator("studentCourse"); j.hasNext();) {
721                    Element courseEl = (Element) j.next();
722                    String subjectArea = courseEl.attributeValue("subject");
723                    String courseNbr = courseEl.attributeValue("courseNumber");
724                    Course course = null;
725                    offerings: for (Offering offering : model.getOfferings()) {
726                        for (Course c : offering.getCourses()) {
727                            if (c.getSubjectArea().equals(subjectArea) && c.getCourseNumber().equals(courseNbr)) {
728                                course = c;
729                                break offerings;
730                            }
731                        }
732                    }
733                    if (course == null && courseNbr.charAt(courseNbr.length() - 1) >= 'A'
734                            && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') {
735                        String courseNbrNoSfx = courseNbr.substring(0, courseNbr.length() - 1);
736                        offerings: for (Offering offering : model.getOfferings()) {
737                            for (Course c : offering.getCourses()) {
738                                if (c.getSubjectArea().equals(subjectArea)
739                                        && c.getCourseNumber().equals(courseNbrNoSfx)) {
740                                    course = c;
741                                    break offerings;
742                                }
743                            }
744                        }
745                    }
746                    if (course == null) {
747                        sLog.warn("Course " + subjectArea + " " + courseNbr + " not found.");
748                    } else {
749                        if (!reqCourses.add(course)) {
750                            sLog.warn("Course " + subjectArea + " " + courseNbr + " already requested.");
751                        } else {
752                            List<Course> courses = new ArrayList<Course>(1);
753                            courses.add(course);
754                            CourseRequest request = new CourseRequest(reqId++, priority++, false, student, courses, false, null);
755                            List<Request> requestsThisCourse = requests.get(course);
756                            if (requestsThisCourse == null) {
757                                requestsThisCourse = new ArrayList<Request>();
758                                requests.put(course, requestsThisCourse);
759                            }
760                            requestsThisCourse.add(request);
761                        }
762                    }
763                }
764                if (!student.getRequests().isEmpty())
765                    model.addStudent(student);
766            }
767            for (Map.Entry<Course, List<Request>> entry : requests.entrySet()) {
768                Course course = entry.getKey();
769                List<Request> requestsThisCourse = entry.getValue();
770                double weight = getLastLikeStudentWeight(course, 0, requestsThisCourse.size());
771                for (Request request : requestsThisCourse) {
772                    request.setWeight(weight);
773                }
774            }
775        } catch (Exception e) {
776            sLog.error(e.getMessage(), e);
777        }
778    }
779
780    /**
781     * Load course request from the given files (in the format being used by the
782     * old MSF system)
783     * 
784     * @param model
785     *            student sectioning model (with offerings loaded)
786     * @param files
787     *            semi-colon separated list of files to be loaded
788     */
789    public static void loadCrsReqFiles(StudentSectioningModel model, String files) {
790        try {
791            boolean lastLike = model.getProperties().getPropertyBoolean("Test.CrsReqIsLastLike", true);
792            boolean shuffleIds = model.getProperties().getPropertyBoolean("Test.CrsReqShuffleStudentIds", true);
793            boolean tryWithoutSuffix = model.getProperties().getPropertyBoolean("Test.CrsReqTryWithoutSuffix", false);
794            HashMap<Long, Student> students = new HashMap<Long, Student>();
795            long reqId = 0;
796            for (StringTokenizer stk = new StringTokenizer(files, ";"); stk.hasMoreTokens();) {
797                String file = stk.nextToken();
798                sLog.debug("Loading " + file + " ...");
799                BufferedReader in = new BufferedReader(new FileReader(file));
800                String line;
801                int lineIndex = 0;
802                while ((line = in.readLine()) != null) {
803                    lineIndex++;
804                    if (line.length() <= 150)
805                        continue;
806                    char code = line.charAt(13);
807                    if (code == 'H' || code == 'T')
808                        continue; // skip header and tail
809                    long studentId = Long.parseLong(line.substring(14, 23));
810                    Student student = students.get(new Long(studentId));
811                    if (student == null) {
812                        student = new Student(studentId);
813                        if (lastLike)
814                            student.setDummy(true);
815                        students.put(new Long(studentId), student);
816                        sLog.debug("  -- loading student " + studentId + " ...");
817                    } else
818                        sLog.debug("  -- updating student " + studentId + " ...");
819                    line = line.substring(150);
820                    while (line.length() >= 20) {
821                        String subjectArea = line.substring(0, 4).trim();
822                        String courseNbr = line.substring(4, 8).trim();
823                        if (subjectArea.length() == 0 || courseNbr.length() == 0) {
824                            line = line.substring(20);
825                            continue;
826                        }
827                        /*
828                         * // UNUSED String instrSel = line.substring(8,10);
829                         * //ZZ - Remove previous instructor selection char
830                         * reqPDiv = line.charAt(10); //P - Personal preference;
831                         * C - Conflict resolution; //0 - (Zero) used by program
832                         * only, for change requests to reschedule division //
833                         * (used to reschedule canceled division) String reqDiv
834                         * = line.substring(11,13); //00 - Reschedule division
835                         * String reqSect = line.substring(13,15); //Contains
836                         * designator for designator-required courses String
837                         * credit = line.substring(15,19); char nameRaise =
838                         * line.charAt(19); //N - Name raise
839                         */
840                        char action = line.charAt(19); // A - Add; D - Drop; C -
841                                                       // Change
842                        sLog.debug("    -- requesting " + subjectArea + " " + courseNbr + " (action:" + action
843                                + ") ...");
844                        Course course = null;
845                        offerings: for (Offering offering : model.getOfferings()) {
846                            for (Course c : offering.getCourses()) {
847                                if (c.getSubjectArea().equals(subjectArea) && c.getCourseNumber().equals(courseNbr)) {
848                                    course = c;
849                                    break offerings;
850                                }
851                            }
852                        }
853                        if (course == null && tryWithoutSuffix && courseNbr.charAt(courseNbr.length() - 1) >= 'A'
854                                && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') {
855                            String courseNbrNoSfx = courseNbr.substring(0, courseNbr.length() - 1);
856                            offerings: for (Offering offering : model.getOfferings()) {
857                                for (Course c : offering.getCourses()) {
858                                    if (c.getSubjectArea().equals(subjectArea)
859                                            && c.getCourseNumber().equals(courseNbrNoSfx)) {
860                                        course = c;
861                                        break offerings;
862                                    }
863                                }
864                            }
865                        }
866                        if (course == null) {
867                            if (courseNbr.charAt(courseNbr.length() - 1) >= 'A'
868                                    && courseNbr.charAt(courseNbr.length() - 1) <= 'Z') {
869                            } else {
870                                sLog.warn("      -- course " + subjectArea + " " + courseNbr + " not found (file "
871                                        + file + ", line " + lineIndex + ")");
872                            }
873                        } else {
874                            CourseRequest courseRequest = null;
875                            for (Request request : student.getRequests()) {
876                                if (request instanceof CourseRequest
877                                        && ((CourseRequest) request).getCourses().contains(course)) {
878                                    courseRequest = (CourseRequest) request;
879                                    break;
880                                }
881                            }
882                            if (action == 'A') {
883                                if (courseRequest == null) {
884                                    List<Course> courses = new ArrayList<Course>(1);
885                                    courses.add(course);
886                                    courseRequest = new CourseRequest(reqId++, student.getRequests().size(), false, student, courses, false, null);
887                                } else {
888                                    sLog.warn("      -- request for course " + course + " is already present");
889                                }
890                            } else if (action == 'D') {
891                                if (courseRequest == null) {
892                                    sLog.warn("      -- request for course " + course
893                                            + " is not present -- cannot be dropped");
894                                } else {
895                                    student.getRequests().remove(courseRequest);
896                                }
897                            } else if (action == 'C') {
898                                if (courseRequest == null) {
899                                    sLog.warn("      -- request for course " + course
900                                            + " is not present -- cannot be changed");
901                                } else {
902                                    // ?
903                                }
904                            } else {
905                                sLog.warn("      -- unknown action " + action);
906                            }
907                        }
908                        line = line.substring(20);
909                    }
910                }
911                in.close();
912            }
913            HashMap<Course, List<Request>> requests = new HashMap<Course, List<Request>>();
914            Set<Long> studentIds = new HashSet<Long>();
915            for (Student student: students.values()) {
916                if (!student.getRequests().isEmpty())
917                    model.addStudent(student);
918                if (shuffleIds) {
919                    long newId = -1;
920                    while (true) {
921                        newId = 1 + (long) (999999999L * Math.random());
922                        if (studentIds.add(new Long(newId)))
923                            break;
924                    }
925                    student.setId(newId);
926                }
927                if (student.isDummy()) {
928                    for (Request request : student.getRequests()) {
929                        if (request instanceof CourseRequest) {
930                            Course course = ((CourseRequest) request).getCourses().get(0);
931                            List<Request> requestsThisCourse = requests.get(course);
932                            if (requestsThisCourse == null) {
933                                requestsThisCourse = new ArrayList<Request>();
934                                requests.put(course, requestsThisCourse);
935                            }
936                            requestsThisCourse.add(request);
937                        }
938                    }
939                }
940            }
941            Collections.sort(model.getStudents(), new Comparator<Student>() {
942                @Override
943                public int compare(Student o1, Student o2) {
944                    return Double.compare(o1.getId(), o2.getId());
945                }
946            });
947            for (Map.Entry<Course, List<Request>> entry : requests.entrySet()) {
948                Course course = entry.getKey();
949                List<Request> requestsThisCourse = entry.getValue();
950                double weight = getLastLikeStudentWeight(course, 0, requestsThisCourse.size());
951                for (Request request : requestsThisCourse) {
952                    request.setWeight(weight);
953                }
954            }
955            if (model.getProperties().getProperty("Test.EtrChk") != null) {
956                for (StringTokenizer stk = new StringTokenizer(model.getProperties().getProperty("Test.EtrChk"), ";"); stk
957                        .hasMoreTokens();) {
958                    String file = stk.nextToken();
959                    sLog.debug("Loading " + file + " ...");
960                    BufferedReader in = new BufferedReader(new FileReader(file));
961                    try {
962                        String line;
963                        while ((line = in.readLine()) != null) {
964                            if (line.length() < 55)
965                                continue;
966                            char code = line.charAt(12);
967                            if (code == 'H' || code == 'T')
968                                continue; // skip header and tail
969                            if (code == 'D' || code == 'K')
970                                continue; // skip delete nad cancel
971                            long studentId = Long.parseLong(line.substring(2, 11));
972                            Student student = students.get(new Long(studentId));
973                            if (student == null) {
974                                sLog.info("  -- student " + studentId + " not found");
975                                continue;
976                            }
977                            sLog.info("  -- reading student " + studentId);
978                            String area = line.substring(15, 18).trim();
979                            if (area.length() == 0)
980                                continue;
981                            String clasf = line.substring(18, 20).trim();
982                            String major = line.substring(21, 24).trim();
983                            String minor = line.substring(24, 27).trim();
984                            student.getAcademicAreaClasiffications().clear();
985                            student.getMajors().clear();
986                            student.getMinors().clear();
987                            student.getAcademicAreaClasiffications().add(new AcademicAreaCode(area, clasf));
988                            if (major.length() > 0)
989                                student.getMajors().add(new AcademicAreaCode(area, major));
990                            if (minor.length() > 0)
991                                student.getMinors().add(new AcademicAreaCode(area, minor));
992                        }
993                    } finally {
994                        in.close();
995                    }
996                }
997            }
998            int without = 0;
999            for (Student student: students.values()) {
1000                if (student.getAcademicAreaClasiffications().isEmpty())
1001                    without++;
1002            }
1003            fixPriorities(model);
1004            sLog.info("Students without academic area: " + without);
1005        } catch (Exception e) {
1006            sLog.error(e.getMessage(), e);
1007        }
1008    }
1009
1010    public static void fixPriorities(StudentSectioningModel model) {
1011        for (Student student : model.getStudents()) {
1012            Collections.sort(student.getRequests(), new Comparator<Request>() {
1013                @Override
1014                public int compare(Request r1, Request r2) {
1015                    int cmp = Double.compare(r1.getPriority(), r2.getPriority());
1016                    if (cmp != 0)
1017                        return cmp;
1018                    return Double.compare(r1.getId(), r2.getId());
1019                }
1020            });
1021            int priority = 0;
1022            for (Request request : student.getRequests()) {
1023                if (priority != request.getPriority()) {
1024                    sLog.debug("Change priority of " + request + " to " + priority);
1025                    request.setPriority(priority);
1026                }
1027            }
1028        }
1029    }
1030
1031    /** Load student infos from a given XML file. 
1032     * @param model problem model
1033     * @param xml an XML file
1034     **/
1035    public static void loadStudentInfoXml(StudentSectioningModel model, File xml) {
1036        try {
1037            sLog.info("Loading student infos from " + xml);
1038            Document document = (new SAXReader()).read(xml);
1039            Element root = document.getRootElement();
1040            HashMap<Long, Student> studentTable = new HashMap<Long, Student>();
1041            for (Student student : model.getStudents()) {
1042                studentTable.put(new Long(student.getId()), student);
1043            }
1044            for (Iterator<?> i = root.elementIterator("student"); i.hasNext();) {
1045                Element studentEl = (Element) i.next();
1046                Student student = studentTable.get(Long.valueOf(studentEl.attributeValue("externalId")));
1047                if (student == null) {
1048                    sLog.debug(" -- student " + studentEl.attributeValue("externalId") + " not found");
1049                    continue;
1050                }
1051                sLog.debug(" -- loading info for student " + student);
1052                student.getAcademicAreaClasiffications().clear();
1053                if (studentEl.element("studentAcadAreaClass") != null)
1054                    for (Iterator<?> j = studentEl.element("studentAcadAreaClass").elementIterator("acadAreaClass"); j
1055                            .hasNext();) {
1056                        Element studentAcadAreaClassElement = (Element) j.next();
1057                        student.getAcademicAreaClasiffications().add(
1058                                new AcademicAreaCode(studentAcadAreaClassElement.attributeValue("academicArea"),
1059                                        studentAcadAreaClassElement.attributeValue("academicClass")));
1060                    }
1061                sLog.debug("   -- acad areas classifs " + student.getAcademicAreaClasiffications());
1062                student.getMajors().clear();
1063                if (studentEl.element("studentMajors") != null)
1064                    for (Iterator<?> j = studentEl.element("studentMajors").elementIterator("major"); j.hasNext();) {
1065                        Element studentMajorElement = (Element) j.next();
1066                        student.getMajors().add(
1067                                new AcademicAreaCode(studentMajorElement.attributeValue("academicArea"),
1068                                        studentMajorElement.attributeValue("code")));
1069                    }
1070                sLog.debug("   -- majors " + student.getMajors());
1071                student.getMinors().clear();
1072                if (studentEl.element("studentMinors") != null)
1073                    for (Iterator<?> j = studentEl.element("studentMinors").elementIterator("minor"); j.hasNext();) {
1074                        Element studentMinorElement = (Element) j.next();
1075                        student.getMinors().add(
1076                                new AcademicAreaCode(studentMinorElement.attributeValue("academicArea", ""),
1077                                        studentMinorElement.attributeValue("code", "")));
1078                    }
1079                sLog.debug("   -- minors " + student.getMinors());
1080            }
1081        } catch (Exception e) {
1082            sLog.error(e.getMessage(), e);
1083        }
1084    }
1085
1086    /** Save solution info as XML 
1087     * @param solution current solution
1088     * @param extra solution extra info
1089     * @param file file to write
1090     **/
1091    public static void saveInfoToXML(Solution<Request, Enrollment> solution, Map<String, String> extra, File file) {
1092        FileOutputStream fos = null;
1093        try {
1094            Document document = DocumentHelper.createDocument();
1095            document.addComment("Solution Info");
1096
1097            Element root = document.addElement("info");
1098            TreeSet<Map.Entry<String, String>> entrySet = new TreeSet<Map.Entry<String, String>>(
1099                    new Comparator<Map.Entry<String, String>>() {
1100                        @Override
1101                        public int compare(Map.Entry<String, String> e1, Map.Entry<String, String> e2) {
1102                            return e1.getKey().compareTo(e2.getKey());
1103                        }
1104                    });
1105            entrySet.addAll(solution.getExtendedInfo().entrySet());
1106            if (extra != null)
1107                entrySet.addAll(extra.entrySet());
1108            for (Map.Entry<String, String> entry : entrySet) {
1109                root.addElement("property").addAttribute("name", entry.getKey()).setText(entry.getValue());
1110            }
1111
1112            fos = new FileOutputStream(file);
1113            (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(document);
1114            fos.flush();
1115            fos.close();
1116            fos = null;
1117        } catch (Exception e) {
1118            sLog.error("Unable to save info, reason: " + e.getMessage(), e);
1119        } finally {
1120            try {
1121                if (fos != null)
1122                    fos.close();
1123            } catch (IOException e) {
1124            }
1125        }
1126    }
1127
1128    private static void fixWeights(StudentSectioningModel model) {
1129        HashMap<Course, Integer> lastLike = new HashMap<Course, Integer>();
1130        HashMap<Course, Integer> real = new HashMap<Course, Integer>();
1131        HashSet<Long> lastLikeIds = new HashSet<Long>();
1132        HashSet<Long> realIds = new HashSet<Long>();
1133        for (Student student : model.getStudents()) {
1134            if (student.isDummy()) {
1135                if (!lastLikeIds.add(new Long(student.getId()))) {
1136                    sLog.error("Two last-like student with id " + student.getId());
1137                }
1138            } else {
1139                if (!realIds.add(new Long(student.getId()))) {
1140                    sLog.error("Two real student with id " + student.getId());
1141                }
1142            }
1143            for (Request request : student.getRequests()) {
1144                if (request instanceof CourseRequest) {
1145                    CourseRequest courseRequest = (CourseRequest) request;
1146                    Course course = courseRequest.getCourses().get(0);
1147                    Integer cnt = (student.isDummy() ? lastLike : real).get(course);
1148                    (student.isDummy() ? lastLike : real).put(course, new Integer(
1149                            (cnt == null ? 0 : cnt.intValue()) + 1));
1150                }
1151            }
1152        }
1153        for (Student student : new ArrayList<Student>(model.getStudents())) {
1154            if (student.isDummy() && realIds.contains(new Long(student.getId()))) {
1155                sLog.warn("There is both last-like and real student with id " + student.getId());
1156                long newId = -1;
1157                while (true) {
1158                    newId = 1 + (long) (999999999L * Math.random());
1159                    if (!realIds.contains(new Long(newId)) && !lastLikeIds.contains(new Long(newId)))
1160                        break;
1161                }
1162                lastLikeIds.remove(new Long(student.getId()));
1163                lastLikeIds.add(new Long(newId));
1164                student.setId(newId);
1165                sLog.warn("  -- last-like student id changed to " + student.getId());
1166            }
1167            for (Request request : new ArrayList<Request>(student.getRequests())) {
1168                if (!student.isDummy()) {
1169                    request.setWeight(1.0);
1170                    continue;
1171                }
1172                if (request instanceof CourseRequest) {
1173                    CourseRequest courseRequest = (CourseRequest) request;
1174                    Course course = courseRequest.getCourses().get(0);
1175                    Integer lastLikeCnt = lastLike.get(course);
1176                    Integer realCnt = real.get(course);
1177                    courseRequest.setWeight(getLastLikeStudentWeight(course, realCnt == null ? 0 : realCnt.intValue(),
1178                            lastLikeCnt == null ? 0 : lastLikeCnt.intValue()));
1179                } else
1180                    request.setWeight(1.0);
1181                if (request.getWeight() <= 0.0) {
1182                    model.removeVariable(request);
1183                    student.getRequests().remove(request);
1184                }
1185            }
1186            if (student.getRequests().isEmpty()) {
1187                model.getStudents().remove(student);
1188            }
1189        }
1190    }
1191
1192    /** Combine students from the provided two files 
1193     * @param cfg solver configuration
1194     * @param lastLikeStudentData a file containing last-like student data
1195     * @param realStudentData a file containing real student data
1196     * @return combined solution
1197     **/
1198    public static Solution<Request, Enrollment> combineStudents(DataProperties cfg, File lastLikeStudentData, File realStudentData) {
1199        try {
1200            RandomStudentFilter rnd = new RandomStudentFilter(1.0);
1201
1202            StudentSectioningModel model = null;
1203            Assignment<Request, Enrollment> assignment = new DefaultSingleAssignment<Request, Enrollment>();
1204
1205            for (StringTokenizer stk = new StringTokenizer(cfg.getProperty("Test.CombineAcceptProb", "1.0"), ","); stk.hasMoreTokens();) {
1206                double acceptProb = Double.parseDouble(stk.nextToken());
1207                sLog.info("Test.CombineAcceptProb=" + acceptProb);
1208                rnd.setProbability(acceptProb);
1209
1210                StudentFilter batchFilter = new CombinedStudentFilter(new ReverseStudentFilter(
1211                        new FreshmanStudentFilter()), rnd, CombinedStudentFilter.OP_AND);
1212
1213                model = new StudentSectioningModel(cfg);
1214                StudentSectioningXMLLoader loader = new StudentSectioningXMLLoader(model, assignment);
1215                loader.setLoadStudents(false);
1216                loader.load();
1217
1218                StudentSectioningXMLLoader lastLikeLoader = new StudentSectioningXMLLoader(model, assignment);
1219                lastLikeLoader.setInputFile(lastLikeStudentData);
1220                lastLikeLoader.setLoadOfferings(false);
1221                lastLikeLoader.setLoadStudents(true);
1222                lastLikeLoader.load();
1223
1224                StudentSectioningXMLLoader realLoader = new StudentSectioningXMLLoader(model, assignment);
1225                realLoader.setInputFile(realStudentData);
1226                realLoader.setLoadOfferings(false);
1227                realLoader.setLoadStudents(true);
1228                realLoader.setStudentFilter(batchFilter);
1229                realLoader.load();
1230
1231                fixWeights(model);
1232
1233                fixPriorities(model);
1234
1235                Solver<Request, Enrollment> solver = new Solver<Request, Enrollment>(model.getProperties());
1236                solver.setInitalSolution(model);
1237                new StudentSectioningXMLSaver(solver).save(new File(new File(model.getProperties().getProperty(
1238                        "General.Output", ".")), "solution-r" + ((int) (100.0 * acceptProb)) + ".xml"));
1239
1240            }
1241
1242            return model == null ? null : new Solution<Request, Enrollment>(model, assignment);
1243
1244        } catch (Exception e) {
1245            sLog.error("Unable to combine students, reason: " + e.getMessage(), e);
1246            return null;
1247        }
1248    }
1249    
1250    /**
1251     * Setup log4j logging
1252     * 
1253     * @param logFile  log file
1254     */
1255    public static void setupLogging(File logFile) {
1256        Logger root = Logger.getRootLogger();
1257        ConsoleAppender console = new ConsoleAppender(new PatternLayout("[%t] %m%n"));
1258        console.setThreshold(Level.INFO);
1259        root.addAppender(console);
1260        if (logFile != null) {
1261            try {
1262                FileAppender file = new FileAppender(new PatternLayout("%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n"), logFile.getPath(), false);
1263                file.setThreshold(Level.DEBUG);
1264                root.addAppender(file);
1265            } catch (IOException e) {
1266                sLog.fatal("Unable to configure logging, reason: " + e.getMessage(), e);
1267            }
1268        }
1269    }
1270
1271    /** Main 
1272     * @param args program arguments
1273     **/
1274    public static void main(String[] args) {
1275        try {
1276            DataProperties cfg = new DataProperties();
1277            cfg.setProperty("Termination.Class", "org.cpsolver.ifs.termination.GeneralTerminationCondition");
1278            cfg.setProperty("Termination.StopWhenComplete", "true");
1279            cfg.setProperty("Termination.TimeOut", "600");
1280            cfg.setProperty("Comparator.Class", "org.cpsolver.ifs.solution.GeneralSolutionComparator");
1281            cfg.setProperty("Value.Class", "org.cpsolver.studentsct.heuristics.EnrollmentSelection");// org.cpsolver.ifs.heuristics.GeneralValueSelection
1282            cfg.setProperty("Value.WeightConflicts", "1.0");
1283            cfg.setProperty("Value.WeightNrAssignments", "0.0");
1284            cfg.setProperty("Variable.Class", "org.cpsolver.ifs.heuristics.GeneralVariableSelection");
1285            cfg.setProperty("Neighbour.Class", "org.cpsolver.studentsct.heuristics.StudentSctNeighbourSelection");
1286            cfg.setProperty("General.SaveBestUnassigned", "0");
1287            cfg.setProperty("Extensions.Classes",
1288                    "org.cpsolver.ifs.extension.ConflictStatistics;org.cpsolver.studentsct.extension.DistanceConflict" +
1289                    ";org.cpsolver.studentsct.extension.TimeOverlapsCounter");
1290            cfg.setProperty("Data.Initiative", "puWestLafayetteTrdtn");
1291            cfg.setProperty("Data.Term", "Fal");
1292            cfg.setProperty("Data.Year", "2007");
1293            cfg.setProperty("General.Input", "pu-sectll-fal07-s.xml");
1294            if (args.length >= 1) {
1295                cfg.load(new FileInputStream(args[0]));
1296            }
1297            cfg.putAll(System.getProperties());
1298
1299            if (args.length >= 2) {
1300                cfg.setProperty("General.Input", args[1]);
1301            }
1302
1303            File outDir = null;
1304            if (args.length >= 3) {
1305                outDir = new File(args[2], sDateFormat.format(new Date()));
1306            } else if (cfg.getProperty("General.Output") != null) {
1307                outDir = new File(cfg.getProperty("General.Output", "."), sDateFormat.format(new Date()));
1308            } else {
1309                outDir = new File(System.getProperty("user.home", ".") + File.separator + "Sectioning-Test" + File.separator + (sDateFormat.format(new Date())));
1310            }
1311            outDir.mkdirs();
1312            setupLogging(new File(outDir, "debug.log"));
1313            cfg.setProperty("General.Output", outDir.getAbsolutePath());
1314
1315            if (args.length >= 4 && "online".equals(args[3])) {
1316                onlineSectioning(cfg);
1317            } else if (args.length >= 4 && "simple".equals(args[3])) {
1318                cfg.setProperty("Sectioning.UseOnlinePenalties", "false");
1319                onlineSectioning(cfg);
1320            } else {
1321                batchSectioning(cfg);
1322            }
1323        } catch (Exception e) {
1324            sLog.error(e.getMessage(), e);
1325            e.printStackTrace();
1326        }
1327    }
1328
1329    public static class ExtraStudentFilter implements StudentFilter {
1330        HashSet<Long> iIds = new HashSet<Long>();
1331
1332        public ExtraStudentFilter(StudentSectioningModel model) {
1333            for (Student student : model.getStudents()) {
1334                iIds.add(new Long(student.getId()));
1335            }
1336        }
1337
1338        @Override
1339        public boolean accept(Student student) {
1340            return !iIds.contains(new Long(student.getId()));
1341        }
1342
1343        @Override
1344        public String getName() {
1345            return "Extra";
1346        }
1347    }
1348
1349    public static class TestSolutionListener implements SolutionListener<Request, Enrollment> {
1350        @Override
1351        public void solutionUpdated(Solution<Request, Enrollment> solution) {
1352            StudentSectioningModel m = (StudentSectioningModel) solution.getModel();
1353            if (m.getTimeOverlaps() != null && TimeOverlapsCounter.sDebug)
1354                m.getTimeOverlaps().checkTotalNrConflicts(solution.getAssignment());
1355            if (m.getDistanceConflict() != null && DistanceConflict.sDebug)
1356                m.getDistanceConflict().checkAllConflicts(solution.getAssignment());
1357            if (m.getStudentQuality() != null && m.getStudentQuality().isDebug())
1358                m.getStudentQuality().checkTotalPenalty(solution.getAssignment());
1359        }
1360
1361        @Override
1362        public void getInfo(Solution<Request, Enrollment> solution, Map<String, String> info) {
1363        }
1364
1365        @Override
1366        public void getInfo(Solution<Request, Enrollment> solution, Map<String, String> info, Collection<Request> variables) {
1367        }
1368
1369        @Override
1370        public void bestCleared(Solution<Request, Enrollment> solution) {
1371        }
1372
1373        @Override
1374        public void bestSaved(Solution<Request, Enrollment> solution) {
1375            sLog.info("**BEST** " + ((StudentSectioningModel)solution.getModel()).toString(solution.getAssignment()) + ", TM:" + sDF.format(solution.getTime() / 3600.0) + "h" +
1376                    (solution.getFailedIterations() > 0 ? ", F:" + sDF.format(100.0 * solution.getFailedIterations() / solution.getIteration()) + "%" : ""));
1377        }
1378
1379        @Override
1380        public void bestRestored(Solution<Request, Enrollment> solution) {
1381        }
1382    }
1383    
1384    private static class ShutdownHook extends Thread {
1385        Solver<Request, Enrollment> iSolver = null;
1386        Map<String, String> iExtra = null;
1387
1388        private ShutdownHook(Solver<Request, Enrollment> solver) {
1389            setName("ShutdownHook");
1390            iSolver = solver;
1391        }
1392        
1393        void setExtra(Map<String, String> extra) { iExtra = extra; }
1394        
1395        @Override
1396        public void run() {
1397            try {
1398                if (iSolver.isRunning()) iSolver.stopSolver();
1399                Solution<Request, Enrollment> solution = iSolver.lastSolution();
1400                solution.restoreBest();
1401                DataProperties cfg = iSolver.getProperties();
1402                
1403                printInfo(solution,
1404                        cfg.getPropertyBoolean("Test.CreateReports", true),
1405                        cfg.getPropertyBoolean("Test.ComputeSectioningInfo", true),
1406                        cfg.getPropertyBoolean("Test.RunChecks", true));
1407
1408                try {
1409                    new StudentSectioningXMLSaver(iSolver).save(new File(new File(cfg.getProperty("General.Output", ".")), "solution.xml"));
1410                } catch (Exception e) {
1411                    sLog.error("Unable to save solution, reason: " + e.getMessage(), e);
1412                }
1413                
1414                saveInfoToXML(solution, iExtra, new File(new File(cfg.getProperty("General.Output", ".")), "info.xml"));
1415                
1416                Progress.removeInstance(solution.getModel());
1417            } catch (Throwable t) {
1418                sLog.error("Test failed.", t);
1419            }
1420        }
1421    }
1422
1423}