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