    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}