001package org.cpsolver.studentsct.online.selection;
002
003import java.util.ArrayList;
004import java.util.Collections;
005import java.util.Comparator;
006import java.util.HashMap;
007import java.util.Hashtable;
008import java.util.Iterator;
009import java.util.List;
010import java.util.Map;
011import java.util.Set;
012
013import org.cpsolver.ifs.assignment.Assignment;
014import org.cpsolver.ifs.model.GlobalConstraint;
015import org.cpsolver.ifs.util.DataProperties;
016import org.cpsolver.ifs.util.JProf;
017import org.cpsolver.studentsct.constraint.LinkedSections;
018import org.cpsolver.studentsct.heuristics.selection.OnlineSelection;
019import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour;
020import org.cpsolver.studentsct.model.Config;
021import org.cpsolver.studentsct.model.CourseRequest;
022import org.cpsolver.studentsct.model.Enrollment;
023import org.cpsolver.studentsct.model.FreeTimeRequest;
024import org.cpsolver.studentsct.model.Request;
025import org.cpsolver.studentsct.model.Section;
026import org.cpsolver.studentsct.model.Student;
027import org.cpsolver.studentsct.model.Subpart;
028import org.cpsolver.studentsct.online.OnlineSectioningModel;
029
030/**
031 * Online student sectioning algorithm using multi-criteria selection. It is very
032 * similar to the {@link SuggestionSelection}, however, the {link {@link OnlineSelection}
033 * is used to compare two solutions and for branching.
034 * 
035 * @version StudentSct 1.3 (Student Sectioning)<br>
036 *          Copyright (C) 2014 Tomáš Müller<br>
037 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
038 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
039 * <br>
040 *          This library is free software; you can redistribute it and/or modify
041 *          it under the terms of the GNU Lesser General Public License as
042 *          published by the Free Software Foundation; either version 3 of the
043 *          License, or (at your option) any later version. <br>
044 * <br>
045 *          This library is distributed in the hope that it will be useful, but
046 *          WITHOUT ANY WARRANTY; without even the implied warranty of
047 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
048 *          Lesser General Public License for more details. <br>
049 * <br>
050 *          You should have received a copy of the GNU Lesser General Public
051 *          License along with this library; if not see <a
052 *          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
053 * 
054 */
055public class MultiCriteriaBranchAndBoundSelection implements OnlineSectioningSelection {
056    protected int iTimeout = 1000;
057    protected OnlineSectioningModel iModel = null;
058    protected Assignment<Request, Enrollment> iAssignment = null;
059    protected SelectionCriterion iComparator = null;
060    private boolean iPriorityWeighting = true;
061    protected boolean iBranchWhenSelectedHasNoConflict = false;
062    private double iMaxOverExpected = -1.0;
063
064    /** Student */
065    protected Student iStudent;
066    /** Start time */
067    protected long iT0;
068    /** End time */
069    protected long iT1;
070    /** Was timeout reached */
071    protected boolean iTimeoutReached;
072    /** Current assignment */
073    protected Enrollment[] iCurrentAssignment;
074    /** Best assignment */
075    protected Enrollment[] iBestAssignment;
076    /** Value cache */
077    protected HashMap<CourseRequest, List<Enrollment>> iValues;
078
079    private Set<FreeTimeRequest> iRequiredFreeTimes;
080    private Hashtable<CourseRequest, Set<Section>> iPreferredSections;
081    private Hashtable<CourseRequest, Config> iRequiredConfig = new Hashtable<CourseRequest, Config>();
082    private Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>();
083    private Set<CourseRequest> iRequiredUnassinged = null;
084
085    public MultiCriteriaBranchAndBoundSelection(DataProperties config) {
086        iTimeout = config.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout);
087        iPriorityWeighting = config.getPropertyBoolean("StudentWeights.PriorityWeighting", iPriorityWeighting);
088        iBranchWhenSelectedHasNoConflict = config.getPropertyBoolean("Students.BranchWhenSelectedHasNoConflict", iBranchWhenSelectedHasNoConflict);
089    }
090
091    @Override
092    public void setModel(OnlineSectioningModel model) {
093        iModel = model;
094    }
095
096    @Override
097    public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) {
098        iPreferredSections = preferredSections;
099    }
100
101    public void setTimeout(int timeout) {
102        iTimeout = timeout;
103    }
104
105    @Override
106    public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) {
107        if (requiredSections != null) {
108            for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) {
109                Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>();
110                iRequiredSection.put(entry.getKey(), subSection);
111                for (Section section : entry.getValue()) {
112                    if (subSection.isEmpty())
113                        iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig());
114                    subSection.put(section.getSubpart(), section);
115                }
116            }
117        }
118    }
119
120    @Override
121    public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) {
122        iRequiredFreeTimes = requiredFreeTimes;
123    }
124
125    public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student,
126            SelectionCriterion comparator) {
127        iStudent = student;
128        iComparator = comparator;
129        iAssignment = assignment;
130        return select();
131    }
132
133    @Override
134    public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) {
135        SelectionCriterion comparator = null;
136        if (iPriorityWeighting)
137            comparator = new OnlineSectioningCriterion(student, iModel, assignment, iPreferredSections);
138        else
139            comparator = new EqualWeightCriterion(student, iModel, assignment, iPreferredSections);
140        return select(assignment, student, comparator);
141    }
142
143    /**
144     * Execute branch & bound, return the best found schedule for the selected
145     * student.
146     */
147    public BranchBoundNeighbour select() {
148        iT0 = JProf.currentTimeMillis();
149        iTimeoutReached = false;
150        iCurrentAssignment = new Enrollment[iStudent.getRequests().size()];
151        iBestAssignment = null;
152
153        int i = 0;
154        for (Request r : iStudent.getRequests())
155            iCurrentAssignment[i++] = iAssignment.getValue(r);
156        saveBest();
157        for (int j = 0; j < iCurrentAssignment.length; j++)
158            iCurrentAssignment[j] = null;
159
160        iValues = new HashMap<CourseRequest, List<Enrollment>>();
161        backTrack(0);
162        iT1 = JProf.currentTimeMillis();
163        if (iBestAssignment == null)
164            return null;
165
166        return new BranchBoundNeighbour(iStudent, iComparator.getTotalWeight(iAssignment, iBestAssignment),
167                iBestAssignment);
168    }
169
170    /** Was timeout reached */
171    public boolean isTimeoutReached() {
172        return iTimeoutReached;
173    }
174
175    /** Time (in milliseconds) the branch & bound did run */
176    public long getTime() {
177        return iT1 - iT0;
178    }
179
180    /** Save the current schedule as the best */
181    public void saveBest() {
182        if (iBestAssignment == null)
183            iBestAssignment = new Enrollment[iCurrentAssignment.length];
184        for (int i = 0; i < iCurrentAssignment.length; i++)
185            iBestAssignment[i] = iCurrentAssignment[i];
186    }
187
188    /** True if the enrollment is conflicting */
189    public boolean inConflict(final int idx, final Enrollment enrollment) {
190        for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints())
191            if (constraint.inConflict(iAssignment, enrollment))
192                return true;
193        for (LinkedSections linkedSections : iStudent.getLinkedSections()) {
194            if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() {
195                @Override
196                public Enrollment getEnrollment(Request request, int index) {
197                    return (index == idx ? enrollment : iCurrentAssignment[index]);
198                }
199            }) != null)
200                return true;
201        }
202        float credit = enrollment.getCredit();
203        for (int i = 0; i < iCurrentAssignment.length; i++) {
204            if (iCurrentAssignment[i] != null && i != idx) {
205                credit += iCurrentAssignment[i].getCredit();
206                if (credit > iStudent.getMaxCredit() || iCurrentAssignment[i].isOverlapping(enrollment))
207                    return true;
208            }
209        }
210        if (iMaxOverExpected >= 0.0) {
211            double penalty = 0.0;
212            for (int i = 0; i < idx; i++) {
213                if (iCurrentAssignment[i] != null && iCurrentAssignment[i].getAssignments() != null && iCurrentAssignment[i].isCourseRequest())
214                    for (Section section: iCurrentAssignment[i].getSections())
215                        penalty += iModel.getOverExpected(iAssignment, iCurrentAssignment, i, section, iCurrentAssignment[i].getRequest());
216            }
217            if (enrollment.isCourseRequest())
218                for (Section section: enrollment.getSections())
219                    penalty += iModel.getOverExpected(iAssignment, iCurrentAssignment, idx, section, enrollment.getRequest());
220            if (penalty > iMaxOverExpected) return true;
221        }
222        return !isAllowed(idx, enrollment);
223    }
224
225    /** True if the given request can be assigned */
226    public boolean canAssign(Request request, int idx) {
227        if (iCurrentAssignment[idx] != null)
228            return true;
229        int alt = 0;
230        int i = 0;
231        float credit = 0;
232        for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
233            Request r = e.next();
234            if (r.equals(request))
235                credit += r.getMinCredit();
236            else if (iCurrentAssignment[i] != null)
237                credit += iCurrentAssignment[i].getCredit();
238            if (r.equals(request))
239                continue;
240            if (r.isAlternative()) {
241                if (iCurrentAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
242                    alt--;
243            } else {
244                if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iCurrentAssignment[i] == null)
245                    alt++;
246            }
247        }
248        return (!request.isAlternative() || alt > 0) && (credit <= request.getStudent().getMaxCredit());
249    }
250
251    public boolean isAllowed(int idx, Enrollment enrollment) {
252        if (enrollment.isCourseRequest()) {
253            CourseRequest request = (CourseRequest) enrollment.getRequest();
254            if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false;
255            Config reqConfig = iRequiredConfig.get(request);
256            if (reqConfig != null) {
257                if (!reqConfig.equals(enrollment.getConfig()))
258                    return false;
259                Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request);
260                for (Section section : enrollment.getSections()) {
261                    Section reqSection = reqSections.get(section.getSubpart());
262                    if (reqSection == null)
263                        continue;
264                    if (!section.equals(reqSection))
265                        return false;
266                }
267            }
268        } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) {
269            if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
270                return false;
271        }
272        return true;
273    }
274
275    /** Returns true if the given request can be left unassigned */
276    protected boolean canLeaveUnassigned(Request request) {
277        if (request instanceof CourseRequest) {
278            if (iRequiredConfig.get(request) != null)
279                return false;
280        } else if (iRequiredFreeTimes.contains(request))
281            return false;
282        return true;
283    }
284
285    /** Returns list of available enrollments for a course request */
286    protected List<Enrollment> values(final CourseRequest request) {
287        if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request))
288            return new ArrayList<Enrollment>();
289        List<Enrollment> values = request.getAvaiableEnrollments(iAssignment);
290        Collections.sort(values, new Comparator<Enrollment>() {
291            @Override
292            public int compare(Enrollment o1, Enrollment o2) {
293                return iComparator.compare(iAssignment, o1, o2);
294            }
295        });
296        return values;
297    }
298
299    /** branch & bound search */
300    public void backTrack(int idx) {
301        if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
302            iTimeoutReached = true;
303            return;
304        }
305        if (idx == iCurrentAssignment.length) {
306            if (iBestAssignment == null || iComparator.compare(iAssignment, iCurrentAssignment, iBestAssignment) < 0)
307                saveBest();
308            return;
309        } else if (iBestAssignment != null
310                && !iComparator.canImprove(iAssignment, idx, iCurrentAssignment, iBestAssignment)) {
311            return;
312        }
313
314        Request request = iStudent.getRequests().get(idx);
315        if (!canAssign(request, idx)) {
316            backTrack(idx + 1);
317            return;
318        }
319
320        List<Enrollment> values = null;
321        if (request instanceof CourseRequest) {
322            CourseRequest courseRequest = (CourseRequest) request;
323            if (!courseRequest.getSelectedChoices().isEmpty()) {
324                values = courseRequest.getSelectedEnrollments(iAssignment, true);
325                if (values != null && !values.isEmpty()) {
326                    boolean hasNoConflictValue = false;
327                    for (Enrollment enrollment : values) {
328                        if (inConflict(idx, enrollment))
329                            continue;
330                        hasNoConflictValue = true;
331                        iCurrentAssignment[idx] = enrollment;
332                        backTrack(idx + 1);
333                        iCurrentAssignment[idx] = null;
334                    }
335                    if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict)
336                        return;
337                }
338            }
339            values = iValues.get(courseRequest);
340            if (values == null) {
341                values = values(courseRequest);
342                iValues.put(courseRequest, values);
343            }
344        } else {
345            values = request.computeEnrollments(iAssignment);
346        }
347
348        boolean hasNoConflictValue = false;
349        for (Enrollment enrollment : values) {
350            if (inConflict(idx, enrollment))
351                continue;
352            hasNoConflictValue = true;
353            iCurrentAssignment[idx] = enrollment;
354            backTrack(idx + 1);
355            iCurrentAssignment[idx] = null;
356        }
357
358        if (canLeaveUnassigned(request) || (!hasNoConflictValue && request instanceof CourseRequest))
359            backTrack(idx + 1);
360    }
361
362    /**
363     * Enrollment comparator
364     */
365    public interface SelectionComparator {
366        /**
367         * Compare two enrollments
368         * 
369         * @param assignment
370         *            current assignment
371         * @param e1
372         *            first enrollment
373         * @param e2
374         *            second enrollment
375         * @return -1 if the first enrollment is better than the second etc.
376         */
377        public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2);
378    }
379
380    /**
381     * Multi-criteria selection interface.
382     */
383    public interface SelectionCriterion extends SelectionComparator {
384        /**
385         * Compare two solutions
386         * 
387         * @param assignment
388         *            current assignment
389         * @param current
390         *            current solution
391         * @param best
392         *            best known solution
393         * @return true if current solution is better than the best one
394         */
395        public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best);
396
397        /**
398         * Bound
399         * 
400         * @param assignment
401         *            current assignment
402         * @param idx
403         *            current request index
404         * @param current
405         *            current solution
406         * @param best
407         *            best known solution
408         * @return if the current solution can be extended and possibly improve
409         *         upon the best known solution
410         */
411        public boolean canImprove(Assignment<Request, Enrollment> assignment, int idx, Enrollment[] current,
412                Enrollment[] best);
413
414        /**
415         * For backward compatibility, return a weighted sum
416         * 
417         * @param assignment
418         *            current assignment
419         * @param enrollments
420         *            current solution
421         * @return solution weight (weighted sum)
422         */
423        public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments);
424    }
425
426    @Override
427    public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) {
428        iRequiredUnassinged = requiredUnassignedRequests;
429    }
430
431    @Override
432    public void setMaxOverExpected(double maxOverExpected) {
433        iMaxOverExpected = maxOverExpected;
434    }
435}