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 Tomas Muller<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        for (int i = 0; i < iCurrentAssignment.length; i++)
203            if (iCurrentAssignment[i] != null && i != idx && iCurrentAssignment[i].isOverlapping(enrollment))
204                return true;
205        if (iMaxOverExpected >= 0.0) {
206            double penalty = 0.0;
207            for (int i = 0; i < idx; i++) {
208                if (iCurrentAssignment[i] != null && iCurrentAssignment[i].getAssignments() != null && iCurrentAssignment[i].isCourseRequest())
209                    for (Section section: iCurrentAssignment[i].getSections())
210                        penalty += iModel.getOverExpected(iAssignment, iCurrentAssignment, i, section, iCurrentAssignment[i].getRequest());
211            }
212            if (enrollment.isCourseRequest())
213                for (Section section: enrollment.getSections())
214                    penalty += iModel.getOverExpected(iAssignment, iCurrentAssignment, idx, section, enrollment.getRequest());
215            if (penalty > iMaxOverExpected) return true;
216        }
217        return !isAllowed(idx, enrollment);
218    }
219
220    /** True if the given request can be assigned */
221    public boolean canAssign(Request request, int idx) {
222        if (!request.isAlternative() || iCurrentAssignment[idx] != null)
223            return true;
224        int alt = 0;
225        int i = 0;
226        for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
227            Request r = e.next();
228            if (r.equals(request))
229                continue;
230            if (r.isAlternative()) {
231                if (iCurrentAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
232                    alt--;
233            } else {
234                if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iCurrentAssignment[i] == null)
235                    alt++;
236            }
237        }
238        return (alt > 0);
239    }
240
241    public boolean isAllowed(int idx, Enrollment enrollment) {
242        if (enrollment.isCourseRequest()) {
243            CourseRequest request = (CourseRequest) enrollment.getRequest();
244            if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false;
245            Config reqConfig = iRequiredConfig.get(request);
246            if (reqConfig != null) {
247                if (!reqConfig.equals(enrollment.getConfig()))
248                    return false;
249                Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request);
250                for (Section section : enrollment.getSections()) {
251                    Section reqSection = reqSections.get(section.getSubpart());
252                    if (reqSection == null)
253                        continue;
254                    if (!section.equals(reqSection))
255                        return false;
256                }
257            }
258        } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) {
259            if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
260                return false;
261        }
262        return true;
263    }
264
265    /** Returns true if the given request can be left unassigned */
266    protected boolean canLeaveUnassigned(Request request) {
267        if (request instanceof CourseRequest) {
268            if (iRequiredConfig.get(request) != null)
269                return false;
270        } else if (iRequiredFreeTimes.contains(request))
271            return false;
272        return true;
273    }
274
275    /** Returns list of available enrollments for a course request */
276    protected List<Enrollment> values(final CourseRequest request) {
277        if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request))
278            return new ArrayList<Enrollment>();
279        List<Enrollment> values = request.getAvaiableEnrollments(iAssignment);
280        Collections.sort(values, new Comparator<Enrollment>() {
281            @Override
282            public int compare(Enrollment o1, Enrollment o2) {
283                return iComparator.compare(iAssignment, o1, o2);
284            }
285        });
286        return values;
287    }
288
289    /** branch & bound search */
290    public void backTrack(int idx) {
291        if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
292            iTimeoutReached = true;
293            return;
294        }
295        if (idx == iCurrentAssignment.length) {
296            if (iBestAssignment == null || iComparator.compare(iAssignment, iCurrentAssignment, iBestAssignment) < 0)
297                saveBest();
298            return;
299        } else if (iBestAssignment != null
300                && !iComparator.canImprove(iAssignment, idx, iCurrentAssignment, iBestAssignment)) {
301            return;
302        }
303
304        Request request = iStudent.getRequests().get(idx);
305        if (!canAssign(request, idx)) {
306            backTrack(idx + 1);
307            return;
308        }
309
310        List<Enrollment> values = null;
311        if (request instanceof CourseRequest) {
312            CourseRequest courseRequest = (CourseRequest) request;
313            if (!courseRequest.getSelectedChoices().isEmpty()) {
314                values = courseRequest.getSelectedEnrollments(iAssignment, true);
315                if (values != null && !values.isEmpty()) {
316                    boolean hasNoConflictValue = false;
317                    for (Enrollment enrollment : values) {
318                        if (inConflict(idx, enrollment))
319                            continue;
320                        hasNoConflictValue = true;
321                        iCurrentAssignment[idx] = enrollment;
322                        backTrack(idx + 1);
323                        iCurrentAssignment[idx] = null;
324                    }
325                    if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict)
326                        return;
327                }
328            }
329            values = iValues.get(courseRequest);
330            if (values == null) {
331                values = values(courseRequest);
332                iValues.put(courseRequest, values);
333            }
334        } else {
335            values = request.computeEnrollments(iAssignment);
336        }
337
338        boolean hasNoConflictValue = false;
339        for (Enrollment enrollment : values) {
340            if (inConflict(idx, enrollment))
341                continue;
342            hasNoConflictValue = true;
343            iCurrentAssignment[idx] = enrollment;
344            backTrack(idx + 1);
345            iCurrentAssignment[idx] = null;
346        }
347
348        if (canLeaveUnassigned(request) || (!hasNoConflictValue && request instanceof CourseRequest))
349            backTrack(idx + 1);
350    }
351
352    /**
353     * Enrollment comparator
354     */
355    public interface SelectionComparator {
356        /**
357         * Compare two enrollments
358         * 
359         * @param assignment
360         *            current assignment
361         * @param e1
362         *            first enrollment
363         * @param e2
364         *            second enrollment
365         * @return -1 if the first enrollment is better than the second etc.
366         */
367        public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2);
368    }
369
370    /**
371     * Multi-criteria selection interface.
372     */
373    public interface SelectionCriterion extends SelectionComparator {
374        /**
375         * Compare two solutions
376         * 
377         * @param assignment
378         *            current assignment
379         * @param current
380         *            current solution
381         * @param best
382         *            best known solution
383         * @return true if current solution is better than the best one
384         */
385        public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best);
386
387        /**
388         * Bound
389         * 
390         * @param assignment
391         *            current assignment
392         * @param idx
393         *            current request index
394         * @param current
395         *            current solution
396         * @param best
397         *            best known solution
398         * @return if the current solution can be extended and possibly improve
399         *         upon the best known solution
400         */
401        public boolean canImprove(Assignment<Request, Enrollment> assignment, int idx, Enrollment[] current,
402                Enrollment[] best);
403
404        /**
405         * For backward compatibility, return a weighted sum
406         * 
407         * @param assignment
408         *            current assignment
409         * @param enrollments
410         *            current solution
411         * @return solution weight (weighted sum)
412         */
413        public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments);
414    }
415
416    @Override
417    public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) {
418        iRequiredUnassinged = requiredUnassignedRequests;
419    }
420
421    @Override
422    public void setMaxOverExpected(double maxOverExpected) {
423        iMaxOverExpected = maxOverExpected;
424    }
425}