001package org.cpsolver.studentsct.online;
002
003import java.io.File;
004import java.io.FileWriter;
005import java.io.IOException;
006import java.io.PrintWriter;
007import java.text.DecimalFormat;
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.HashMap;
011import java.util.HashSet;
012import java.util.Hashtable;
013import java.util.Iterator;
014import java.util.List;
015import java.util.Map;
016import java.util.NoSuchElementException;
017import java.util.Set;
018import java.util.TreeSet;
019
020import org.apache.logging.log4j.Logger;
021import org.cpsolver.ifs.assignment.Assignment;
022import org.cpsolver.ifs.assignment.AssignmentMap;
023import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
024import org.cpsolver.ifs.solver.Solver;
025import org.cpsolver.ifs.util.DataProperties;
026import org.cpsolver.ifs.util.DistanceMetric;
027import org.cpsolver.ifs.util.JProf;
028import org.cpsolver.ifs.util.ToolBox;
029import org.cpsolver.studentsct.StudentPreferencePenalties;
030import org.cpsolver.studentsct.StudentSectioningModel;
031import org.cpsolver.studentsct.StudentSectioningXMLLoader;
032import org.cpsolver.studentsct.StudentSectioningXMLSaver;
033import org.cpsolver.studentsct.constraint.LinkedSections;
034import org.cpsolver.studentsct.extension.DistanceConflict;
035import org.cpsolver.studentsct.extension.StudentQuality;
036import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
037import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour;
038import org.cpsolver.studentsct.heuristics.studentord.StudentChoiceOrder;
039import org.cpsolver.studentsct.model.Config;
040import org.cpsolver.studentsct.model.Course;
041import org.cpsolver.studentsct.model.CourseRequest;
042import org.cpsolver.studentsct.model.Enrollment;
043import org.cpsolver.studentsct.model.FreeTimeRequest;
044import org.cpsolver.studentsct.model.Offering;
045import org.cpsolver.studentsct.model.Request;
046import org.cpsolver.studentsct.model.Section;
047import org.cpsolver.studentsct.model.Student;
048import org.cpsolver.studentsct.model.Subpart;
049import org.cpsolver.studentsct.online.expectations.AvoidUnbalancedWhenNoExpectations;
050import org.cpsolver.studentsct.online.expectations.FractionallyOverExpected;
051import org.cpsolver.studentsct.online.expectations.FractionallyUnbalancedWhenNoExpectations;
052import org.cpsolver.studentsct.online.expectations.PercentageOverExpected;
053import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection;
054import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSuggestions;
055import org.cpsolver.studentsct.online.selection.OnlineSectioningSelection;
056import org.cpsolver.studentsct.online.selection.StudentSchedulingAssistantWeights;
057import org.cpsolver.studentsct.online.selection.SuggestionSelection;
058import org.cpsolver.studentsct.online.selection.SuggestionsBranchAndBound;
059import org.cpsolver.studentsct.reservation.CourseReservation;
060import org.cpsolver.studentsct.reservation.Reservation;
061
062/**
063 * An online student sectioning test. It loads the given problem (passed as the only argument) with no assignments. It sections all
064 * students in the given order (given by -Dsort parameter, values shuffle, choice, reverse). Multiple threads can be used to section
065 * students in parallel (given by -DnrConcurrent parameter). If parameter -Dsuggestions is set to true, the test also asks for suggestions
066 * for each of the assigned class, preferring mid-day times. Over-expected criterion can be defined by the -Doverexp parameter (see the
067 * examples bellow). Multi-criteria selection can be enabled by -DStudentWeights.MultiCriteria=true and equal weighting can be set by
068 * -DStudentWeights.PriorityWeighting=equal).
069 * 
070 * <br><br>
071 * Usage:<ul>
072 *      java -Xmx1g -cp studentsct-1.3.jar [parameters] org.cpsolver.studentsct.online.Test data/pu-sect-fal07.xml<br>
073 * </ul>
074 * Parameters:<ul>
075 *      <li>-Dsort=shuffle|choice|reverse ... for taking students in random order, more choices first, or more choices last (defaults to shuffle)
076 *      <li>-DnrConcurrent=N ... for the number of threads (concurrent computations of student schedules, defaults to 10)
077 *      <li>-Dsuggestions=true|false ... true to use suggestions (to simulate students preferring mid-day, defaults to false)
078 *      <li>-Doverexp=<i>x<sub>over</sub></i>|b<i>x<sub>over</sub></i>-<i>x<sub>disb</sub></i>%|<i>x<sub>over</sub></i>-<i>x<sub>max</sub></i>|b<i>x<sub>over</sub></i>-<i>x<sub>max</sub></i>-<i>x<sub>disb</sub></i>% for over-expected criterion, examples:<ul>
079 *              <li>1.1 ... {@link PercentageOverExpected} with OverExpected.Percentage set to 1.1 (<i>x<sub>over</sub></i>)
080 *              <li>b1-10 ... {@link AvoidUnbalancedWhenNoExpectations} with OverExpected.Percentage set to 1 and General.BalanceUnlimited set to 10/100 (<i>x<sub>disb</sub></i>%)
081 *              <li>0.85-5 ... {@link FractionallyOverExpected} with OverExpected.Percentage set to 0.85 and OverExpected.Maximum set to 5 (<i>x<sub>max</sub></i>)
082 *              <li>1.1-5-1 ... {@link FractionallyUnbalancedWhenNoExpectations} with OverExpected.Percentage set to 1.1, General.BalanceUnlimited set to 5/100, and OverExpected.Maximum set to 1
083 *      </ul>
084 *      <li>-DStudentWeights.PriorityWeighting=priority|equal ... priority or equal weighting (defaults to priority)
085 *      <li>-DStudentWeights.MultiCriteria=true|false ... true for multi-criteria (lexicographic ordering), false for a weighted sum (default to true)
086 *      <li>-DNeighbour.BranchAndBoundTimeout=M ... time limit for each student in milliseconds (CPU time, defaults to 1000)
087 * </ul>
088 * 
089 * @version StudentSct 1.3 (Student Sectioning)<br>
090 *          Copyright (C) 2014 Tomáš Müller<br>
091 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
092 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
093 * <br>
094 *          This library is free software; you can redistribute it and/or modify
095 *          it under the terms of the GNU Lesser General Public License as
096 *          published by the Free Software Foundation; either version 3 of the
097 *          License, or (at your option) any later version. <br>
098 * <br>
099 *          This library is distributed in the hope that it will be useful, but
100 *          WITHOUT ANY WARRANTY; without even the implied warranty of
101 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
102 *          Lesser General Public License for more details. <br>
103 * <br>
104 *          You should have received a copy of the GNU Lesser General Public
105 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
106 * 
107 */
108public class Test {
109    public static DecimalFormat sDF = new DecimalFormat("0.00000");
110    public static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(Test.class);
111
112    private OnlineSectioningModel iModel;
113    private Assignment<Request, Enrollment> iAssignment;
114    private boolean iSuggestions = false;
115
116    private Map<String, Counter> iCounters = new HashMap<String, Counter>();
117
118    public Test(DataProperties config) {
119        iModel = new TestModel(config);
120        iModel.setDistanceConflict(new DistanceConflict(new DistanceMetric(iModel.getProperties()), iModel.getProperties()));
121        iModel.getDistanceConflict().register(iModel);
122        iModel.getDistanceConflict().setAssignmentContextReference(iModel.createReference(iModel.getDistanceConflict()));
123        iModel.setTimeOverlaps(new TimeOverlapsCounter(null, iModel.getProperties()));
124        iModel.getTimeOverlaps().register(iModel);
125        iModel.getTimeOverlaps().setAssignmentContextReference(iModel.createReference(iModel.getTimeOverlaps()));
126        iModel.setStudentQuality(new StudentQuality(new DistanceMetric(iModel.getProperties()), iModel.getProperties()));
127        iModel.getStudentQuality().register(iModel);
128        iModel.getStudentQuality().setAssignmentContextReference(iModel.createReference(iModel.getStudentQuality()));
129        iModel.setStudentWeights(new StudentSchedulingAssistantWeights(iModel.getProperties()));
130        iAssignment = new DefaultSingleAssignment<Request, Enrollment>();
131        iSuggestions = "true".equals(System.getProperty("suggestions", iSuggestions ? "true" : "false"));
132
133        String overexp = System.getProperty("overexp");
134        if (overexp != null) {
135            boolean bal = false;
136            if (overexp.startsWith("b")) {
137                bal = true;
138                overexp = overexp.substring(1);
139            }
140            String[] x = overexp.split("[/\\-]");
141            if (x.length == 1) {
142                iModel.setOverExpectedCriterion(new PercentageOverExpected(Double.valueOf(x[0])));
143            } else if (x.length == 2) {
144                iModel.setOverExpectedCriterion(bal ? new AvoidUnbalancedWhenNoExpectations(Double.valueOf(x[0]), Double.valueOf(x[1]) / 100.0) :
145                    new FractionallyOverExpected(Double.valueOf(x[0]), Double.valueOf(x[1])));
146            } else {
147                iModel.setOverExpectedCriterion(new FractionallyUnbalancedWhenNoExpectations(Double.valueOf(x[0]),
148                        Double.valueOf(x[1]), Double.valueOf(x[2]) / 100.0));
149            }
150        }
151
152        sLog.info("Using " + (config.getPropertyBoolean("StudentWeights.MultiCriteria", true) ? "multi-criteria " : "")
153                + (config.getPropertyBoolean("StudentWeights.PriorityWeighting", true) ? "priority" : "equal")
154                + " weighting model" + " with over-expected " + iModel.getOverExpectedCriterion()
155                + (iSuggestions ? ", suggestions" : "") + ", " + System.getProperty("sort", "shuffle") + " order"
156                + " and " + config.getPropertyInt("Neighbour.BranchAndBoundTimeout", 1000) + " ms time limit.");
157    }
158
159    public OnlineSectioningModel model() {
160        return iModel;
161    }
162
163    public Assignment<Request, Enrollment> assignment() {
164        return iAssignment;
165    }
166
167    public void inc(String name, double value) {
168        synchronized (iCounters) {
169            Counter c = iCounters.get(name);
170            if (c == null) {
171                c = new Counter();
172                iCounters.put(name, c);
173            }
174            c.inc(value);
175        }
176    }
177
178    public void inc(String name) {
179        inc(name, 1.0);
180    }
181
182    public Counter get(String name) {
183        synchronized (iCounters) {
184            Counter c = iCounters.get(name);
185            if (c == null) {
186                c = new Counter();
187                iCounters.put(name, c);
188            }
189            return c;
190        }
191    }
192
193    public double getPercDisbalancedSections(Assignment<Request, Enrollment> assignment, double perc) {
194        boolean balanceUnlimited = model().getProperties().getPropertyBoolean("General.BalanceUnlimited", false);
195        double disb10Sections = 0, nrSections = 0;
196        for (Offering offering : model().getOfferings()) {
197            for (Config config : offering.getConfigs()) {
198                double enrl = config.getEnrollmentTotalWeight(assignment, null);
199                for (Subpart subpart : config.getSubparts()) {
200                    if (subpart.getSections().size() <= 1)
201                        continue;
202                    nrSections += subpart.getSections().size();
203                    if (subpart.getLimit() > 0) {
204                        // sections have limits -> desired size is section limit
205                        // x (total enrollment / total limit)
206                        double ratio = enrl / subpart.getLimit();
207                        for (Section section : subpart.getSections()) {
208                            double desired = ratio * section.getLimit();
209                            if (Math.abs(desired - section.getEnrollmentTotalWeight(assignment, null)) >= Math.max(1.0, perc * section.getLimit()))
210                                disb10Sections++;
211                        }
212                    } else if (balanceUnlimited) {
213                        // unlimited sections -> desired size is total
214                        // enrollment / number of sections
215                        for (Section section : subpart.getSections()) {
216                            double desired = enrl / subpart.getSections().size();
217                            if (Math.abs(desired - section.getEnrollmentTotalWeight(assignment, null)) >= Math.max(1.0, perc * desired))
218                                disb10Sections++;
219                        }
220                    }
221                }
222            }
223        }
224        return 100.0 * disb10Sections / nrSections;
225    }
226
227    protected Course clone(Course course, long studentId, Student originalStudent, Map<Long, Section> classTable, StudentSectioningModel model) {
228        Offering clonedOffering = new Offering(course.getOffering().getId(), course.getOffering().getName());
229        clonedOffering.setModel(model);
230        int courseLimit = course.getLimit();
231        if (courseLimit >= 0) {
232            courseLimit -= course.getEnrollments(assignment()).size();
233            if (courseLimit < 0)
234                courseLimit = 0;
235            for (Iterator<Enrollment> i = course.getEnrollments(assignment()).iterator(); i.hasNext();) {
236                Enrollment enrollment = i.next();
237                if (enrollment.getStudent().getId() == studentId) {
238                    courseLimit++;
239                    break;
240                }
241            }
242        }
243        Course clonedCourse = new Course(course.getId(), course.getSubjectArea(), course.getCourseNumber(),
244                clonedOffering, courseLimit, course.getProjected());
245        clonedCourse.setNote(course.getNote());
246        clonedCourse.setType(course.getType());
247        clonedCourse.setTitle(course.getTitle());
248        Hashtable<Config, Config> configs = new Hashtable<Config, Config>();
249        Hashtable<Subpart, Subpart> subparts = new Hashtable<Subpart, Subpart>();
250        Hashtable<Section, Section> sections = new Hashtable<Section, Section>();
251        for (Iterator<Config> e = course.getOffering().getConfigs().iterator(); e.hasNext();) {
252            Config config = e.next();
253            int configLimit = config.getLimit();
254            int configEnrollment = config.getEnrollments(assignment()).size();
255            if (configLimit >= 0) {
256                configLimit -= config.getEnrollments(assignment()).size();
257                if (configLimit < 0)
258                    configLimit = 0;
259                for (Iterator<Enrollment> i = config.getEnrollments(assignment()).iterator(); i.hasNext();) {
260                    Enrollment enrollment = i.next();
261                    if (enrollment.getStudent().getId() == studentId) {
262                        configLimit++;
263                        configEnrollment--;
264                        break;
265                    }
266                }
267            }
268            OnlineConfig clonedConfig = new OnlineConfig(config.getId(), configLimit, config.getName(), clonedOffering);
269            clonedConfig.setInstructionalMethodId(config.getInstructionalMethodId());
270            clonedConfig.setInstructionalMethodName(config.getInstructionalMethodName());
271            clonedConfig.setInstructionalMethodReference(config.getInstructionalMethodReference());
272            clonedConfig.setEnrollment(configEnrollment);
273            configs.put(config, clonedConfig);
274            for (Iterator<Subpart> f = config.getSubparts().iterator(); f.hasNext();) {
275                Subpart subpart = f.next();
276                Subpart clonedSubpart = new Subpart(subpart.getId(), subpart.getInstructionalType(), subpart.getName(),
277                        clonedConfig, (subpart.getParent() == null ? null : subparts.get(subpart.getParent())));
278                clonedSubpart.setAllowOverlap(subpart.isAllowOverlap());
279                clonedSubpart.setCredit(subpart.getCredit());
280                subparts.put(subpart, clonedSubpart);
281                for (Iterator<Section> g = subpart.getSections().iterator(); g.hasNext();) {
282                    Section section = g.next();
283                    int limit = section.getLimit();
284                    int enrl = section.getEnrollments(assignment()).size();
285                    if (limit >= 0) {
286                        // limited section, deduct enrollments
287                        limit -= section.getEnrollments(assignment()).size();
288                        if (limit < 0)
289                            limit = 0; // over-enrolled, but not unlimited
290                        if (studentId >= 0)
291                            for (Enrollment enrollment : section.getEnrollments(assignment()))
292                                if (enrollment.getStudent().getId() == studentId) {
293                                    limit++;
294                                    enrl--;
295                                    break;
296                                }
297                    }
298                    OnlineSection clonedSection = new OnlineSection(section.getId(), limit,
299                            section.getName(course .getId()), clonedSubpart, section.getPlacement(), section.getInstructors(), (section.getParent() == null ? null : sections.get(section.getParent())));
300                    clonedSection.setName(-1l, section.getName(-1l));
301                    clonedSection.setNote(section.getNote());
302                    clonedSection.setSpaceExpected(section.getSpaceExpected());
303                    clonedSection.setSpaceHeld(section.getSpaceHeld());
304                    clonedSection.setEnrollment(enrl);
305                    clonedSection.setCancelled(section.isCancelled());
306                    clonedSection.setEnabled(section.isEnabled());
307                    clonedSection.setPast(section.isPast());
308                    clonedSection.setOnline(section.isOnline());
309                    if (section.getIgnoreConflictWithSectionIds() != null)
310                        for (Long id : section.getIgnoreConflictWithSectionIds())
311                            clonedSection.addIgnoreConflictWith(id);
312                    if (limit > 0) {
313                        double available = Math.round(section.getSpaceExpected() - limit);
314                        clonedSection.setPenalty(available / section.getLimit());
315                    }
316                    sections.put(section, clonedSection);
317                    classTable.put(section.getId(), clonedSection);
318                }
319            }
320        }
321        if (course.getOffering().hasReservations()) {
322            for (Reservation reservation : course.getOffering().getReservations()) {
323                int reservationLimit = (int) Math.round(reservation.getLimit());
324                if (reservationLimit >= 0) {
325                    reservationLimit -= reservation.getEnrollments(assignment()).size();
326                    if (reservationLimit < 0)
327                        reservationLimit = 0;
328                    for (Iterator<Enrollment> i = reservation.getEnrollments(assignment()).iterator(); i.hasNext();) {
329                        Enrollment enrollment = i.next();
330                        if (enrollment.getStudent().getId() == studentId) {
331                            reservationLimit++;
332                            break;
333                        }
334                    }
335                    if (reservationLimit <= 0 && !reservation.mustBeUsed())
336                        continue;
337                }
338                boolean applicable = originalStudent != null && reservation.isApplicable(originalStudent);
339                if (reservation instanceof CourseReservation)
340                    applicable = (course.getId() == ((CourseReservation) reservation).getCourse().getId());
341                if (reservation instanceof org.cpsolver.studentsct.reservation.DummyReservation) {
342                    // Ignore by reservation only flag (dummy reservation) when
343                    // the student is already enrolled in the course
344                    for (Enrollment enrollment : course.getEnrollments(assignment()))
345                        if (enrollment.getStudent().getId() == studentId) {
346                            applicable = true;
347                            break;
348                        }
349                }
350                Reservation clonedReservation = new OnlineReservation(0, reservation.getId(), clonedOffering,
351                        reservation.getPriority(), reservation.canAssignOverLimit(), reservationLimit, applicable,
352                        reservation.mustBeUsed(), reservation.isAllowOverlap(), reservation.isExpired());
353                for (Config config : reservation.getConfigs())
354                    clonedReservation.addConfig(configs.get(config));
355                for (Map.Entry<Subpart, Set<Section>> entry : reservation.getSections().entrySet()) {
356                    Set<Section> clonedSections = new HashSet<Section>();
357                    for (Section section : entry.getValue())
358                        clonedSections.add(sections.get(section));
359                    clonedReservation.getSections().put(subparts.get(entry.getKey()), clonedSections);
360                }
361            }
362        }
363        return clonedCourse;
364    }
365
366    protected Request addRequest(Student student, Student original, Request request, Map<Long, Section> classTable,
367            StudentSectioningModel model) {
368        if (request instanceof FreeTimeRequest) {
369            return new FreeTimeRequest(student.getRequests().size() + 1, student.getRequests().size(),
370                    request.isAlternative(), student, ((FreeTimeRequest) request).getTime());
371        } else if (request instanceof CourseRequest) {
372            List<Course> courses = new ArrayList<Course>();
373            for (Course course : ((CourseRequest) request).getCourses())
374                courses.add(clone(course, student.getId(), original, classTable, model));
375            CourseRequest clonnedRequest = new CourseRequest(student.getRequests().size() + 1, student.getRequests().size(),
376                    request.isAlternative(), student, courses, ((CourseRequest) request).isWaitlist(), request.getRequestPriority(), null);
377            for (Request originalRequest : original.getRequests()) {
378                Enrollment originalEnrollment = assignment().getValue(originalRequest);
379                for (Course clonnedCourse : clonnedRequest.getCourses()) {
380                    if (!clonnedCourse.getOffering().hasReservations())
381                        continue;
382                    if (originalEnrollment != null && clonnedCourse.equals(originalEnrollment.getCourse())) {
383                        boolean needReservation = clonnedCourse.getOffering().getUnreservedSpace(assignment(), clonnedRequest) < 1.0;
384                        if (!needReservation) {
385                            boolean configChecked = false;
386                            for (Section originalSection : originalEnrollment.getSections()) {
387                                Section clonnedSection = classTable.get(originalSection.getId());
388                                if (clonnedSection.getUnreservedSpace(assignment(), clonnedRequest) < 1.0) {
389                                    needReservation = true;
390                                    break;
391                                }
392                                if (!configChecked
393                                        && clonnedSection.getSubpart().getConfig()
394                                                .getUnreservedSpace(assignment(), clonnedRequest) < 1.0) {
395                                    needReservation = true;
396                                    break;
397                                }
398                                configChecked = true;
399                            }
400                        }
401                        if (needReservation) {
402                            Reservation reservation = new OnlineReservation(0, -original.getId(),
403                                    clonnedCourse.getOffering(), 5, false, 1, true, false, false, true);
404                            for (Section originalSection : originalEnrollment.getSections())
405                                reservation.addSection(classTable.get(originalSection.getId()));
406                        }
407                        break;
408                    }
409                }
410            }
411            return clonnedRequest;
412        } else {
413            return null;
414        }
415    }
416
417    public boolean section(Student original) {
418        OnlineSectioningModel model = new TestModel(iModel.getProperties());
419        model.setOverExpectedCriterion(iModel.getOverExpectedCriterion());
420        Student student = new Student(original.getId());
421        Hashtable<CourseRequest, Set<Section>> preferredSectionsForCourse = new Hashtable<CourseRequest, Set<Section>>();
422        Map<Long, Section> classTable = new HashMap<Long, Section>();
423
424        synchronized (iModel) {
425            for (Request request : original.getRequests()) {
426                Request clonnedRequest = addRequest(student, original, request, classTable, model);
427                Enrollment enrollment = assignment().getValue(request);
428                if (enrollment != null && enrollment.isCourseRequest()) {
429                    Set<Section> sections = new HashSet<Section>();
430                    for (Section section : enrollment.getSections())
431                        sections.add(classTable.get(section.getId()));
432                    preferredSectionsForCourse.put((CourseRequest) clonnedRequest, sections);
433                }
434            }
435        }
436
437        model.addStudent(student);
438        model.setDistanceConflict(new DistanceConflict(iModel.getDistanceConflict().getDistanceMetric(), model.getProperties()));
439        model.setTimeOverlaps(new TimeOverlapsCounter(null, model.getProperties()));
440        for (LinkedSections link : iModel.getLinkedSections()) {
441            List<Section> sections = new ArrayList<Section>();
442            for (Offering offering : link.getOfferings())
443                for (Subpart subpart : link.getSubparts(offering))
444                    for (Section section : link.getSections(subpart)) {
445                        Section x = classTable.get(section.getId());
446                        if (x != null)
447                            sections.add(x);
448                    }
449            if (sections.size() >= 2)
450                model.addLinkedSections(link.isMustBeUsed(), sections);
451        }
452        OnlineSectioningSelection selection = null;
453        if (model.getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true)) {
454            selection = new MultiCriteriaBranchAndBoundSelection(iModel.getProperties());
455        } else {
456            selection = new SuggestionSelection(model.getProperties());
457        }
458
459        selection.setModel(model);
460        selection.setPreferredSections(preferredSectionsForCourse);
461        selection.setRequiredSections(new Hashtable<CourseRequest, Set<Section>>());
462        selection.setRequiredFreeTimes(new HashSet<FreeTimeRequest>());
463
464        long t0 = JProf.currentTimeMillis();
465        Assignment<Request, Enrollment> newAssignment = new AssignmentMap<Request, Enrollment>();
466        BranchBoundNeighbour neighbour = selection.select(newAssignment, student);
467        long time = JProf.currentTimeMillis() - t0;
468        inc("[C] CPU Time", time);
469        if (neighbour == null) {
470            inc("[F] Failure");
471        } else {
472            if (iSuggestions) {
473                StudentPreferencePenalties penalties = new StudentPreferencePenalties(StudentPreferencePenalties.sDistTypePreference);
474                double maxOverExpected = 0;
475                int assigned = 0;
476                double penalty = 0.0;
477                Hashtable<CourseRequest, Set<Section>> enrollments = new Hashtable<CourseRequest, Set<Section>>();
478                List<RequestSectionPair> pairs = new ArrayList<RequestSectionPair>();
479
480                for (int i = 0; i < neighbour.getAssignment().length; i++) {
481                    Enrollment enrl = neighbour.getAssignment()[i];
482                    if (enrl != null && enrl.isCourseRequest() && enrl.getAssignments() != null) {
483                        assigned++;
484                        for (Section section : enrl.getSections()) {
485                            maxOverExpected += model.getOverExpected(newAssignment, section, enrl.getRequest());
486                            pairs.add(new RequestSectionPair(enrl.variable(), section));
487                        }
488                        enrollments.put((CourseRequest) enrl.variable(), enrl.getSections());
489                        penalty += penalties.getPenalty(enrl);
490                    }
491                }
492                penalty /= assigned;
493                inc("[S] Initial Penalty", penalty);
494                double nrSuggestions = 0.0, nrAccepted = 0.0, totalSuggestions = 0.0, nrTries = 0.0;
495                for (int i = 0; i < pairs.size(); i++) {
496                    RequestSectionPair pair = pairs.get(i);
497                    SuggestionsBranchAndBound suggestionBaB = null;
498                    if (model.getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true)) {
499                        suggestionBaB = new MultiCriteriaBranchAndBoundSuggestions(model.getProperties(), student,
500                                newAssignment, new Hashtable<CourseRequest, Set<Section>>(),
501                                new HashSet<FreeTimeRequest>(), enrollments, pair.getRequest(), pair.getSection(),
502                                null, maxOverExpected, iModel.getProperties().getPropertyBoolean(
503                                        "StudentWeights.PriorityWeighting", true));
504                    } else {
505                        suggestionBaB = new SuggestionsBranchAndBound(model.getProperties(), student, newAssignment,
506                                new Hashtable<CourseRequest, Set<Section>>(), new HashSet<FreeTimeRequest>(),
507                                enrollments, pair.getRequest(), pair.getSection(), null, maxOverExpected);
508                    }
509
510                    long x0 = JProf.currentTimeMillis();
511                    TreeSet<SuggestionsBranchAndBound.Suggestion> suggestions = suggestionBaB.computeSuggestions();
512                    inc("[S] Suggestion CPU Time", JProf.currentTimeMillis() - x0);
513                    totalSuggestions += suggestions.size();
514                    if (!suggestions.isEmpty())
515                        nrSuggestions += 1.0;
516                    nrTries += 1.0;
517
518                    SuggestionsBranchAndBound.Suggestion best = null;
519                    for (SuggestionsBranchAndBound.Suggestion suggestion : suggestions) {
520                        int a = 0;
521                        double p = 0.0;
522                        for (int j = 0; j < suggestion.getEnrollments().length; j++) {
523                            Enrollment e = suggestion.getEnrollments()[j];
524                            if (e != null && e.isCourseRequest() && e.getAssignments() != null) {
525                                p += penalties.getPenalty(e);
526                                a++;
527                            }
528                        }
529                        p /= a;
530                        if (a > assigned || (assigned == a && p < penalty)) {
531                            best = suggestion;
532                        }
533                    }
534                    if (best != null) {
535                        nrAccepted += 1.0;
536                        Enrollment[] e = best.getEnrollments();
537                        for (int j = 0; j < e.length; j++)
538                            if (e[j] != null && e[j].getAssignments() == null)
539                                e[j] = null;
540                        neighbour = new BranchBoundNeighbour(student, best.getValue(), e);
541                        assigned = 0;
542                        penalty = 0.0;
543                        enrollments.clear();
544                        pairs.clear();
545                        for (int j = 0; j < neighbour.getAssignment().length; j++) {
546                            Enrollment enrl = neighbour.getAssignment()[j];
547                            if (enrl != null && enrl.isCourseRequest() && enrl.getAssignments() != null) {
548                                assigned++;
549                                for (Section section : enrl.getSections())
550                                    pairs.add(new RequestSectionPair(enrl.variable(), section));
551                                enrollments.put((CourseRequest) enrl.variable(), enrl.getSections());
552                                penalty += penalties.getPenalty(enrl);
553                            }
554                        }
555                        penalty /= assigned;
556                        inc("[S] Improved Penalty", penalty);
557                    }
558                }
559                inc("[S] Final Penalty", penalty);
560                if (nrSuggestions > 0) {
561                    inc("[S] Classes with suggestion", nrSuggestions);
562                    inc("[S] Avg. # of suggestions", totalSuggestions / nrSuggestions);
563                    inc("[S] Suggestion acceptance rate [%]", nrAccepted / nrSuggestions);
564                } else {
565                    inc("[S] Student with no suggestions available", 1.0);
566                }
567                if (!pairs.isEmpty())
568                    inc("[S] Probability that a class has suggestions [%]", nrSuggestions / nrTries);
569            }
570
571            List<Enrollment> enrollments = new ArrayList<Enrollment>();
572            i: for (int i = 0; i < neighbour.getAssignment().length; i++) {
573                Request request = original.getRequests().get(i);
574                Enrollment clonnedEnrollment = neighbour.getAssignment()[i];
575                if (clonnedEnrollment != null && clonnedEnrollment.getAssignments() != null) {
576                    if (request instanceof FreeTimeRequest) {
577                        enrollments.add(((FreeTimeRequest) request).createEnrollment());
578                    } else {
579                        for (Course course : ((CourseRequest) request).getCourses())
580                            if (course.getId() == clonnedEnrollment.getCourse().getId())
581                                for (Config config : course.getOffering().getConfigs())
582                                    if (config.getId() == clonnedEnrollment.getConfig().getId()) {
583                                        Set<Section> assignments = new HashSet<Section>();
584                                        for (Subpart subpart : config.getSubparts())
585                                            for (Section section : subpart.getSections()) {
586                                                if (clonnedEnrollment.getSections().contains(section)) {
587                                                    assignments.add(section);
588                                                }
589                                            }
590                                        Reservation reservation = null;
591                                        if (clonnedEnrollment.getReservation() != null) {
592                                            for (Reservation r : course.getOffering().getReservations())
593                                                if (r.getId() == clonnedEnrollment.getReservation().getId()) {
594                                                    reservation = r;
595                                                    break;
596                                                }
597                                        }
598                                        enrollments.add(new Enrollment(request, clonnedEnrollment.getPriority(),
599                                                course, config, assignments, reservation));
600                                        continue i;
601                                    }
602                    }
603                }
604            }
605            synchronized (iModel) {
606                for (Request r : original.getRequests()) {
607                    Enrollment e = assignment().getValue(r);
608                    r.setInitialAssignment(e);
609                    if (e != null)
610                        updateSpace(assignment(), e, true);
611                }
612                for (Request r : original.getRequests())
613                    if (assignment().getValue(r) != null)
614                        assignment().unassign(0, r);
615                boolean fail = false;
616                for (Enrollment enrl : enrollments) {
617                    if (iModel.conflictValues(assignment(), enrl).isEmpty()) {
618                        assignment().assign(0, enrl);
619                    } else {
620                        fail = true;
621                        break;
622                    }
623                }
624                if (fail) {
625                    for (Request r : original.getRequests())
626                        if (assignment().getValue(r) != null)
627                            assignment().unassign(0, r);
628                    for (Request r : original.getRequests())
629                        if (r.getInitialAssignment() != null)
630                            assignment().assign(0, r.getInitialAssignment());
631                    for (Request r : original.getRequests())
632                        if (assignment().getValue(r) != null)
633                            updateSpace(assignment(), assignment().getValue(r), false);
634                } else {
635                    for (Enrollment enrl : enrollments)
636                        updateSpace(assignment(), enrl, false);
637                }
638                if (fail)
639                    return false;
640            }
641            neighbour.assign(newAssignment, 0);
642            int a = 0, u = 0, np = 0, zp = 0, pp = 0, cp = 0;
643            double over = 0;
644            double p = 0.0;
645            for (Request r : student.getRequests()) {
646                if (r instanceof CourseRequest) {
647                    Enrollment e = newAssignment.getValue(r);
648                    if (e != null) {
649                        for (Section s : e.getSections()) {
650                            if (s.getPenalty() < 0.0)
651                                np++;
652                            if (s.getPenalty() == 0.0)
653                                zp++;
654                            if (s.getPenalty() > 0.0)
655                                pp++;
656                            if (s.getLimit() > 0) {
657                                p += s.getPenalty();
658                                cp++;
659                            }
660                            over += model.getOverExpected(newAssignment, s, r);
661                        }
662                        a++;
663                    } else {
664                        u++;
665                    }
666                }
667            }
668            inc("[A] Student");
669            if (over > 0.0)
670                inc("[O] Over", over);
671            if (a > 0)
672                inc("[A] Assigned", a);
673            if (u > 0)
674                inc("[A] Not Assigned", u);
675            inc("[V] Value", neighbour.value(newAssignment));
676            if (zp > 0)
677                inc("[P] Zero penalty", zp);
678            if (np > 0)
679                inc("[P] Negative penalty", np);
680            if (pp > 0)
681                inc("[P] Positive penalty", pp);
682            if (cp > 0)
683                inc("[P] Average penalty", p / cp);
684        }
685        inc("[T0] Time <10ms", time < 10 ? 1 : 0);
686        inc("[T1] Time <100ms", time < 100 ? 1 : 0);
687        inc("[T2] Time <250ms", time < 250 ? 1 : 0);
688        inc("[T3] Time <500ms", time < 500 ? 1 : 0);
689        inc("[T4] Time <1s", time < 1000 ? 1 : 0);
690        inc("[T5] Time >=1s", time >= 1000 ? 1 : 0);
691        return true;
692    }
693
694    public static void updateSpace(Assignment<Request, Enrollment> assignment, Enrollment enrollment, boolean increment) {
695        if (enrollment == null || !enrollment.isCourseRequest())
696            return;
697        for (Section section : enrollment.getSections())
698            section.setSpaceHeld(section.getSpaceHeld() + (increment ? 1.0 : -1.0));
699        List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>();
700        int totalLimit = 0;
701        for (Enrollment enrl : enrollment.getRequest().values(assignment)) {
702            if (!enrl.getCourse().equals(enrollment.getCourse()))
703                continue;
704            boolean overlaps = false;
705            for (Request otherRequest : enrollment.getRequest().getStudent().getRequests()) {
706                if (otherRequest.equals(enrollment.getRequest()) || !(otherRequest instanceof CourseRequest))
707                    continue;
708                Enrollment otherErollment = assignment.getValue(otherRequest);
709                if (otherErollment == null)
710                    continue;
711                if (enrl.isOverlapping(otherErollment)) {
712                    overlaps = true;
713                    break;
714                }
715            }
716            if (!overlaps) {
717                feasibleEnrollments.add(enrl);
718                if (totalLimit >= 0) {
719                    int limit = enrl.getLimit();
720                    if (limit < 0)
721                        totalLimit = -1;
722                    else
723                        totalLimit += limit;
724                }
725            }
726        }
727        double change = enrollment.getRequest().getWeight()
728                / (totalLimit > 0 ? totalLimit : feasibleEnrollments.size());
729        for (Enrollment feasibleEnrollment : feasibleEnrollments)
730            for (Section section : feasibleEnrollment.getSections()) {
731                if (totalLimit > 0) {
732                    section.setSpaceExpected(section.getSpaceExpected() + (increment ? +change : -change)
733                            * feasibleEnrollment.getLimit());
734                } else {
735                    section.setSpaceExpected(section.getSpaceExpected() + (increment ? +change : -change));
736                }
737            }
738    }
739
740    public void run() {
741        sLog.info("Input: " + ToolBox.dict2string(model().getExtendedInfo(assignment()), 2));
742
743        List<Student> students = new ArrayList<Student>(model().getStudents());
744        String sort = System.getProperty("sort", "shuffle");
745        if ("shuffle".equals(sort)) {
746            Collections.shuffle(students);
747        } else if ("choice".equals(sort)) {
748            StudentChoiceOrder ord = new StudentChoiceOrder(model().getProperties());
749            ord.setReverse(false);
750            Collections.sort(students, ord);
751        } else if ("referse".equals(sort)) {
752            StudentChoiceOrder ord = new StudentChoiceOrder(model().getProperties());
753            ord.setReverse(true);
754            Collections.sort(students, ord);
755        }
756
757        Iterator<Student> iterator = students.iterator();
758        int nrThreads = Integer.parseInt(System.getProperty("nrConcurrent", "10"));
759        List<Executor> executors = new ArrayList<Executor>();
760        for (int i = 0; i < nrThreads; i++) {
761            Executor executor = new Executor(iterator);
762            executor.start();
763            executors.add(executor);
764        }
765
766        long t0 = System.currentTimeMillis();
767        while (iterator.hasNext()) {
768            try {
769                Thread.sleep(60000);
770            } catch (InterruptedException e) {
771            }
772            long time = System.currentTimeMillis() - t0;
773            synchronized (iModel) {
774                sLog.info("Progress [" + (time / 60000) + "m]: " + ToolBox.dict2string(model().getExtendedInfo(assignment()), 2));
775            }
776        }
777
778        for (Executor executor : executors) {
779            try {
780                executor.join();
781            } catch (InterruptedException e) {
782            }
783        }
784
785        sLog.info("Output: " + ToolBox.dict2string(model().getExtendedInfo(assignment()), 2));
786        long time = System.currentTimeMillis() - t0;
787        inc("[T] Run Time [m]", time / 60000.0);
788
789    }
790
791    public class Executor extends Thread {
792        private Iterator<Student> iStudents = null;
793
794        public Executor(Iterator<Student> students) {
795            iStudents = students;
796        }
797
798        @Override
799        public void run() {
800            try {
801                for (;;) {
802                    Student student = iStudents.next();
803                    int attempt = 1;
804                    while (!section(student)) {
805                        sLog.warn(attempt + ". attempt failed for " + student.getId());
806                        inc("[F] Failed attempt", attempt);
807                        attempt++;
808                        if (attempt == 101)
809                            break;
810                        if (attempt > 10) {
811                            try {
812                                Thread.sleep(ToolBox.random(100 * attempt));
813                            } catch (InterruptedException e) {
814                            }
815                        }
816                    }
817                    if (attempt > 100)
818                        inc("[F] Failed enrollment (all 100 attempts)");
819                }
820            } catch (NoSuchElementException e) {
821            }
822        }
823
824    }
825
826    public class TestModel extends OnlineSectioningModel {
827        public TestModel(DataProperties config) {
828            super(config);
829        }
830
831        @Override
832        public Map<String, String> getExtendedInfo(Assignment<Request, Enrollment> assignment) {
833            Map<String, String> ret = super.getExtendedInfo(assignment);
834            for (Map.Entry<String, Counter> e : iCounters.entrySet())
835                ret.put(e.getKey(), e.getValue().toString());
836            ret.put("Weighting model",
837                    (model().getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true) ? "multi-criteria " : "") +
838                    (model().getProperties().getPropertyBoolean("StudentWeights.PriorityWeighting", true) ? "priority" : "equal"));
839            ret.put("B&B time limit", model().getProperties().getPropertyInt("Neighbour.BranchAndBoundTimeout", 1000) + " ms");
840            if (iSuggestions) {
841                ret.put("Suggestion time limit", model().getProperties().getPropertyInt("Suggestions.Timeout", 1000) + " ms");
842            }
843            return ret;
844        }
845    }
846
847    private static class RequestSectionPair {
848        private Request iRequest;
849        private Section iSection;
850
851        RequestSectionPair(Request request, Section section) {
852            iRequest = request;
853            iSection = section;
854        }
855
856        Request getRequest() {
857            return iRequest;
858        }
859
860        Section getSection() {
861            return iSection;
862        }
863    }
864
865    private void stats(File input) throws IOException {
866        File file = new File(input.getParentFile(), "stats.csv");
867        DecimalFormat df = new DecimalFormat("0.0000");
868        boolean ex = file.exists();
869        PrintWriter pw = new PrintWriter(new FileWriter(file, true));
870        if (!ex) {
871            pw.println("Input File,Run Time [m],Model,Sort,Over Expected,Not Assigned,Disb. Sections [%],Distance Confs.,Time Confs. [m],"
872                    + "CPU Assignment [ms],Has Suggestions [%],Nbr Suggestions,Acceptance [%],CPU Suggestions [ms]");
873        }
874        pw.print(input.getName() + ",");
875        pw.print(df.format(get("[T] Run Time [m]").sum()) + ",");
876        pw.print(model().getProperties().getPropertyBoolean("StudentWeights.MultiCriteria", true) ? "multi-criteria " : "");
877        pw.print(model().getProperties().getPropertyBoolean("StudentWeights.PriorityWeighting", true) ? "priority" : "equal");
878        pw.print(iSuggestions ? " with suggestions" : "");
879        pw.print(",");
880        pw.print(System.getProperty("sort", "shuffle") + ",");
881        pw.print("\"" + model().getOverExpectedCriterion() + "\",");
882
883        pw.print(get("[A] Not Assigned").sum() + ",");
884        pw.print(df.format(getPercDisbalancedSections(assignment(), 0.1)) + ",");
885        if (model().getStudentQuality() != null) {
886            pw.print(df.format(((double) model().getStudentQuality().getTotalPenalty(assignment(), StudentQuality.Type.Distance, StudentQuality.Type.ShortDistance)) / model().getStudents().size()) + ",");
887            pw.print(df.format(5.0 * model().getStudentQuality().getTotalPenalty(assignment(), StudentQuality.Type.CourseTimeOverlap, StudentQuality.Type.FreeTimeOverlap, StudentQuality.Type.Unavailability) / model().getStudents().size()) + ",");
888        } else {
889            pw.print(df.format(((double) model().getDistanceConflict().getTotalNrConflicts(assignment())) / model().getStudents().size()) + ",");
890            pw.print(df.format(5.0 * model().getTimeOverlaps().getTotalNrConflicts(assignment()) / model().getStudents().size()) + ",");
891        }
892        pw.print(df.format(get("[C] CPU Time").avg()) + ",");
893        if (iSuggestions) {
894            pw.print(df.format(get("[S] Probability that a class has suggestions [%]").avg()) + ",");
895            pw.print(df.format(get("[S] Avg. # of suggestions").avg()) + ",");
896            pw.print(df.format(get("[S] Suggestion acceptance rate [%]").avg()) + ",");
897            pw.print(df.format(get("[S] Suggestion CPU Time").avg()));
898        }
899        pw.println();
900
901        pw.flush();
902        pw.close();
903    }
904
905    public static void main(String[] args) {
906        try {
907            System.setProperty("jprof", "cpu");
908            ToolBox.configureLogging();
909
910            DataProperties cfg = new DataProperties();
911            cfg.setProperty("Neighbour.BranchAndBoundTimeout", "5000");
912            cfg.setProperty("Suggestions.Timeout", "1000");
913            cfg.setProperty("Extensions.Classes", DistanceConflict.class.getName() + ";" + TimeOverlapsCounter.class.getName());
914            cfg.setProperty("StudentWeights.Class", StudentSchedulingAssistantWeights.class.getName());
915            cfg.setProperty("StudentWeights.PriorityWeighting", "true");
916            cfg.setProperty("StudentWeights.LeftoverSpread", "true");
917            cfg.setProperty("StudentWeights.BalancingFactor", "0.0");
918            cfg.setProperty("Reservation.CanAssignOverTheLimit", "true");
919            cfg.setProperty("Distances.Ellipsoid", DistanceMetric.Ellipsoid.WGS84.name());
920            cfg.setProperty("StudentWeights.MultiCriteria", "true");
921            cfg.setProperty("CourseRequest.SameTimePrecise", "true");
922
923            cfg.setProperty("Xml.LoadBest", "false");
924            cfg.setProperty("Xml.LoadCurrent", "false");
925
926            cfg.putAll(System.getProperties());
927
928            final Test test = new Test(cfg);
929
930            final File input = new File(args[0]);
931            StudentSectioningXMLLoader loader = new StudentSectioningXMLLoader(test.model(), test.assignment());
932            loader.setInputFile(input);
933            loader.load();
934
935            test.run();
936
937            Solver<Request, Enrollment> s = new Solver<Request, Enrollment>(cfg);
938            s.setInitalSolution(test.model());
939            StudentSectioningXMLSaver saver = new StudentSectioningXMLSaver(s);
940            File output = new File(input.getParentFile(), input.getName().substring(0, input.getName().lastIndexOf('.')) +
941                    "-" + cfg.getProperty("run", "r0") + ".xml");
942            saver.save(output);
943
944            test.stats(input);
945        } catch (Exception e) {
946            sLog.error("Test failed: " + e.getMessage(), e);
947        }
948    }
949
950    private static class Counter {
951        private double iTotal = 0.0, iMin = 0.0, iMax = 0.0, iTotalSquare = 0.0;
952        private int iCount = 0;
953
954        void inc(double value) {
955            if (iCount == 0) {
956                iTotal = value;
957                iMin = value;
958                iMax = value;
959                iTotalSquare = value * value;
960            } else {
961                iTotal += value;
962                iMin = Math.min(iMin, value);
963                iMax = Math.max(iMax, value);
964                iTotalSquare += value * value;
965            }
966            iCount++;
967        }
968
969        int count() {
970            return iCount;
971        }
972
973        double sum() {
974            return iTotal;
975        }
976
977        double min() {
978            return iMin;
979        }
980
981        double max() {
982            return iMax;
983        }
984
985        double rms() {
986            return (iCount == 0 ? 0.0 : Math.sqrt(iTotalSquare / iCount));
987        }
988
989        double avg() {
990            return (iCount == 0 ? 0.0 : iTotal / iCount);
991        }
992
993        @Override
994        public String toString() {
995            return sDF.format(sum()) + " (min: " + sDF.format(min()) + ", max: " + sDF.format(max()) +
996                    ", avg: " + sDF.format(avg()) + ", rms: " + sDF.format(rms()) + ", cnt: " + count() + ")";
997        }
998    }
999
1000}