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