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