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