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