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            return overlaps;
351        }
352        
353        /**
354         * Weight of an assignment. Unlike {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this side of distance conflicts and time overlaps.
355         * @param enrollment an enrollment
356         * @param distanceConflicts set of distance conflicts
357         * @param timeOverlappingConflicts set of time overlapping conflicts
358         * @return value of the assignment
359         **/
360        protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
361            double weight = - iModel.getStudentWeights().getWeight(iCurrentAssignment, enrollment);
362            if (distanceConflicts != null)
363                for (DistanceConflict.Conflict c: distanceConflicts) {
364                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
365                    if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
366                        weight += iModel.getStudentWeights().getDistanceConflictWeight(iCurrentAssignment, c);
367                }
368            if (timeOverlappingConflicts != null)
369                for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
370                    weight += iModel.getStudentWeights().getTimeOverlapConflictWeight(iCurrentAssignment, enrollment, c);
371                }
372            return enrollment.getRequest().getWeight() * weight;
373        }
374        
375        /** Return bound of a request 
376         * @param r a request
377         * @return bound 
378         **/
379        protected double getBound(Request r) {
380            return r.getBound();
381        }
382
383        /** Bound for the current schedule 
384         * @param idx index of the request
385         * @return current bound
386         **/
387        public double getBound(int idx) {
388            double bound = 0.0;
389            int i = 0, alt = 0;
390            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
391                Request r = e.next();
392                if (i < idx) {
393                    if (iAssignment[i] != null)
394                        bound += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
395                    if (r.isAlternative()) {
396                        if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
397                            alt--;
398                    } else {
399                        if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
400                            alt++;
401                    }
402                } else {
403                    if (!r.isAlternative())
404                        bound += getBound(r);
405                    else if (alt > 0) {
406                        bound += getBound(r);
407                        alt--;
408                    }
409                }
410            }
411            return bound;
412        }
413
414        /** Value of the current schedule 
415         * @return value of the current schedule
416         **/
417        public double getValue() {
418            double value = 0.0;
419            for (int i = 0; i < iAssignment.length; i++)
420                if (iAssignment[i] != null)
421                    value += getWeight(iAssignment[i], getDistanceConflicts(i), getTimeOverlappingConflicts(i));
422            return value;
423        }
424
425        /** Assignment penalty 
426         * @param i index of the request
427         * @return assignment penalty
428         **/
429        protected double getAssignmentPenalty(int i) {
430            return iAssignment[i].getPenalty() + iDistConfWeight * getDistanceConflicts(i).size();
431        }
432
433        /** Penalty of the current schedule 
434         * @return penalty of the current schedule
435         **/
436        public double getPenalty() {
437            double bestPenalty = 0;
438            for (int i = 0; i < iAssignment.length; i++)
439                if (iAssignment[i] != null)
440                    bestPenalty += getAssignmentPenalty(i);
441            return bestPenalty;
442        }
443
444        /** Penalty bound of the current schedule 
445         * @param idx index of request
446         * @return current penalty bound
447         **/
448        public double getPenaltyBound(int idx) {
449            double bound = 0.0;
450            int i = 0, alt = 0;
451            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
452                Request r = e.next();
453                if (i < idx) {
454                    if (iAssignment[i] != null)
455                        bound += getAssignmentPenalty(i);
456                    if (r.isAlternative()) {
457                        if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
458                            alt--;
459                    } else {
460                        if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
461                            alt++;
462                    }
463                } else {
464                    if (!r.isAlternative()) {
465                        if (r instanceof CourseRequest)
466                            bound += ((CourseRequest) r).getMinPenalty();
467                    } else if (alt > 0) {
468                        if (r instanceof CourseRequest)
469                            bound += ((CourseRequest) r).getMinPenalty();
470                        alt--;
471                    }
472                }
473            }
474            return bound;
475        }
476
477        /** Save the current schedule as the best */
478        public void saveBest() {
479            if (iBestAssignment == null)
480                iBestAssignment = new Enrollment[iAssignment.length];
481            for (int i = 0; i < iAssignment.length; i++)
482                iBestAssignment[i] = iAssignment[i];
483            if (iMinimizePenalty)
484                iBestValue = getPenalty();
485            else
486                iBestValue = getValue();
487        }
488        
489        /** True if the enrollment is conflicting 
490         * @param idx index of request
491         * @param enrollment enrollment in question
492         * @return true if there is a conflict with previous enrollments 
493         **/
494        public boolean inConflict(final int idx, final Enrollment enrollment) {
495            for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints())
496                if (constraint.inConflict(iCurrentAssignment, enrollment))
497                    return true;
498            for (LinkedSections linkedSections: iStudent.getLinkedSections()) {
499                if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() {
500                    @Override
501                    public Enrollment getEnrollment(Request request, int index) {
502                        return (index == idx ? enrollment : iAssignment[index]);
503                    }
504                }) != null) return true;
505            }
506            for (int i = 0; i < iAssignment.length; i++)
507                if (iAssignment[i] != null && i != idx && iAssignment[i].isOverlapping(enrollment))
508                    return true;
509            return false;
510        }
511
512        /** First conflicting enrollment 
513         * @param idx index of request
514         * @param enrollment enrollment in question
515         * @return first conflicting enrollment 
516         **/
517        public Enrollment firstConflict(int idx, Enrollment enrollment) {
518            Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(iCurrentAssignment, enrollment);
519            if (conflicts.contains(enrollment))
520                return enrollment;
521            if (!conflicts.isEmpty()) {
522                for (Enrollment conflict : conflicts) {
523                    if (!conflict.getStudent().equals(iStudent))
524                        return conflict;
525                }
526            }
527            for (int i = 0; i < iAssignment.length; i++) {
528                if (iAssignment[i] == null || i == idx)
529                    continue;
530                if (iAssignment[i].isOverlapping(enrollment))
531                    return iAssignment[i];
532            }
533            return null;
534        }
535
536        /** True if the given request can be assigned 
537         * @param request given request
538         * @param idx index of request
539         * @return true if can be assigned
540         **/
541        public boolean canAssign(Request request, int idx) {
542            if (!request.isAlternative() || iAssignment[idx] != null)
543                return true;
544            int alt = 0;
545            int i = 0;
546            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
547                Request r = e.next();
548                if (r.equals(request))
549                    continue;
550                if (r.isAlternative()) {
551                    if (iAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
552                        alt--;
553                } else {
554                    if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iAssignment[i] == null)
555                        alt++;
556                }
557            }
558            return (alt > 0);
559        }
560
561        /** Number of assigned requests in the current schedule 
562         * @return number of assigned requests
563         **/
564        public int getNrAssigned() {
565            int assigned = 0;
566            for (int i = 0; i < iAssignment.length; i++)
567                if (iAssignment[i] != null)
568                    assigned += (iAssignment[i].isCourseRequest() ? 10 : 1);
569            return assigned;
570        }
571
572        /** Returns true if the given request can be left unassigned 
573         * @param request given request
574         * @return true if can be left unassigned
575         **/
576        protected boolean canLeaveUnassigned(Request request) {
577            return true;
578        }
579        
580        /** Returns list of available enrollments for a course request 
581         * @param request given request
582         * @return list of enrollments to consider
583         **/
584        protected List<Enrollment> values(final CourseRequest request) {
585            List<Enrollment> values = request.getAvaiableEnrollments(iCurrentAssignment);
586            Collections.sort(values, new Comparator<Enrollment>() {
587                
588                private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
589                
590                private Double value(Enrollment e) {
591                    Double value = iValues.get(e);
592                    if (value == null) {
593                        value = iModel.getStudentWeights().getWeight(iCurrentAssignment, e,
594                                        (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)),
595                                        (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().freeTimeConflicts(e)));
596                        iValues.put(e, value);       
597                    }
598                    return value;
599                }
600                
601                @Override
602                public int compare(Enrollment e1, Enrollment e2) {
603                    if (e1.equals(iCurrentAssignment.getValue(request))) return -1;
604                    if (e2.equals(iCurrentAssignment.getValue(request))) return 1;
605                    Double v1 = value(e1), v2 = value(e2);
606                    return v1.equals(v2) ? e1.compareTo(iCurrentAssignment, e2) : v2.compareTo(v1);
607                }
608                
609            });
610            return values;
611        }
612
613        /** branch &amp; bound search 
614         * @param idx index of request
615         **/
616        public void backTrack(int idx) {
617            if (sDebug)
618                sLog.debug("backTrack(" + getNrAssigned() + "/" + getValue() + "," + idx + ")");
619            if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
620                if (sDebug)
621                    sLog.debug("  -- timeout reached");
622                iTimeoutReached = true;
623                return;
624            }
625            if (iMinimizePenalty) {
626                if (getBestAssignment() != null
627                        && (getNrAssignedBound(idx) < getBestNrAssigned() || (getNrAssignedBound(idx) == getBestNrAssigned() && getPenaltyBound(idx) >= getBestValue()))) {
628                    if (sDebug)
629                        sLog.debug("  -- branch number of assigned " + getNrAssignedBound(idx) + "<"
630                                + getBestNrAssigned() + ", or penalty " + getPenaltyBound(idx) + ">=" + getBestValue());
631                    return;
632                }
633                if (idx == iAssignment.length) {
634                    if (getBestAssignment() == null
635                            || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) {
636                        if (sDebug)
637                            sLog.debug("  -- best solution found " + getNrAssigned() + "/" + getPenalty());
638                        saveBest();
639                    }
640                    return;
641                }
642            } else {
643                if (getBestAssignment() != null && getBound(idx) >= getBestValue()) {
644                    if (sDebug)
645                        sLog.debug("  -- branch " + getBound(idx) + " >= " + getBestValue());
646                    return;
647                }
648                if (idx == iAssignment.length) {
649                    if (getBestAssignment() == null || getValue() < getBestValue()) {
650                        if (sDebug)
651                            sLog.debug("  -- best solution found " + getNrAssigned() + "/" + getValue());
652                        saveBest();
653                    }
654                    return;
655                }
656            }
657
658            Request request = iStudent.getRequests().get(idx);
659            if (sDebug)
660                sLog.debug("  -- request: " + request);
661            if (!canAssign(request, idx)) {
662                if (sDebug)
663                    sLog.debug("    -- cannot assign");
664                backTrack(idx + 1);
665                return;
666            }
667            List<Enrollment> values = null;
668            if (request instanceof CourseRequest) {
669                CourseRequest courseRequest = (CourseRequest) request;
670                if (courseRequest.getInitialAssignment() != null && iModel.isMPP()) {
671                    Enrollment enrollment = courseRequest.getInitialAssignment();
672                    if (!inConflict(idx, enrollment)) {
673                        iAssignment[idx] = enrollment;
674                        backTrack(idx + 1);
675                        iAssignment[idx] = null;
676                        return;
677                    }
678                }
679                if (!courseRequest.getSelectedChoices().isEmpty()) {
680                    if (sDebug)
681                        sLog.debug("    -- selection among selected enrollments");
682                    values = courseRequest.getSelectedEnrollments(iCurrentAssignment, true);
683                    if (values != null && !values.isEmpty()) {
684                        boolean hasNoConflictValue = false;
685                        for (Enrollment enrollment : values) {
686                            if (inConflict(idx, enrollment))
687                                continue;
688                            hasNoConflictValue = true;
689                            if (sDebug)
690                                sLog.debug("      -- nonconflicting enrollment found: " + enrollment);
691                            iAssignment[idx] = enrollment;
692                            backTrack(idx + 1);
693                            iAssignment[idx] = null;
694                        }
695                        if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict)
696                            return;
697                    }
698                }
699                values = iValues.get(courseRequest);
700                if (values == null) {
701                    values = values(courseRequest);
702                    iValues.put(courseRequest, values);
703                }
704            } else {
705                values = request.computeEnrollments(iCurrentAssignment);
706            }
707            if (sDebug) {
708                sLog.debug("  -- nrValues: " + values.size());
709                int vIdx = 1;
710                for (Enrollment enrollment : values) {
711                    if (sDebug)
712                        sLog.debug("    -- [" + vIdx + "]: " + enrollment);
713                }
714            }
715            boolean hasNoConflictValue = false;
716            for (Enrollment enrollment : values) {
717                if (sDebug)
718                    sLog.debug("    -- enrollment: " + enrollment);
719                if (sDebug) {
720                    Enrollment conflict = firstConflict(idx, enrollment);
721                    if (conflict != null) {
722                        sLog.debug("        -- in conflict with: " + conflict);
723                        continue;
724                    }
725                } else {
726                    if (inConflict(idx, enrollment)) continue;
727                }
728                hasNoConflictValue = true;
729                iAssignment[idx] = enrollment;
730                backTrack(idx + 1);
731                iAssignment[idx] = null;
732            }
733            if (canLeaveUnassigned(request) && (!hasNoConflictValue || request instanceof CourseRequest))
734                backTrack(idx + 1);
735        }
736    }
737
738    /** Branch &amp; bound neighbour -- a schedule of a student */
739    public static class BranchBoundNeighbour implements Neighbour<Request, Enrollment> {
740        private double iValue;
741        private Enrollment[] iAssignment;
742        private Student iStudent;
743
744        /**
745         * Constructor
746         * 
747         * @param student selected student
748         * @param value
749         *            value of the schedule
750         * @param assignment
751         *            enrollments of student's requests
752         */
753        public BranchBoundNeighbour(Student student, double value, Enrollment[] assignment) {
754            iValue = value;
755            iAssignment = assignment;
756            iStudent = student;
757        }
758
759        @Override
760        public double value(Assignment<Request, Enrollment> assignment) {
761            return iValue;
762        }
763
764        /** Assignment 
765         * @return an enrollment for each request of the student
766         **/
767        public Enrollment[] getAssignment() {
768            return iAssignment;
769        }
770        
771        /** Student 
772         * @return selected student
773         **/
774        public Student getStudent() {
775            return iStudent;
776        }
777
778        /** Assign the schedule */
779        @Override
780        public void assign(Assignment<Request, Enrollment> assignment, long iteration) {
781            for (Request r: iStudent.getRequests())
782                assignment.unassign(iteration, r);
783            for (int i = 0; i < iAssignment.length; i++)
784                if (iAssignment[i] != null)
785                    assignment.assign(iteration, iAssignment[i]);
786        }
787
788        @Override
789        public String toString() {
790            StringBuffer sb = new StringBuffer("B&B{ " + iStudent + " " + sDF.format(-iValue * 100.0) + "%");
791            int idx = 0;
792            for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); idx++) {
793                Request request = e.next();
794                sb.append("\n  " + request);
795                Enrollment enrollment = iAssignment[idx];
796                if (enrollment == null)
797                    sb.append("  -- not assigned");
798                else
799                    sb.append("  -- " + enrollment);
800            }
801            sb.append("\n}");
802            return sb.toString();
803        }
804
805        @Override
806        public Map<Request, Enrollment> assignments() {
807            Map<Request, Enrollment> ret = new HashMap<Request, Enrollment>();
808            for (int i = 0; i < iAssignment.length; i++)
809                ret.put(iStudent.getRequests().get(i), iAssignment[i]);
810            return ret;
811        }
812
813    }
814}