    001package net.sf.cpsolver.studentsct.heuristics.selection;
    002
    003import java.text.DecimalFormat;
    004import java.util.Collections;
    005import java.util.Comparator;
    006import java.util.HashMap;
    007import java.util.HashSet;
    008import java.util.Iterator;
    009import java.util.List;
    010import java.util.Set;
    011
    012import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    013import net.sf.cpsolver.ifs.model.GlobalConstraint;
    014import net.sf.cpsolver.ifs.model.Neighbour;
    015import net.sf.cpsolver.ifs.solution.Solution;
    016import net.sf.cpsolver.ifs.solver.Solver;
    017import net.sf.cpsolver.ifs.util.DataProperties;
    018import net.sf.cpsolver.ifs.util.JProf;
    019import net.sf.cpsolver.ifs.util.Progress;
    020import net.sf.cpsolver.studentsct.StudentSectioningModel;
    021import net.sf.cpsolver.studentsct.constraint.LinkedSections;
    022import net.sf.cpsolver.studentsct.extension.DistanceConflict;
    023import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter;
    024import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
    025import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
    026import net.sf.cpsolver.studentsct.model.CourseRequest;
    027import net.sf.cpsolver.studentsct.model.Enrollment;
    028import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
    029import net.sf.cpsolver.studentsct.model.Request;
    030import net.sf.cpsolver.studentsct.model.Student;
    031import net.sf.cpsolver.studentsct.weights.StudentWeights;
    032
    033import org.apache.log4j.Logger;
    034
    035/**
    036 * Section all students using incremental branch & bound (no unassignments). All
    037 * students are taken in a random order, for each student a branch & bound
    038 * algorithm is used to find his/her best schedule on top of all other existing
    039 * student schedules (no enrollment of a different student is unassigned).
    040 *
    041 * <br>
    042 * <br>
    043 * Parameters: <br>
    044 * <table border='1'>
    045 * <tr>
    046 * <th>Parameter</th>
    047 * <th>Type</th>
    048 * <th>Comment</th>
    049 * </tr>
    050 * <tr>
    051 * <td>Neighbour.BranchAndBoundTimeout</td>
    052 * <td>{@link Integer}</td>
    053 * <td>Timeout for each neighbour selection (in milliseconds).</td>
    054 * </tr>
    055 * <tr>
    056 * <td>Neighbour.BranchAndBoundMinimizePenalty</td>
    057 * <td>{@link Boolean}</td>
    058 * <td>If true, section penalties (instead of section values) are minimized:
    059 * overall penalty is minimized together with the maximization of the number of
    060 * assigned requests and minimization of distance conflicts -- this variant is
    061 * to better mimic the case when students can choose their sections (section
    062 * times).</td>
    063 * </tr>
    064 * </table>
    065 * <br>
    066 * <br>
    067 *
    068 * @version StudentSct 1.2 (Student Sectioning)<br>
    069 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    070 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    071 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    072 * <br>
    073 *          This library is free software; you can redistribute it and/or modify
    074 *          it under the terms of the GNU Lesser General Public License as
    075 *          published by the Free Software Foundation; either version 3 of the
    076 *          License, or (at your option) any later version. <br>
    077 * <br>
    078 *          This library is distributed in the hope that it will be useful, but
    079 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    080 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    081 *          Lesser General Public License for more details. <br>
    082 * <br>
    083 *          You should have received a copy of the GNU Lesser General Public
    084 *          License along with this library; if not see
    085 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    086 */
    087
    088public class BranchBoundSelection implements NeighbourSelection<Request, Enrollment> {
    089    private static Logger sLog = Logger.getLogger(BranchBoundSelection.class);
    090    private static DecimalFormat sDF = new DecimalFormat("0.00");
    091    protected int iTimeout = 10000;
    092    protected DistanceConflict iDistanceConflict = null;
    093    protected TimeOverlapsCounter iTimeOverlaps = null;
    094    protected StudentSectioningModel iModel = null;
    095    public static boolean sDebug = false;
    096    protected Iterator<Student> iStudentsEnumeration = null;
    097    protected boolean iMinimizePenalty = false;
    098    protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
    099    protected double iDistConfWeight = 1.0;
    100
    101    /**
    102     * Constructor
    103     *
    104     * @param properties
    105     *            configuration
    106     */
    107    public BranchBoundSelection(DataProperties properties) {
    108        iTimeout = properties.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout);
    109        iMinimizePenalty = properties.getPropertyBoolean("Neighbour.BranchAndBoundMinimizePenalty", iMinimizePenalty);
    110        if (iMinimizePenalty)
    111            sLog.info("Overall penalty is going to be minimized (together with the maximization of the number of assigned requests and minimization of distance conflicts).");
    112        if (properties.getProperty("Neighbour.BranchAndBoundOrder") != null) {
    113            try {
    114                iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.BranchAndBoundOrder"))
    115                        .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
    116            } catch (Exception e) {
    117                sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
    118            }
    119        }
    120        iDistConfWeight = properties.getPropertyDouble("DistanceConflict.Weight", iDistConfWeight);
    121    }
    122
    123    /**
    124     * Initialize
    125     */
    126    public void init(Solver<Request, Enrollment> solver, String name) {
    127        setModel((StudentSectioningModel) solver.currentSolution().getModel());
    128        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, iModel.getStudents().size());
    129    }
    130
    131    public void setModel(StudentSectioningModel model) {
    132        iModel = model;
    133        List<Student> students = iOrder.order(iModel.getStudents());
    134        iStudentsEnumeration = students.iterator();
    135        iTimeOverlaps = model.getTimeOverlaps();
    136        iDistanceConflict = model.getDistanceConflict();
    137    }
    138
    139    @Override
    140    public void init(Solver<Request, Enrollment> solver) {
    141        init(solver, "Branch&bound...");
    142    }
    143
    144    /**
    145     * Select neighbour. All students are taken, one by one in a random order.
    146     * For each student a branch & bound search is employed.
    147     */
    148    @Override
    149    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    150        while (iStudentsEnumeration.hasNext()) {
    151            Student student = iStudentsEnumeration.next();
    152            Progress.getInstance(solution.getModel()).incProgress();
    153            Neighbour<Request, Enrollment> neighbour = getSelection(student).select();
    154            if (neighbour != null)
    155                return neighbour;
    156        }
    157        return null;
    158    }
    159
    160    /**
    161     * Branch & bound selection for a student
    162     */
    163    public Selection getSelection(Student student) {
    164        return new Selection(student);
    165    }
    166
    167    /**
    168     * Branch & bound selection for a student
    169     */
    170    public class Selection {
    171        /** Student */
    172        protected Student iStudent;
    173        /** Start time */
    174        protected long iT0;
    175        /** End time */
    176        protected long iT1;
    177        /** Was timeout reached */
    178        protected boolean iTimeoutReached;
    179        /** Current assignment */
    180        protected Enrollment[] iAssignment;
    181        /** Best assignment */
    182        protected Enrollment[] iBestAssignment;
    183        /** Best value */
    184        protected double iBestValue;
    185        /** Value cache */
    186        protected HashMap<CourseRequest, List<Enrollment>> iValues;
    187
    188        /**
    189         * Constructor
    190         *
    191         * @param student
    192         *            selected student
    193         */
    194        public Selection(Student student) {
    195            iStudent = student;
    196        }
    197
    198        /**
    199         * Execute branch & bound, return the best found schedule for the
    200         * selected student.
    201         */
    202        public BranchBoundNeighbour select() {
    203            iT0 = JProf.currentTimeMillis();
    204            iTimeoutReached = false;
    205            iAssignment = new Enrollment[iStudent.getRequests().size()];
    206            iBestAssignment = null;
    207            iBestValue = 0;
    208
    209            int i = 0;
    210            for (Request r: iStudent.getRequests())
    211                iAssignment[i++] = r.getAssignment();
    212            saveBest();
    213            for (int j = 0; j < iAssignment.length; j++)
    214                iAssignment[j] = null;
    215
    216
    217            iValues = new HashMap<CourseRequest, List<Enrollment>>();
    218            backTrack(0);
    219            iT1 = JProf.currentTimeMillis();
    220            if (iBestAssignment == null)
    221                return null;
    222            return new BranchBoundNeighbour(iStudent, iBestValue, iBestAssignment);
    223        }
    224
    225        /** Was timeout reached */
    226        public boolean isTimeoutReached() {
    227            return iTimeoutReached;
    228        }
    229
    230        /** Time (in milliseconds) the branch & bound did run */
    231        public long getTime() {
    232            return iT1 - iT0;
    233        }
    234
    235        /** Best schedule */
    236        public Enrollment[] getBestAssignment() {
    237            return iBestAssignment;
    238        }
    239
    240        /** Value of the best schedule */
    241        public double getBestValue() {
    242            return iBestValue;
    243        }
    244
    245        /** Number of requests assigned in the best schedule */
    246        public int getBestNrAssigned() {
    247            int nrAssigned = 0;
    248            for (int i = 0; i < iBestAssignment.length; i++)
    249                if (iBestAssignment[i] != null)
    250                    nrAssigned += (iBestAssignment[i].isCourseRequest() ? 10 : 1);
    251            return nrAssigned;
    252        }
    253
    254        /** Bound for the number of assigned requests in the current schedule */
    255        public int getNrAssignedBound(int idx) {
    256            int bound = 0;
    257            int i = 0, alt = 0;
    258            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    259                Request r = e.next();
    260                boolean cr = r instanceof CourseRequest;
    261                if (i < idx) {
    262                    if (iAssignment[i] != null)
    263                        bound += (cr ? 10 : 1);
    264                    if (r.isAlternative()) {
    265                        if (iAssignment[i] != null || (cr && ((CourseRequest) r).isWaitlist()))
    266                            alt--;
    267                    } else {
    268                        if (cr && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    269                            alt++;
    270                    }
    271                } else {
    272                    if (!r.isAlternative())
    273                        bound += (cr ? 10 : 1);
    274                    else if (alt > 0) {
    275                        bound += (cr ? 10 : 1);
    276                        alt--;
    277                    }
    278                }
    279            }
    280            return bound;
    281        }
    282
    283        /**
    284         * Distance conflicts of idx-th assignment of the current
    285         * schedule
    286         */
    287        public Set<DistanceConflict.Conflict> getDistanceConflicts(int idx) {
    288            if (iDistanceConflict == null || iAssignment[idx] == null)
    289                return null;
    290            Set<DistanceConflict.Conflict> dist = iDistanceConflict.conflicts(iAssignment[idx]);
    291            for (int x = 0; x < idx; x++)
    292                if (iAssignment[x] != null)
    293                    dist.addAll(iDistanceConflict.conflicts(iAssignment[x], iAssignment[idx]));
    294            return dist;
    295        }
    296
    297        /**
    298         * Time overlapping conflicts of idx-th assignment of the current
    299         * schedule
    300         */
    301        public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(int idx) {
    302            if (iTimeOverlaps == null || iAssignment[idx] == null)
    303                return null;
    304            Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
    305            for (int x = 0; x < idx; x++)
    306                if (iAssignment[x] != null)
    307                    overlaps.addAll(iTimeOverlaps.conflicts(iAssignment[x], iAssignment[idx]));
    308                else if (iStudent.getRequests().get(x) instanceof FreeTimeRequest)
    309                    overlaps.addAll(iTimeOverlaps.conflicts(((FreeTimeRequest)iStudent.getRequests().get(x)).createEnrollment(), iAssignment[idx]));
    310            return overlaps;
    311        }
    312
    313        /**
    314         * Weight of an assignment. Unlike {@link StudentWeights#getWeight(Enrollment, Set, Set)}, only count this side of distance conflicts and time overlaps.
    315         **/
    316        protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
    317            double weight = - iModel.getStudentWeights().getWeight(enrollment);
    318            if (distanceConflicts != null)
    319                for (DistanceConflict.Conflict c: distanceConflicts) {
    320                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
    321                    if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
    322                        weight += iModel.getStudentWeights().getDistanceConflictWeight(c);
    323                }
    324            if (timeOverlappingConflicts != null)
    325                for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
    326                    weight += iModel.getStudentWeights().getTimeOverlapConflictWeight(enrollment, c);
    327                }
    328            return enrollment.getRequest().getWeight() * weight;
    329        }
    330
    331        /** Return bound of a request */
    332        protected double getBound(Request r) {
    333            return r.getBound();
    334        }
    335
    336        /** Bound for the current schedule */
    337        public double getBound(int idx) {
    338            double bound = 0.0;
    339            int i = 0, alt = 0;
    340            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    341                Request r = e.next();
    342                if (i < idx) {
    343                    if (iAssignment[i] != null)
    344                        bound += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
    345                    if (r.isAlternative()) {
    346                        if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
    347                            alt--;
    348                    } else {
    349                        if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    350                            alt++;
    351                    }
    352                } else {
    353                    if (!r.isAlternative())
    354                        bound += getBound(r);
    355                    else if (alt > 0) {
    356                        bound += getBound(r);
    357                        alt--;
    358                    }
    359                }
    360            }
    361            return bound;
    362        }
    363
    364        /** Value of the current schedule */
    365        public double getValue() {
    366            double value = 0.0;
    367            for (int i = 0; i < iAssignment.length; i++)
    368                if (iAssignment[i] != null)
    369                    value += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
    370            return value;
    371        }
    372
    373        /** Assignment penalty */
    374        protected double getAssignmentPenalty(int i) {
    375            return iAssignment[i].getPenalty() + iDistConfWeight * getDistanceConflicts(i).size();
    376        }
    377
    378        /** Penalty of the current schedule */
    379        public double getPenalty() {
    380            double bestPenalty = 0;
    381            for (int i = 0; i < iAssignment.length; i++)
    382                if (iAssignment[i] != null)
    383                    bestPenalty += getAssignmentPenalty(i);
    384            return bestPenalty;
    385        }
    386
    387        /** Penalty bound of the current schedule */
    388        public double getPenaltyBound(int idx) {
    389            double bound = 0.0;
    390            int i = 0, alt = 0;
    391            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    392                Request r = e.next();
    393                if (i < idx) {
    394                    if (iAssignment[i] != null)
    395                        bound += getAssignmentPenalty(i);
    396                    if (r.isAlternative()) {
    397                        if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
    398                            alt--;
    399                    } else {
    400                        if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    401                            alt++;
    402                    }
    403                } else {
    404                    if (!r.isAlternative()) {
    405                        if (r instanceof CourseRequest)
    406                            bound += ((CourseRequest) r).getMinPenalty();
    407                    } else if (alt > 0) {
    408                        if (r instanceof CourseRequest)
    409                            bound += ((CourseRequest) r).getMinPenalty();
    410                        alt--;
    411                    }
    412                }
    413            }
    414            return bound;
    415        }
    416
    417        /** Save the current schedule as the best */
    418        public void saveBest() {
    419            if (iBestAssignment == null)
    420                iBestAssignment = new Enrollment[iAssignment.length];
    421            for (int i = 0; i < iAssignment.length; i++)
    422                iBestAssignment[i] = iAssignment[i];
    423            if (iMinimizePenalty)
    424                iBestValue = getPenalty();
    425            else
    426                iBestValue = getValue();
    427        }
    428
    429        /** True if the enrollment is conflicting */
    430        public boolean inConflict(final int idx, final Enrollment enrollment) {
    431            for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints())
    432                if (constraint.inConflict(enrollment))
    433                    return true;
    434            for (LinkedSections linkedSections: iStudent.getLinkedSections()) {
    435                if (linkedSections.inConflict(enrollment, new LinkedSections.Assignment() {
    436                    @Override
    437                    public Enrollment getEnrollment(Request request, int index) {
    438                        return (index == idx ? enrollment : iAssignment[index]);
    439                    }
    440                }) != null) return true;
    441            }
    442            for (int i = 0; i < iAssignment.length; i++)
    443                if (iAssignment[i] != null && i != idx && iAssignment[i].isOverlapping(enrollment))
    444                    return true;
    445            return false;
    446        }
    447
    448        /** First conflicting enrollment */
    449        public Enrollment firstConflict(int idx, Enrollment enrollment) {
    450            Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(enrollment);
    451            if (conflicts.contains(enrollment))
    452                return enrollment;
    453            if (!conflicts.isEmpty()) {
    454                for (Enrollment conflict : conflicts) {
    455                    if (!conflict.getStudent().equals(iStudent))
    456                        return conflict;
    457                }
    458            }
    459            for (int i = 0; i < iAssignment.length; i++) {
    460                if (iAssignment[i] == null || i == idx)
    461                    continue;
    462                if (iAssignment[i].isOverlapping(enrollment))
    463                    return iAssignment[i];
    464            }
    465            return null;
    466        }
    467
    468        /** True if the given request can be assigned */
    469        public boolean canAssign(Request request, int idx) {
    470            if (!request.isAlternative() || iAssignment[idx] != null)
    471                return true;
    472            int alt = 0;
    473            int i = 0;
    474            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
    475                Request r = e.next();
    476                if (r.equals(request))
    477                    continue;
    478                if (r.isAlternative()) {
    479                    if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
    480                        alt--;
    481                } else {
    482                    if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
    483                        alt++;
    484                }
    485            }
    486            return (alt > 0);
    487        }
    488
    489        /** Number of assigned requests in the current schedule */
    490        public int getNrAssigned() {
    491            int assigned = 0;
    492            for (int i = 0; i < iAssignment.length; i++)
    493                if (iAssignment[i] != null)
    494                    assigned += (iAssignment[i].isCourseRequest() ? 10 : 1);
    495            return assigned;
    496        }
    497
    498        /** Returns true if the given request can be left unassigned */
    499        protected boolean canLeaveUnassigned(Request request) {
    500            return true;
    501        }
    502
    503        /** Returns list of available enrollments for a course request */
    504        protected List<Enrollment> values(final CourseRequest request) {
    505            List<Enrollment> values = request.getAvaiableEnrollments();
    506            Collections.sort(values, new Comparator<Enrollment>() {
    507
    508                private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
    509
    510                private Double value(Enrollment e) {
    511                    Double value = iValues.get(e);
    512                    if (value == null) {
    513                        value = iModel.getStudentWeights().getWeight(e,
    514                                        (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)),
    515                                        (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().freeTimeConflicts(e)));
    516                        iValues.put(e, value);
    517                    }
    518                    return value;
    519                }
    520
    521                @Override
    522                public int compare(Enrollment e1, Enrollment e2) {
    523                    if (e1.equals(request.getAssignment())) return -1;
    524                    if (e2.equals(request.getAssignment())) return 1;
    525                    Double v1 = value(e1), v2 = value(e2);
    526                    return v1.equals(v2) ? e1.compareTo(e2) : v2.compareTo(v1);
    527                }
    528
    529            });
    530            return values;
    531        }
    532
    533        /** branch & bound search */
    534        public void backTrack(int idx) {
    535            if (sDebug)
    536                sLog.debug("backTrack(" + getNrAssigned() + "/" + getValue() + "," + idx + ")");
    537            if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
    538                if (sDebug)
    539                    sLog.debug("  -- timeout reached");
    540                iTimeoutReached = true;
    541                return;
    542            }
    543            if (iMinimizePenalty) {
    544                if (getBestAssignment() != null
    545                        && (getNrAssignedBound(idx) < getBestNrAssigned() || (getNrAssignedBound(idx) == getBestNrAssigned() && getPenaltyBound(idx) >= getBestValue()))) {
    546                    if (sDebug)
    547                        sLog.debug("  -- branch number of assigned " + getNrAssignedBound(idx) + "<"
    548                                + getBestNrAssigned() + ", or penalty " + getPenaltyBound(idx) + ">=" + getBestValue());
    549                    return;
    550                }
    551                if (idx == iAssignment.length) {
    552                    if (getBestAssignment() == null
    553                            || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) {
    554                        if (sDebug)
    555                            sLog.debug("  -- best solution found " + getNrAssigned() + "/" + getPenalty());
    556                        saveBest();
    557                    }
    558                    return;
    559                }
    560            } else {
    561                if (getBestAssignment() != null && getBound(idx) >= getBestValue()) {
    562                    if (sDebug)
    563                        sLog.debug("  -- branch " + getBound(idx) + " >= " + getBestValue());
    564                    return;
    565                }
    566                if (idx == iAssignment.length) {
    567                    if (getBestAssignment() == null || getValue() < getBestValue()) {
    568                        if (sDebug)
    569                            sLog.debug("  -- best solution found " + getNrAssigned() + "/" + getValue());
    570                        saveBest();
    571                    }
    572                    return;
    573                }
    574            }
    575
    576            Request request = iStudent.getRequests().get(idx);
    577            if (sDebug)
    578                sLog.debug("  -- request: " + request);
    579            if (!canAssign(request, idx)) {
    580                if (sDebug)
    581                    sLog.debug("    -- cannot assign");
    582                backTrack(idx + 1);
    583                return;
    584            }
    585            List<Enrollment> values = null;
    586            if (request instanceof CourseRequest) {
    587                CourseRequest courseRequest = (CourseRequest) request;
    588                if (!courseRequest.getSelectedChoices().isEmpty()) {
    589                    if (sDebug)
    590                        sLog.debug("    -- selection among selected enrollments");
    591                    values = courseRequest.getSelectedEnrollments(true);
    592                    if (values != null && !values.isEmpty()) {
    593                        boolean hasNoConflictValue = false;
    594                        for (Enrollment enrollment : values) {
    595                            if (inConflict(idx, enrollment))
    596                                continue;
    597                            hasNoConflictValue = true;
    598                            if (sDebug)
    599                                sLog.debug("      -- nonconflicting enrollment found: " + enrollment);
    600                            iAssignment[idx] = enrollment;
    601                            backTrack(idx + 1);
    602                            iAssignment[idx] = null;
    603                        }
    604                        if (hasNoConflictValue)
    605                            return;
    606                    }
    607                }
    608                values = iValues.get(courseRequest);
    609                if (values == null) {
    610                    values = values(courseRequest);
    611                    iValues.put(courseRequest, values);
    612                }
    613            } else {
    614                values = request.computeEnrollments();
    615            }
    616            if (sDebug) {
    617                sLog.debug("  -- nrValues: " + values.size());
    618                int vIdx = 1;
    619                for (Enrollment enrollment : values) {
    620                    if (sDebug)
    621                        sLog.debug("    -- [" + vIdx + "]: " + enrollment);
    622                }
    623            }
    624            boolean hasNoConflictValue = false;
    625            for (Enrollment enrollment : values) {
    626                if (sDebug)
    627                    sLog.debug("    -- enrollment: " + enrollment);
    628                if (sDebug) {
    629                    Enrollment conflict = firstConflict(idx, enrollment);
    630                    if (conflict != null) {
    631                        sLog.debug("        -- in conflict with: " + conflict);
    632                        continue;
    633                    }
    634                } else {
    635                    if (inConflict(idx, enrollment)) continue;
    636                }
    637                hasNoConflictValue = true;
    638                iAssignment[idx] = enrollment;
    639                backTrack(idx + 1);
    640                iAssignment[idx] = null;
    641            }
    642            if (canLeaveUnassigned(request) && (!hasNoConflictValue || request instanceof CourseRequest))
    643                backTrack(idx + 1);
    644        }
    645    }
    646
    647    /** Branch & bound neighbour -- a schedule of a student */
    648    public static class BranchBoundNeighbour extends Neighbour<Request, Enrollment> {
    649        private double iValue;
    650        private Enrollment[] iAssignment;
    651        private Student iStudent;
    652
    653        /**
    654         * Constructor
    655         *
    656         * @param value
    657         *            value of the schedule
    658         * @param assignment
    659         *            enrollments of student's requests
    660         */
    661        public BranchBoundNeighbour(Student student, double value, Enrollment[] assignment) {
    662            iValue = value;
    663            iAssignment = assignment;
    664            iStudent = student;
    665        }
    666
    667        @Override
    668        public double value() {
    669            return iValue;
    670        }
    671
    672        /** Assignment */
    673        public Enrollment[] getAssignment() {
    674            return iAssignment;
    675        }
    676
    677        /** Student */
    678        public Student getStudent() {
    679            return iStudent;
    680        }
    681
    682        /** Assign the schedule */
    683        @Override
    684        public void assign(long iteration) {
    685            for (Request r: iStudent.getRequests())
    686                if (r.getAssignment() != null) r.unassign(iteration);
    687            for (int i = 0; i < iAssignment.length; i++)
    688                if (iAssignment[i] != null)
    689                    iAssignment[i].variable().assign(iteration, iAssignment[i]);
    690        }
    691
    692        @Override
    693        public String toString() {
    694            StringBuffer sb = new StringBuffer("B&B{ " + iStudent + " " + sDF.format(-value() * 100.0) + "%");
    695            int idx = 0;
    696            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); idx++) {
    697                Request request = e.next();
    698                sb.append("\n  " + request);
    699                Enrollment enrollment = iAssignment[idx];
    700                if (enrollment == null)
    701                    sb.append("  -- not assigned");
    702                else
    703                    sb.append("  -- " + enrollment);
    704            }
    705            sb.append("\n}");
    706            return sb.toString();
    707        }
    708
    709    }
    710}