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