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