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