    001package org.cpsolver.studentsct.heuristics.selection;
    002
    003import java.text.DecimalFormat;
    004import java.util.ArrayList;
    005import java.util.Collection;
    006import java.util.Collections;
    007import java.util.Comparator;
    008import java.util.ConcurrentModificationException;
    009import java.util.HashMap;
    010import java.util.HashSet;
    011import java.util.Iterator;
    012import java.util.LinkedList;
    013import java.util.List;
    014import java.util.Map;
    015import java.util.Set;
    016
    017import org.apache.logging.log4j.Logger;
    018import org.cpsolver.ifs.assignment.Assignment;
    019import org.cpsolver.ifs.heuristics.NeighbourSelection;
    020import org.cpsolver.ifs.model.GlobalConstraint;
    021import org.cpsolver.ifs.model.InfoProvider;
    022import org.cpsolver.ifs.model.Neighbour;
    023import org.cpsolver.ifs.solution.Solution;
    024import org.cpsolver.ifs.solver.Solver;
    025import org.cpsolver.ifs.solver.SolverListener;
    026import org.cpsolver.ifs.util.DataProperties;
    027import org.cpsolver.ifs.util.JProf;
    028import org.cpsolver.ifs.util.Progress;
    029import org.cpsolver.studentsct.StudentSectioningModel;
    030import org.cpsolver.studentsct.constraint.DependentCourses;
    031import org.cpsolver.studentsct.constraint.LinkedSections;
    032import org.cpsolver.studentsct.extension.DistanceConflict;
    033import org.cpsolver.studentsct.extension.StudentQuality;
    034import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
    035import org.cpsolver.studentsct.filter.StudentFilter;
    036import org.cpsolver.studentsct.heuristics.studentord.StudentGroupsChoiceRealFirstOrder;
    037import org.cpsolver.studentsct.heuristics.studentord.StudentOrder;
    038import org.cpsolver.studentsct.model.CourseRequest;
    039import org.cpsolver.studentsct.model.Enrollment;
    040import org.cpsolver.studentsct.model.FreeTimeRequest;
    041import org.cpsolver.studentsct.model.Request;
    042import org.cpsolver.studentsct.model.Section;
    043import org.cpsolver.studentsct.model.Student;
    044import org.cpsolver.studentsct.model.Unavailability;
    045import org.cpsolver.studentsct.online.selection.OnlineSectioningCriterion.TimeToAvoid;
    046import org.cpsolver.studentsct.weights.StudentWeights;
    047
    048/**
    049 * Section all students using incremental branch &amp; bound (no unassignments). All
    050 * students are taken in a random order, for each student a branch &amp; bound
    051 * algorithm is used to find his/her best schedule on top of all other existing
    052 * student schedules (no enrollment of a different student is unassigned).
    053 *
    054 * <br>
    055 * <br>
    056 * Parameters: <br>
    057 * <table border='1'><caption>Related Solver Parameters</caption>
    058 * <tr>
    059 * <th>Parameter</th>
    060 * <th>Type</th>
    061 * <th>Comment</th>
    062 * </tr>
    063 * <tr>
    064 * <td>Neighbour.BranchAndBoundTimeout</td>
    065 * <td>{@link Integer}</td>
    066 * <td>Timeout for each neighbour selection (in milliseconds).</td>
    067 * </tr>
    068 * <tr>
    069 * <td>Neighbour.BranchAndBoundMinimizePenalty</td>
    070 * <td>{@link Boolean}</td>
    071 * <td>If true, section penalties (instead of section values) are minimized:
    072 * overall penalty is minimized together with the maximization of the number of
    073 * assigned requests and minimization of distance conflicts -- this variant is
    074 * to better mimic the case when students can choose their sections (section
    075 * times).</td>
    076 * </tr>
    077 * </table>
    078 * <br>
    079 * <br>
    080 *
    081 * @author  Tomáš Müller
    082 * @version StudentSct 1.3 (Student Sectioning)<br>
    083 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    084 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    085 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    086 * <br>
    087 *          This library is free software; you can redistribute it and/or modify
    088 *          it under the terms of the GNU Lesser General Public License as
    089 *          published by the Free Software Foundation; either version 3 of the
    090 *          License, or (at your option) any later version. <br>
    091 * <br>
    092 *          This library is distributed in the hope that it will be useful, but
    093 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    094 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    095 *          Lesser General Public License for more details. <br>
    096 * <br>
    097 *          You should have received a copy of the GNU Lesser General Public
    098 *          License along with this library; if not see
    099 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    100 */
    101
    102public class BranchBoundSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> {
    103    private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(BranchBoundSelection.class);
    104    private static DecimalFormat sDF = new DecimalFormat("0.00");
    105    protected int iTimeout = 10000;
    106    protected DistanceConflict iDistanceConflict = null;
    107    protected TimeOverlapsCounter iTimeOverlaps = null;
    108    protected StudentQuality iStudentQuality = null;
    109    protected StudentSectioningModel iModel = null;
    110    public static boolean sDebug = false;
    111    protected LinkedList<Student> iStudents = null;
    112    protected boolean iMinimizePenalty = false;
    113    protected StudentOrder iOrder = new StudentGroupsChoiceRealFirstOrder();
    114    protected double iDistConfWeight = 1.0;
    115    protected boolean iBranchWhenSelectedHasNoConflict = false;
    116    protected boolean iTimesToAvoidHeuristics = true;
    117    protected StudentFilter iFilter = null;
    118
    119    protected long iNbrIterations = 0;
    120    protected long iTotalTime = 0;
    121    protected long iNbrTimeoutReached = 0;
    122    protected long iNbrNoSolution = 0;
    123
    124    /**
    125     * Constructor
    126     *
    127     * @param properties
    128     *            configuration
    129     */
    130    public BranchBoundSelection(DataProperties properties) {
    131        iTimeout = properties.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout);
    132        iMinimizePenalty = properties.getPropertyBoolean("Neighbour.BranchAndBoundMinimizePenalty", iMinimizePenalty);
    133        if (iMinimizePenalty)
    134            sLog.info("Overall penalty is going to be minimized (together with the maximization of the number of assigned requests and minimization of distance conflicts).");
    135        if (properties.getProperty("Neighbour.BranchAndBoundOrder") != null) {
    136            try {
    137                iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.BranchAndBoundOrder"))
    138                        .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
    139            } catch (Exception e) {
    140                sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
    141            }
    142        }
    143        iDistConfWeight = properties.getPropertyDouble("DistanceConflict.Weight", iDistConfWeight);
    144        iBranchWhenSelectedHasNoConflict = properties.getPropertyBoolean("Students.BranchWhenSelectedHasNoConflict", iBranchWhenSelectedHasNoConflict);
    145        iTimesToAvoidHeuristics = properties.getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", iTimesToAvoidHeuristics);
    146    }
    147
    148    /**
    149     * Initialize
    150     * @param solver current solver
    151     * @param name phase name
    152     */
    153    public void init(Solver<Request, Enrollment> solver, String name) {
    154        setModel((StudentSectioningModel) solver.currentSolution().getModel());
    155        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, iModel.getStudents().size());
    156        iNbrIterations = 0;
    157        iNbrTimeoutReached = 0;
    158        iNbrNoSolution = 0;
    159        iTotalTime = 0;
    160    }
    161
    162    public void setModel(StudentSectioningModel model) {
    163        iModel = model;
    164        List<Student> students = iOrder.order(iModel.getStudents());
    165        iStudents = new LinkedList<Student>(students);
    166        iTimeOverlaps = model.getTimeOverlaps();
    167        iDistanceConflict = model.getDistanceConflict();
    168        iStudentQuality = model.getStudentQuality();
    169    }
    170
    171    @Override
    172    public void init(Solver<Request, Enrollment> solver) {
    173        init(solver, "Branch&bound" + (iFilter == null ? "" : " (" + iFilter.getName().toLowerCase() + " students)") + "...");
    174    }
    175
    176    protected synchronized Student nextStudent() {
    177        while (true) {
    178            Student student = iStudents.poll();
    179            if (student == null) return null;
    180            if (iFilter == null || iFilter.accept(student))
    181                return student;
    182        }
    183    }
    184
    185    public synchronized void addStudent(Student student) {
    186        if (iStudents != null && !student.isDummy()) iStudents.addFirst(student);
    187    }
    188
    189    /**
    190     * Select neighbour. All students are taken, one by one in a random order.
    191     * For each student a branch &amp; bound search is employed.
    192     */
    193    @Override
    194    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    195        Student student = null;
    196        while ((student = nextStudent()) != null) {
    197            Progress.getInstance(solution.getModel()).incProgress();
    198            for (int i = 0; i < 5; i++) {
    199                try {
    200                    Neighbour<Request, Enrollment> neighbour = getSelection(solution.getAssignment(), student).select();
    201                    if (neighbour != null) return neighbour;
    202                    break;
    203                } catch (ConcurrentModificationException e) {}
    204            }
    205        }
    206        return null;
    207    }
    208
    209    /**
    210     * Branch &amp; bound selection for a student
    211     * @param assignment current assignment
    212     * @param student selected student
    213     * @return selection
    214     */
    215    public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) {
    216        return new Selection(student, assignment);
    217    }
    218
    219    /**
    220     * Branch &amp; bound selection for a student
    221     */
    222    public class Selection {
    223        /** Student */
    224        protected Student iStudent;
    225        /** Start time */
    226        protected long iT0;
    227        /** End time */
    228        protected long iT1;
    229        /** Was timeout reached */
    230        protected boolean iTimeoutReached;
    231        /** Current assignment */
    232        protected Enrollment[] iAssignment;
    233        /** Best assignment */
    234        protected Enrollment[] iBestAssignment;
    235        /** Best value */
    236        protected double iBestValue;
    237        /** Value cache */
    238        protected HashMap<CourseRequest, List<Enrollment>> iValues;
    239        /** Current assignment */
    240        protected Assignment<Request, Enrollment> iCurrentAssignment;
    241        /** Times to avoid (used when comparing enrollments) */
    242        protected ArrayList<TimeToAvoid> iTimesToAvoid = null;
    243
    244        /**
    245         * Constructor
    246         *
    247         * @param student
    248         *            selected student
    249         * @param assignment current assignment
    250         */
    251        public Selection(Student student, Assignment<Request, Enrollment> assignment) {
    252            iStudent = student;
    253            iCurrentAssignment = assignment;
    254            if (iTimesToAvoidHeuristics) {
    255                iTimesToAvoid = new ArrayList<TimeToAvoid>();
    256                for (Request r : iStudent.getRequests()) {
    257                    if (r instanceof CourseRequest) {
    258                        List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment);
    259                        if (enrollments.size() <= 5) {
    260                            int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size());
    261                            for (Enrollment enrollment : enrollments)
    262                                for (Section section : enrollment.getSections())
    263                                    if (section.getTime() != null)
    264                                        iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority()));
    265                        }
    266                    } else if (r instanceof FreeTimeRequest) {
    267                        iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, Integer.MAX_VALUE));
    268                    }
    269                }
    270                for (Unavailability unavailability: iStudent.getUnavailabilities())
    271                    if (unavailability.getTime() != null)
    272                        iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE));
    273            }
    274        }
    275
    276        /**
    277         * Execute branch &amp; bound, return the best found schedule for the
    278         * selected student.
    279         * @return best found schedule for the student
    280         */
    281        public BranchBoundNeighbour select() {
    282            iT0 = JProf.currentTimeMillis();
    283            iTimeoutReached = false;
    284            iAssignment = new Enrollment[iStudent.getRequests().size()];
    285            iBestAssignment = null;
    286            iBestValue = 0;
    287
    288            int i = 0;
    289            for (Request r: iStudent.getRequests())
    290                iAssignment[i++] = iCurrentAssignment.getValue(r);
    291            saveBest();
    292            for (int j = 0; j < iAssignment.length; j++)
    293                iAssignment[j] = null;
    294
    295
    296            iValues = new HashMap<CourseRequest, List<Enrollment>>();
    297            backTrack(0);
    298            iT1 = JProf.currentTimeMillis();
    299
    300            iNbrIterations ++;
    301            iTotalTime += (iT1 - iT0);
    302            if (iTimeoutReached) iNbrTimeoutReached ++;
    303            if (iBestAssignment == null) iNbrNoSolution ++;
    304
    305            if (iBestAssignment == null)
    306                return null;
    307            return new BranchBoundNeighbour(iStudent, iBestValue, iBestAssignment);
    308        }
    309
    310        /** Was timeout reached
    311         * @return true if the timeout was reached
    312         **/
    313        public boolean isTimeoutReached() {
    314            return iTimeoutReached;
    315        }
    316
    317        /** Time (in milliseconds) the branch &amp; bound did run
    318         * @return solver time
    319         **/
    320        public long getTime() {
    321            return iT1 - iT0;
    322        }
    323
    324        /** Best schedule
    325         * @return best schedule
    326         **/
    327        public Enrollment[] getBestAssignment() {
    328            return iBestAssignment;
    329        }
    330
    331        /** Value of the best schedule
    332         * @return value of the best schedule
    333         **/
    334        public double getBestValue() {
    335            return iBestValue;
    336        }
    337
    338        /** Number of requests assigned in the best schedule
    339         * @return number of assigned requests in the best schedule
    340         **/
    341        public int getBestNrAssigned() {
    342            int nrAssigned = 0;
    343            for (int i = 0; i < iBestAssignment.length; i++)
    344                if (iBestAssignment[i] != null)
    345                    nrAssigned += (iBestAssignment[i].isCourseRequest() ? 10 : 1);
    346            return nrAssigned;
    347        }
    348
    349        /** Bound for the number of assigned requests in the current schedule
    350         * @param idx index of the request that is being considered
    351         * @return bound for the given request
    352         **/
    353        public int getNrAssignedBound(int idx) {
    354            int bound = 0;
    355            int i = 0, alt = 0;
    356            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    357                Request r = e.next();
    358                boolean cr = r instanceof CourseRequest;
    359                if (i < idx) {
    360                    if (iAssignment[i] != null)
    361                        bound += (cr ? 10 : 1);
    362                    if (r.isAlternative()) {
    363                        if (iAssignment[i] != null || (cr && ((CourseRequest) r).isWaitlist()))
    364                            alt--;
    365                    } else {
    366                        if (cr && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    367                            alt++;
    368                    }
    369                } else {
    370                    if (!r.isAlternative())
    371                        bound += (cr ? 10 : 1);
    372                    else if (alt > 0) {
    373                        bound += (cr ? 10 : 1);
    374                        alt--;
    375                    }
    376                }
    377            }
    378            return bound;
    379        }
    380
    381        /**
    382         * Distance conflicts of idx-th assignment of the current
    383         * schedule
    384         * @param idx index of the request
    385         * @return set of distance conflicts
    386         */
    387        public Set<DistanceConflict.Conflict> getDistanceConflicts(int idx) {
    388            if (iDistanceConflict == null || iAssignment[idx] == null)
    389                return null;
    390            Set<DistanceConflict.Conflict> dist = iDistanceConflict.conflicts(iAssignment[idx]);
    391            for (int x = 0; x < idx; x++)
    392                if (iAssignment[x] != null)
    393                    dist.addAll(iDistanceConflict.conflicts(iAssignment[x], iAssignment[idx]));
    394            return dist;
    395        }
    396
    397        /**
    398         * Time overlapping conflicts of idx-th assignment of the current
    399         * schedule
    400         * @param idx index of the request
    401         * @return set of time overlapping conflicts
    402         */
    403        public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(int idx) {
    404            if (iTimeOverlaps == null || iAssignment[idx] == null)
    405                return null;
    406            Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
    407            for (int x = 0; x < idx; x++)
    408                if (iAssignment[x] != null)
    409                    overlaps.addAll(iTimeOverlaps.conflicts(iAssignment[x], iAssignment[idx]));
    410                else if (iStudent.getRequests().get(x) instanceof FreeTimeRequest)
    411                    overlaps.addAll(iTimeOverlaps.conflicts(((FreeTimeRequest)iStudent.getRequests().get(x)).createEnrollment(), iAssignment[idx]));
    412            overlaps.addAll(iTimeOverlaps.notAvailableTimeConflicts(iAssignment[idx]));
    413            return overlaps;
    414        }
    415
    416        public Set<StudentQuality.Conflict> getStudentQualityConflicts(int idx) {
    417            if (iStudentQuality == null || iAssignment[idx] == null)
    418                return null;
    419
    420            Set<StudentQuality.Conflict> conflicts = new HashSet<StudentQuality.Conflict>();
    421            for (StudentQuality.Type t: StudentQuality.Type.values()) {
    422                conflicts.addAll(iStudentQuality.conflicts(t, iAssignment[idx]));
    423                for (int x = 0; x < idx; x++)
    424                    if (iAssignment[x] != null)
    425                        conflicts.addAll(iStudentQuality.conflicts(t, iAssignment[x], iAssignment[idx]));
    426            }
    427            return conflicts;
    428        }
    429
    430        /**
    431         * Weight of an assignment. Unlike {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this side of distance conflicts and time overlaps.
    432         * @param enrollment an enrollment
    433         * @param distanceConflicts set of distance conflicts
    434         * @param timeOverlappingConflicts set of time overlapping conflicts
    435         * @return value of the assignment
    436         **/
    437        @Deprecated
    438        protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
    439            double weight = - iModel.getStudentWeights().getWeight(iCurrentAssignment, enrollment);
    440            if (distanceConflicts != null)
    441                for (DistanceConflict.Conflict c: distanceConflicts) {
    442                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
    443                    if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
    444                        weight += iModel.getStudentWeights().getDistanceConflictWeight(iCurrentAssignment, c);
    445                }
    446            if (timeOverlappingConflicts != null)
    447                for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
    448                    weight += iModel.getStudentWeights().getTimeOverlapConflictWeight(iCurrentAssignment, enrollment, c);
    449                }
    450            return enrollment.getRequest().getWeight() * weight;
    451        }
    452
    453        protected double getWeight(Enrollment enrollment, Set<StudentQuality.Conflict> conflicts) {
    454            double weight = - iModel.getStudentWeights().getWeight(iCurrentAssignment, enrollment);
    455            if (conflicts != null)
    456                for (StudentQuality.Conflict c: conflicts)
    457                    weight += iModel.getStudentWeights().getStudentQualityConflictWeight(iCurrentAssignment, enrollment, c);
    458            return enrollment.getRequest().getWeight() * weight;
    459        }
    460
    461        /** Return bound of a request
    462         * @param r a request
    463         * @return bound
    464         **/
    465        protected double getBound(Request r) {
    466            return r.getBound();
    467        }
    468
    469        /** Bound for the current schedule
    470         * @param idx index of the request
    471         * @return current bound
    472         **/
    473        public double getBound(int idx) {
    474            double bound = 0.0;
    475            int i = 0, alt = 0;
    476            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    477                Request r = e.next();
    478                if (i < idx) {
    479                    if (iAssignment[i] != null) {
    480                        if (iStudentQuality != null)
    481                            bound += getWeight(iAssignment[i], getStudentQualityConflicts(i));
    482                        else
    483                            bound += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
    484                    }
    485                    if (r.isAlternative()) {
    486                        if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
    487                            alt--;
    488                    } else {
    489                        if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    490                            alt++;
    491                    }
    492                } else {
    493                    if (!r.isAlternative())
    494                        bound += getBound(r);
    495                    else if (alt > 0) {
    496                        bound += getBound(r);
    497                        alt--;
    498                    }
    499                }
    500            }
    501            return bound;
    502        }
    503
    504        /** Value of the current schedule
    505         * @return value of the current schedule
    506         **/
    507        public double getValue() {
    508            double value = 0.0;
    509            for (int i = 0; i < iAssignment.length; i++)
    510                if (iAssignment[i] != null) {
    511                    if (iStudentQuality != null)
    512                        value += getWeight(iAssignment[i], getStudentQualityConflicts(i));
    513                    else
    514                        value += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
    515                }
    516            return value;
    517        }
    518
    519        /** Assignment penalty
    520         * @param i index of the request
    521         * @return assignment penalty
    522         **/
    523        protected double getAssignmentPenalty(int i) {
    524            return iAssignment[i].getPenalty() + iDistConfWeight * getDistanceConflicts(i).size();
    525        }
    526
    527        /** Penalty of the current schedule
    528         * @return penalty of the current schedule
    529         **/
    530        public double getPenalty() {
    531            double bestPenalty = 0;
    532            for (int i = 0; i < iAssignment.length; i++)
    533                if (iAssignment[i] != null)
    534                    bestPenalty += getAssignmentPenalty(i);
    535            return bestPenalty;
    536        }
    537
    538        /** Penalty bound of the current schedule
    539         * @param idx index of request
    540         * @return current penalty bound
    541         **/
    542        public double getPenaltyBound(int idx) {
    543            double bound = 0.0;
    544            int i = 0, alt = 0;
    545            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    546                Request r = e.next();
    547                if (i < idx) {
    548                    if (iAssignment[i] != null)
    549                        bound += getAssignmentPenalty(i);
    550                    if (r.isAlternative()) {
    551                        if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
    552                            alt--;
    553                    } else {
    554                        if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    555                            alt++;
    556                    }
    557                } else {
    558                    if (!r.isAlternative()) {
    559                        if (r instanceof CourseRequest)
    560                            bound += ((CourseRequest) r).getMinPenalty();
    561                    } else if (alt > 0) {
    562                        if (r instanceof CourseRequest)
    563                            bound += ((CourseRequest) r).getMinPenalty();
    564                        alt--;
    565                    }
    566                }
    567            }
    568            return bound;
    569        }
    570
    571        /** Save the current schedule as the best */
    572        public void saveBest() {
    573            if (iBestAssignment == null)
    574                iBestAssignment = new Enrollment[iAssignment.length];
    575            for (int i = 0; i < iAssignment.length; i++)
    576                iBestAssignment[i] = iAssignment[i];
    577            if (iMinimizePenalty)
    578                iBestValue = getPenalty();
    579            else
    580                iBestValue = getValue();
    581        }
    582
    583        /** True if the enrollment is conflicting
    584         * @param idx index of request
    585         * @param enrollment enrollment in question
    586         * @return true if there is a conflict with previous enrollments
    587         **/
    588        public boolean inConflict(final int idx, final Enrollment enrollment) {
    589            for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints())
    590                if (constraint instanceof DependentCourses) {
    591                    if (((DependentCourses)constraint).isPartialScheduleInConflict(iStudent, new LinkedSections.EnrollmentAssignment() {
    592                        @Override
    593                        public Enrollment getEnrollment(Request request, int index) {
    594                            return (index == idx ? enrollment : iAssignment[index]);
    595                        }
    596                    }, idx)) return true;
    597                } else if (constraint.inConflict(iCurrentAssignment, enrollment))
    598                    return true;
    599            for (LinkedSections linkedSections: iStudent.getLinkedSections()) {
    600                if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() {
    601                    @Override
    602                    public Enrollment getEnrollment(Request request, int index) {
    603                        return (index == idx ? enrollment : iAssignment[index]);
    604                    }
    605                }) != null) return true;
    606            }
    607            float credit = enrollment.getCredit();
    608            for (int i = 0; i < iAssignment.length; i++) {
    609                if (iAssignment[i] != null && i != idx) {
    610                    credit += iAssignment[i].getCredit();
    611                    if (credit > iStudent.getMaxCredit() || iAssignment[i].isOverlapping(enrollment))
    612                        return true;
    613                }
    614            }
    615            return false;
    616        }
    617
    618        /** First conflicting enrollment
    619         * @param idx index of request
    620         * @param enrollment enrollment in question
    621         * @return first conflicting enrollment
    622         **/
    623        public Enrollment firstConflict(int idx, Enrollment enrollment) {
    624            Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(iCurrentAssignment, enrollment);
    625            if (conflicts.contains(enrollment))
    626                return enrollment;
    627            if (!conflicts.isEmpty()) {
    628                for (Enrollment conflict : conflicts) {
    629                    if (!conflict.getStudent().equals(iStudent))
    630                        return conflict;
    631                }
    632            }
    633            float credit = enrollment.getCredit();
    634            for (int i = 0; i < iAssignment.length; i++) {
    635                if (iAssignment[i] != null && i != idx) {
    636                    credit += iAssignment[i].getCredit();
    637                    if (credit > iStudent.getMaxCredit() || iAssignment[i].isOverlapping(enrollment))
    638                    return iAssignment[i];
    639                }
    640            }
    641            return null;
    642        }
    643
    644        /** True if the given request can be assigned
    645         * @param request given request
    646         * @param idx index of request
    647         * @return true if can be assigned
    648         **/
    649        public boolean canAssign(Request request, int idx) {
    650            if (iAssignment[idx] != null)
    651                return true;
    652            int alt = 0;
    653            int i = 0;
    654            float credit = 0;
    655            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    656                Request r = e.next();
    657                if (r.equals(request))
    658                    credit += r.getMinCredit();
    659                else if (iAssignment[i] != null)
    660                    credit += iAssignment[i].getCredit();
    661                if (r.equals(request))
    662                    continue;
    663                if (r.isAlternative()) {
    664                    if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
    665                        alt--;
    666                } else {
    667                    if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    668                        alt++;
    669                }
    670            }
    671            return (!request.isAlternative() || alt > 0) && (credit <= iStudent.getMaxCredit());
    672        }
    673
    674        /** Number of assigned requests in the current schedule
    675         * @return number of assigned requests
    676         **/
    677        public int getNrAssigned() {
    678            int assigned = 0;
    679            for (int i = 0; i < iAssignment.length; i++)
    680                if (iAssignment[i] != null)
    681                    assigned += (iAssignment[i].isCourseRequest() ? 10 : 1);
    682            return assigned;
    683        }
    684
    685        /** Returns true if the given request can be left unassigned
    686         * @param request given request
    687         * @return true if can be left unassigned
    688         **/
    689        protected boolean canLeaveUnassigned(Request request) {
    690            if (request instanceof CourseRequest && ((CourseRequest)request).getFixedValue() != null) return false;
    691            if (request.isMPP() && iModel.getKeepInitialAssignments()) return false;
    692            if (iModel.getDependentCoursesConstraint() != null &&
    693                !iModel.getDependentCoursesConstraint().canLeaveUnassigned(iStudent, new LinkedSections.EnrollmentAssignment() {
    694                    @Override
    695                    public Enrollment getEnrollment(Request r, int index) {
    696                        return iAssignment[index];
    697                    }
    698                }, request)) return false;
    699            return true;
    700        }
    701
    702        /** Returns list of available enrollments for a course request
    703         * @param request given request
    704         * @return list of enrollments to consider
    705         **/
    706        protected List<Enrollment> values(final CourseRequest request) {
    707            List<Enrollment> values = request.getAvaiableEnrollments(iCurrentAssignment);
    708            Collections.sort(values, new Comparator<Enrollment>() {
    709
    710                private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
    711
    712                private Double value(Enrollment e) {
    713                    Double value = iValues.get(e);
    714                    if (value == null) {
    715                        if (iModel.getStudentQuality() != null)
    716                            value = iModel.getStudentWeights().getWeight(iCurrentAssignment, e, iModel.getStudentQuality().conflicts(e));
    717                        else
    718                            value = iModel.getStudentWeights().getWeight(iCurrentAssignment, e,
    719                                    (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)),
    720                                    (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().conflicts(e)));
    721                        iValues.put(e, value);
    722                    }
    723                    return value;
    724                }
    725
    726                @Override
    727                public int compare(Enrollment e1, Enrollment e2) {
    728                    if (e1.equals(e2)) return 0;
    729                    if (e1.equals(iCurrentAssignment.getValue(request))) return -1;
    730                    if (e2.equals(iCurrentAssignment.getValue(request))) return 1;
    731                    if (iTimesToAvoid != null) {
    732                        double o1 = 0.0, o2 = 0.0;
    733                        for (Section s : e1.getSections()) {
    734                            if (s.getTime() != null)
    735                                for (TimeToAvoid avoid : iTimesToAvoid) {
    736                                    if (avoid.priority() > e1.getRequest().getPriority())
    737                                        o1 += avoid.overlap(s.getTime());
    738                                }
    739                        }
    740                        for (Section s : e2.getSections()) {
    741                            if (s.getTime() != null)
    742                                for (TimeToAvoid avoid : iTimesToAvoid) {
    743                                    if (avoid.priority() > e2.getRequest().getPriority())
    744                                        o2 += avoid.overlap(s.getTime());
    745                                }
    746                        }
    747                        if (o1 < o2)
    748                            return -1;
    749                        if (o2 < o1)
    750                            return 1;
    751                    }
    752                    Double v1 = value(e1), v2 = value(e2);
    753                    return v1.equals(v2) ? e1.compareTo(iCurrentAssignment, e2) : v2.compareTo(v1);
    754                }
    755
    756            });
    757            return values;
    758        }
    759
    760        /** branch &amp; bound search
    761         * @param idx index of request
    762         **/
    763        public void backTrack(int idx) {
    764            if (sDebug)
    765                sLog.debug("backTrack(" + getNrAssigned() + "/" + getValue() + "," + idx + ")");
    766            if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
    767                if (sDebug)
    768                    sLog.debug("  -- timeout reached");
    769                iTimeoutReached = true;
    770                return;
    771            }
    772            if (iMinimizePenalty) {
    773                if (getBestAssignment() != null
    774                        && (getNrAssignedBound(idx) < getBestNrAssigned() || (getNrAssignedBound(idx) == getBestNrAssigned() && getPenaltyBound(idx) >= getBestValue()))) {
    775                    if (sDebug)
    776                        sLog.debug("  -- branch number of assigned " + getNrAssignedBound(idx) + "<"
    777                                + getBestNrAssigned() + ", or penalty " + getPenaltyBound(idx) + ">=" + getBestValue());
    778                    return;
    779                }
    780                if (idx == iAssignment.length) {
    781                    if (getBestAssignment() == null
    782                            || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) {
    783                        if (sDebug)
    784                            sLog.debug("  -- best solution found " + getNrAssigned() + "/" + getPenalty());
    785                        saveBest();
    786                    }
    787                    return;
    788                }
    789            } else {
    790                if (getBestAssignment() != null && getBound(idx) >= getBestValue()) {
    791                    if (sDebug)
    792                        sLog.debug("  -- branch " + getBound(idx) + " >= " + getBestValue());
    793                    return;
    794                }
    795                if (idx == iAssignment.length) {
    796                    if (getBestAssignment() == null || getValue() < getBestValue()) {
    797                        if (sDebug)
    798                            sLog.debug("  -- best solution found " + getNrAssigned() + "/" + getValue());
    799                        saveBest();
    800                    }
    801                    return;
    802                }
    803            }
    804
    805            Request request = iStudent.getRequests().get(idx);
    806            if (sDebug)
    807                sLog.debug("  -- request: " + request);
    808            if (!canAssign(request, idx)) {
    809                if (sDebug)
    810                    sLog.debug("    -- cannot assign");
    811                backTrack(idx + 1);
    812                return;
    813            }
    814            List<Enrollment> values = null;
    815            if (request instanceof CourseRequest) {
    816                CourseRequest courseRequest = (CourseRequest) request;
    817                if (courseRequest.getInitialAssignment() != null && iModel.isMPP()) {
    818                    Enrollment enrollment = courseRequest.getInitialAssignment();
    819                    if (!inConflict(idx, enrollment)) {
    820                        iAssignment[idx] = enrollment;
    821                        backTrack(idx + 1);
    822                        iAssignment[idx] = null;
    823                        return;
    824                    }
    825                }
    826                if (!courseRequest.getSelectedChoices().isEmpty()) {
    827                    if (sDebug)
    828                        sLog.debug("    -- selection among selected enrollments");
    829                    values = courseRequest.getSelectedEnrollments(iCurrentAssignment, true);
    830                    if (values != null && !values.isEmpty()) {
    831                        boolean hasNoConflictValue = false;
    832                        for (Enrollment enrollment : values) {
    833                            if (inConflict(idx, enrollment))
    834                                continue;
    835                            hasNoConflictValue = true;
    836                            if (sDebug)
    837                                sLog.debug("      -- nonconflicting enrollment found: " + enrollment);
    838                            iAssignment[idx] = enrollment;
    839                            backTrack(idx + 1);
    840                            iAssignment[idx] = null;
    841                        }
    842                        if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict)
    843                            return;
    844                    }
    845                }
    846                values = iValues.get(courseRequest);
    847                if (values == null) {
    848                    values = values(courseRequest);
    849                    iValues.put(courseRequest, values);
    850                }
    851            } else {
    852                values = request.computeEnrollments(iCurrentAssignment);
    853            }
    854            if (sDebug) {
    855                sLog.debug("  -- nrValues: " + values.size());
    856                int vIdx = 1;
    857                for (Enrollment enrollment : values) {
    858                    if (sDebug)
    859                        sLog.debug("    -- [" + vIdx + "]: " + enrollment);
    860                }
    861            }
    862            boolean hasNoConflictValue = false;
    863            for (Enrollment enrollment : values) {
    864                if (sDebug)
    865                    sLog.debug("    -- enrollment: " + enrollment);
    866                if (sDebug) {
    867                    Enrollment conflict = firstConflict(idx, enrollment);
    868                    if (conflict != null) {
    869                        sLog.debug("        -- in conflict with: " + conflict);
    870                        continue;
    871                    }
    872                } else {
    873                    if (inConflict(idx, enrollment)) continue;
    874                }
    875                hasNoConflictValue = true;
    876                iAssignment[idx] = enrollment;
    877                backTrack(idx + 1);
    878                iAssignment[idx] = null;
    879            }
    880            if (canLeaveUnassigned(request) && (!hasNoConflictValue || request instanceof CourseRequest))
    881                backTrack(idx + 1);
    882        }
    883    }
    884
    885    /** Branch &amp; bound neighbour -- a schedule of a student */
    886    public static class BranchBoundNeighbour implements Neighbour<Request, Enrollment> {
    887        private double iValue;
    888        private Enrollment[] iAssignment;
    889        private Student iStudent;
    890
    891        /**
    892         * Constructor
    893         *
    894         * @param student selected student
    895         * @param value
    896         *            value of the schedule
    897         * @param assignment
    898         *            enrollments of student's requests
    899         */
    900        public BranchBoundNeighbour(Student student, double value, Enrollment[] assignment) {
    901            iValue = value;
    902            iAssignment = assignment;
    903            iStudent = student;
    904        }
    905
    906        @Override
    907        public double value(Assignment<Request, Enrollment> assignment) {
    908            return iValue;
    909        }
    910
    911        /** Assignment
    912         * @return an enrollment for each request of the student
    913         **/
    914        public Enrollment[] getAssignment() {
    915            return iAssignment;
    916        }
    917
    918        /** Student
    919         * @return selected student
    920         **/
    921        public Student getStudent() {
    922            return iStudent;
    923        }
    924
    925        /** Assign the schedule */
    926        @Override
    927        public void assign(Assignment<Request, Enrollment> assignment, long iteration) {
    928            for (int i = 0; i < iAssignment.length; i++)
    929                assignment.unassign(iteration, iStudent.getRequests().get(i), iAssignment[i]);
    930            for (int i = 0; i < iAssignment.length; i++)
    931                if (iAssignment[i] != null)
    932                    assignment.assign(iteration, iAssignment[i]);
    933        }
    934
    935        @Override
    936        public String toString() {
    937            StringBuffer sb = new StringBuffer("B&B{ " + iStudent + " " + sDF.format(-iValue * 100.0) + "%");
    938            int idx = 0;
    939            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); idx++) {
    940                Request request = e.next();
    941                sb.append("\n  " + request);
    942                Enrollment enrollment = iAssignment[idx];
    943                if (enrollment == null)
    944                    sb.append("  -- not assigned");
    945                else
    946                    sb.append("  -- " + enrollment);
    947            }
    948            sb.append("\n}");
    949            return sb.toString();
    950        }
    951
    952        @Override
    953        public Map<Request, Enrollment> assignments() {
    954            Map<Request, Enrollment> ret = new HashMap<Request, Enrollment>();
    955            for (int i = 0; i < iAssignment.length; i++)
    956                ret.put(iStudent.getRequests().get(i), iAssignment[i]);
    957            return ret;
    958        }
    959
    960    }
    961
    962    @Override
    963    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
    964        if (iNbrIterations > 0)
    965            info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" +
    966                    iNbrIterations + " iterations, " +
    967                    (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") +
    968                    sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iTimeout / 1000.0) + " seconds reached)");
    969    }
    970
    971    @Override
    972    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
    973    }
    974
    975    /**
    976     * Only consider students meeting the given filter.
    977     */
    978    public StudentFilter getFilter() { return iFilter; }
    979
    980    /**
    981     * Only consider students meeting the given filter.
    982     */
    983    public BranchBoundSelection withFilter(StudentFilter filter) { iFilter = filter; return this; }
    984
    985    @Override
    986    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
    987        return false;
    988    }
    989    @Override
    990    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
    991        return false;
    992    }
    993    @Override
    994    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    995        return false;
    996    }
    997    @Override
    998    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    999        if (neighbour instanceof BranchBoundNeighbour)
    1000            addStudent(((BranchBoundNeighbour)neighbour).getStudent());
    1001    }
    1002}