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