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    protected boolean iBranchWhenSelectedHasNoConflict = false;
061
062    /** Student */
063    protected Student iStudent;
064    /** Start time */
065    protected long iT0;
066    /** End time */
067    protected long iT1;
068    /** Was timeout reached */
069    protected boolean iTimeoutReached;
070    /** Current assignment */
071    protected Enrollment[] iCurrentAssignment;
072    /** Best assignment */
073    protected Enrollment[] iBestAssignment;
074    /** Value cache */
075    protected HashMap<CourseRequest, List<Enrollment>> iValues;
076
077    private Set<FreeTimeRequest> iRequiredFreeTimes;
078    private Hashtable<CourseRequest, Set<Section>> iPreferredSections;
079    private Hashtable<CourseRequest, Config> iRequiredConfig = new Hashtable<CourseRequest, Config>();
080    private Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>();
081
082    public MultiCriteriaBranchAndBoundSelection(DataProperties config) {
083        iTimeout = config.getPropertyInt("Neighbour.BranchAndBoundTimeout", iTimeout);
084        iPriorityWeighting = config.getPropertyBoolean("StudentWeights.PriorityWeighting", iPriorityWeighting);
085        iBranchWhenSelectedHasNoConflict = config.getPropertyBoolean("Students.BranchWhenSelectedHasNoConflict", iBranchWhenSelectedHasNoConflict);
086    }
087
088    @Override
089    public void setModel(OnlineSectioningModel model) {
090        iModel = model;
091    }
092
093    @Override
094    public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) {
095        iPreferredSections = preferredSections;
096    }
097
098    public void setTimeout(int timeout) {
099        iTimeout = timeout;
100    }
101
102    @Override
103    public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) {
104        if (requiredSections != null) {
105            for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) {
106                Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>();
107                iRequiredSection.put(entry.getKey(), subSection);
108                for (Section section : entry.getValue()) {
109                    if (subSection.isEmpty())
110                        iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig());
111                    subSection.put(section.getSubpart(), section);
112                }
113            }
114        }
115    }
116
117    @Override
118    public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) {
119        iRequiredFreeTimes = requiredFreeTimes;
120    }
121
122    public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student,
123            SelectionCriterion comparator) {
124        iStudent = student;
125        iComparator = comparator;
126        iAssignment = assignment;
127        return select();
128    }
129
130    @Override
131    public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) {
132        SelectionCriterion comparator = null;
133        if (iPriorityWeighting)
134            comparator = new OnlineSectioningCriterion(student, iModel, assignment, iPreferredSections);
135        else
136            comparator = new EqualWeightCriterion(student, iModel, assignment, iPreferredSections);
137        return select(assignment, student, comparator);
138    }
139
140    /**
141     * Execute branch & bound, return the best found schedule for the selected
142     * student.
143     */
144    public BranchBoundNeighbour select() {
145        iT0 = JProf.currentTimeMillis();
146        iTimeoutReached = false;
147        iCurrentAssignment = new Enrollment[iStudent.getRequests().size()];
148        iBestAssignment = null;
149
150        int i = 0;
151        for (Request r : iStudent.getRequests())
152            iCurrentAssignment[i++] = iAssignment.getValue(r);
153        saveBest();
154        for (int j = 0; j < iCurrentAssignment.length; j++)
155            iCurrentAssignment[j] = null;
156
157        iValues = new HashMap<CourseRequest, List<Enrollment>>();
158        backTrack(0);
159        iT1 = JProf.currentTimeMillis();
160        if (iBestAssignment == null)
161            return null;
162
163        return new BranchBoundNeighbour(iStudent, iComparator.getTotalWeight(iAssignment, iBestAssignment),
164                iBestAssignment);
165    }
166
167    /** Was timeout reached */
168    public boolean isTimeoutReached() {
169        return iTimeoutReached;
170    }
171
172    /** Time (in milliseconds) the branch & bound did run */
173    public long getTime() {
174        return iT1 - iT0;
175    }
176
177    /** Save the current schedule as the best */
178    public void saveBest() {
179        if (iBestAssignment == null)
180            iBestAssignment = new Enrollment[iCurrentAssignment.length];
181        for (int i = 0; i < iCurrentAssignment.length; i++)
182            iBestAssignment[i] = iCurrentAssignment[i];
183    }
184
185    /** True if the enrollment is conflicting */
186    public boolean inConflict(final int idx, final Enrollment enrollment) {
187        for (GlobalConstraint<Request, Enrollment> constraint : enrollment.variable().getModel().globalConstraints())
188            if (constraint.inConflict(iAssignment, enrollment))
189                return true;
190        for (LinkedSections linkedSections : iStudent.getLinkedSections()) {
191            if (linkedSections.inConflict(enrollment, new LinkedSections.EnrollmentAssignment() {
192                @Override
193                public Enrollment getEnrollment(Request request, int index) {
194                    return (index == idx ? enrollment : iCurrentAssignment[index]);
195                }
196            }) != null)
197                return true;
198        }
199        for (int i = 0; i < iCurrentAssignment.length; i++)
200            if (iCurrentAssignment[i] != null && i != idx && iCurrentAssignment[i].isOverlapping(enrollment))
201                return true;
202        return !isAllowed(idx, enrollment);
203    }
204
205    /** True if the given request can be assigned */
206    public boolean canAssign(Request request, int idx) {
207        if (!request.isAlternative() || iCurrentAssignment[idx] != null)
208            return true;
209        int alt = 0;
210        int i = 0;
211        for (Iterator<Request> e = iStudent.getRequests().iterator(); e.hasNext(); i++) {
212            Request r = e.next();
213            if (r.equals(request))
214                continue;
215            if (r.isAlternative()) {
216                if (iCurrentAssignment[i] != null || (r instanceof CourseRequest && ((CourseRequest) r).isWaitlist()))
217                    alt--;
218            } else {
219                if (r instanceof CourseRequest && !((CourseRequest) r).isWaitlist() && iCurrentAssignment[i] == null)
220                    alt++;
221            }
222        }
223        return (alt > 0);
224    }
225
226    public boolean isAllowed(int idx, Enrollment enrollment) {
227        if (enrollment.isCourseRequest()) {
228            CourseRequest request = (CourseRequest) enrollment.getRequest();
229            Config reqConfig = iRequiredConfig.get(request);
230            if (reqConfig != null) {
231                if (!reqConfig.equals(enrollment.getConfig()))
232                    return false;
233                Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request);
234                for (Section section : enrollment.getSections()) {
235                    Section reqSection = reqSections.get(section.getSubpart());
236                    if (reqSection == null)
237                        continue;
238                    if (!section.equals(reqSection))
239                        return false;
240                }
241            }
242        } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) {
243            if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
244                return false;
245        }
246        return true;
247    }
248
249    /** Returns true if the given request can be left unassigned */
250    protected boolean canLeaveUnassigned(Request request) {
251        if (request instanceof CourseRequest) {
252            if (iRequiredConfig.get(request) != null)
253                return false;
254        } else if (iRequiredFreeTimes.contains(request))
255            return false;
256        return true;
257    }
258
259    /** Returns list of available enrollments for a course request */
260    protected List<Enrollment> values(final CourseRequest request) {
261        List<Enrollment> values = request.getAvaiableEnrollments(iAssignment);
262        Collections.sort(values, new Comparator<Enrollment>() {
263            @Override
264            public int compare(Enrollment o1, Enrollment o2) {
265                return iComparator.compare(iAssignment, o1, o2);
266            }
267        });
268        return values;
269    }
270
271    /** branch & bound search */
272    public void backTrack(int idx) {
273        if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
274            iTimeoutReached = true;
275            return;
276        }
277        if (idx == iCurrentAssignment.length) {
278            if (iBestAssignment == null || iComparator.compare(iAssignment, iCurrentAssignment, iBestAssignment) < 0)
279                saveBest();
280            return;
281        } else if (iBestAssignment != null
282                && !iComparator.canImprove(iAssignment, idx, iCurrentAssignment, iBestAssignment)) {
283            return;
284        }
285
286        Request request = iStudent.getRequests().get(idx);
287        if (!canAssign(request, idx)) {
288            backTrack(idx + 1);
289            return;
290        }
291
292        List<Enrollment> values = null;
293        if (request instanceof CourseRequest) {
294            CourseRequest courseRequest = (CourseRequest) request;
295            if (!courseRequest.getSelectedChoices().isEmpty()) {
296                values = courseRequest.getSelectedEnrollments(iAssignment, true);
297                if (values != null && !values.isEmpty()) {
298                    boolean hasNoConflictValue = false;
299                    for (Enrollment enrollment : values) {
300                        if (inConflict(idx, enrollment))
301                            continue;
302                        hasNoConflictValue = true;
303                        iCurrentAssignment[idx] = enrollment;
304                        backTrack(idx + 1);
305                        iCurrentAssignment[idx] = null;
306                    }
307                    if (hasNoConflictValue && iBranchWhenSelectedHasNoConflict)
308                        return;
309                }
310            }
311            values = iValues.get(courseRequest);
312            if (values == null) {
313                values = values(courseRequest);
314                iValues.put(courseRequest, values);
315            }
316        } else {
317            values = request.computeEnrollments(iAssignment);
318        }
319
320        boolean hasNoConflictValue = false;
321        for (Enrollment enrollment : values) {
322            if (inConflict(idx, enrollment))
323                continue;
324            hasNoConflictValue = true;
325            iCurrentAssignment[idx] = enrollment;
326            backTrack(idx + 1);
327            iCurrentAssignment[idx] = null;
328        }
329
330        if (canLeaveUnassigned(request) || (!hasNoConflictValue && request instanceof CourseRequest))
331            backTrack(idx + 1);
332    }
333
334    /**
335     * Enrollment comparator
336     */
337    public interface SelectionComparator {
338        /**
339         * Compare two enrollments
340         * 
341         * @param assignment
342         *            current assignment
343         * @param e1
344         *            first enrollment
345         * @param e2
346         *            second enrollment
347         * @return -1 if the first enrollment is better than the second etc.
348         */
349        public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2);
350    }
351
352    /**
353     * Multi-criteria selection interface.
354     */
355    public interface SelectionCriterion extends SelectionComparator {
356        /**
357         * Compare two solutions
358         * 
359         * @param assignment
360         *            current assignment
361         * @param current
362         *            current solution
363         * @param best
364         *            best known solution
365         * @return true if current solution is better than the best one
366         */
367        public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best);
368
369        /**
370         * Bound
371         * 
372         * @param assignment
373         *            current assignment
374         * @param idx
375         *            current request index
376         * @param current
377         *            current solution
378         * @param best
379         *            best known solution
380         * @return if the current solution can be extended and possibly improve
381         *         upon the best known solution
382         */
383        public boolean canImprove(Assignment<Request, Enrollment> assignment, int idx, Enrollment[] current,
384                Enrollment[] best);
385
386        /**
387         * For backward compatibility, return a weighted sum
388         * 
389         * @param assignment
390         *            current assignment
391         * @param enrollments
392         *            current solution
393         * @return solution weight (weighted sum)
394         */
395        public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollments);
396    }
397}