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