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