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