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