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