    001package org.cpsolver.studentsct.online.selection;
    002
    003import java.util.ArrayList;
    004import java.util.Hashtable;
    005import java.util.List;
    006import java.util.Map;
    007import java.util.Set;
    008
    009import org.cpsolver.ifs.assignment.Assignment;
    010import org.cpsolver.ifs.util.DataProperties;
    011import org.cpsolver.studentsct.extension.DistanceConflict;
    012import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
    013import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
    014import org.cpsolver.studentsct.model.Config;
    015import org.cpsolver.studentsct.model.CourseRequest;
    016import org.cpsolver.studentsct.model.Enrollment;
    017import org.cpsolver.studentsct.model.FreeTimeRequest;
    018import org.cpsolver.studentsct.model.Request;
    019import org.cpsolver.studentsct.model.Section;
    020import org.cpsolver.studentsct.model.Student;
    021import org.cpsolver.studentsct.model.Subpart;
    022import org.cpsolver.studentsct.online.OnlineSectioningModel;
    023
    024/**
    025 * Online student sectioning algorithm based on the {@link BranchBoundSelection} of the batch solver. The
    026 * selections adds the ability to provide required free times and sections and to prefer certain sections.
    027 * If a course request has preferred sections, StudentWeights.PreferenceFactor parameter is used
    028 * to penalize selection of a non-preferred section.
    029 *
    030 * @version StudentSct 1.3 (Student Sectioning)<br>
    031 *          Copyright (C) 2014 Tomáš Müller<br>
    032 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    033 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    034 * <br>
    035 *          This library is free software; you can redistribute it and/or modify
    036 *          it under the terms of the GNU Lesser General Public License as
    037 *          published by the Free Software Foundation; either version 3 of the
    038 *          License, or (at your option) any later version. <br>
    039 * <br>
    040 *          This library is distributed in the hope that it will be useful, but
    041 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    042 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    043 *          Lesser General Public License for more details. <br>
    044 * <br>
    045 *          You should have received a copy of the GNU Lesser General Public
    046 *          License along with this library; if not see <a
    047 *          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
    048 *
    049 */
    050public class SuggestionSelection extends BranchBoundSelection implements OnlineSectioningSelection {
    051    protected Set<FreeTimeRequest> iRequiredFreeTimes;
    052    protected Hashtable<CourseRequest, Config> iRequiredConfig = null;
    053    protected Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = null;
    054    protected Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
    055    protected Set<CourseRequest> iRequiredUnassinged = null;
    056    /** add up to 50% for preferred sections */
    057    private double iPreferenceFactor = 0.500;
    058    private double iMaxOverExpected = -1.0;
    059
    060    public SuggestionSelection(DataProperties properties) {
    061        super(properties);
    062        iPreferenceFactor = properties.getPropertyDouble("StudentWeights.PreferenceFactor", iPreferenceFactor);
    063    }
    064
    065    @Override
    066    public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) {
    067        iPreferredSections = preferredSections;
    068    }
    069
    070    @Override
    071    public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) {
    072        iRequiredConfig = new Hashtable<CourseRequest, Config>();
    073        iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>();
    074        if (requiredSections != null) {
    075            for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) {
    076                Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>();
    077                iRequiredSection.put(entry.getKey(), subSection);
    078                for (Section section : entry.getValue()) {
    079                    if (subSection.isEmpty())
    080                        iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig());
    081                    subSection.put(section.getSubpart(), section);
    082                }
    083            }
    084        }
    085    }
    086
    087    @Override
    088    public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) {
    089        iRequiredFreeTimes = requiredFreeTimes;
    090    }
    091
    092    @Override
    093    public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) {
    094        return new Selection(student, assignment).select();
    095    }
    096
    097    @Override
    098    public void setModel(OnlineSectioningModel model) {
    099        super.setModel(model);
    100    }
    101
    102    /**
    103     * Extension of {@link org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.Selection} including checking of
    104     * required free times and sections.
    105     *
    106     */
    107    public class Selection extends BranchBoundSelection.Selection {
    108        public Selection(Student student, Assignment<Request, Enrollment> assignment) {
    109            super(student, assignment);
    110        }
    111
    112        /**
    113         * Check if the given enrollment is allowed
    114         * @param idx enrollment index
    115         * @param enrollment enrollment
    116         * @return true if allowed (there is no conflict with required sections or free times)
    117         */
    118        public boolean isAllowed(int idx, Enrollment enrollment) {
    119            if (enrollment.isCourseRequest()) {
    120                CourseRequest request = (CourseRequest) enrollment.getRequest();
    121                if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false;
    122                Config reqConfig = iRequiredConfig.get(request);
    123                if (reqConfig != null) {
    124                    if (!reqConfig.equals(enrollment.getConfig()))
    125                        return false;
    126                    Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request);
    127                    for (Section section : enrollment.getSections()) {
    128                        Section reqSection = reqSections.get(section.getSubpart());
    129                        if (reqSection == null)
    130                            continue;
    131                        if (!section.equals(reqSection))
    132                            return false;
    133                    }
    134                }
    135            } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) {
    136                if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
    137                    return false;
    138            }
    139            return true;
    140        }
    141
    142        @Override
    143        public boolean inConflict(int idx, Enrollment enrollment) {
    144            if (iMaxOverExpected >= 0.0 && iModel instanceof OnlineSectioningModel) {
    145                double penalty = 0.0;
    146                for (int i = 0; i < idx; i++) {
    147                    if (iAssignment[i] != null && iAssignment[i].getAssignments() != null && iAssignment[i].isCourseRequest())
    148                        for (Section section: iAssignment[i].getSections())
    149                            penalty += ((OnlineSectioningModel)iModel).getOverExpected(iCurrentAssignment, iAssignment, i, section, iAssignment[i].getRequest());
    150                }
    151                if (enrollment.isCourseRequest())
    152                    for (Section section: enrollment.getSections())
    153                        penalty += ((OnlineSectioningModel)iModel).getOverExpected(iCurrentAssignment, iAssignment, idx, section, enrollment.getRequest());
    154                if (penalty > iMaxOverExpected) return true;
    155            }
    156            return super.inConflict(idx, enrollment) || !isAllowed(idx, enrollment);
    157        }
    158
    159        @Override
    160        public Enrollment firstConflict(int idx, Enrollment enrollment) {
    161            Enrollment conflict = super.firstConflict(idx, enrollment);
    162            if (conflict != null)
    163                return conflict;
    164            return (isAllowed(idx, enrollment) ? null : enrollment);
    165        }
    166
    167        @Override
    168        protected boolean canLeaveUnassigned(Request request) {
    169            if (request instanceof CourseRequest) {
    170                if (iRequiredConfig.get(request) != null)
    171                    return false;
    172            } else if (iRequiredFreeTimes.contains(request))
    173                return false;
    174            return true;
    175        }
    176
    177        @Override
    178        protected List<Enrollment> values(final CourseRequest request) {
    179            if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request))
    180                return new ArrayList<Enrollment>();
    181            return super.values(request);
    182        }
    183
    184        @Override
    185        @Deprecated
    186        protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts,
    187                Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
    188            double weight = super.getWeight(enrollment, distanceConflicts, timeOverlappingConflicts);
    189            if (enrollment.isCourseRequest() && iPreferredSections != null) {
    190                Set<Section> preferred = iPreferredSections.get(enrollment.getRequest());
    191                if (preferred != null && !preferred.isEmpty()) {
    192                    double nrPreferred = 0;
    193                    for (Section section : enrollment.getSections())
    194                        if (preferred.contains(section))
    195                            nrPreferred++;
    196                    double preferredFraction = nrPreferred / preferred.size();
    197                    weight *= 1.0 + iPreferenceFactor * preferredFraction;
    198                }
    199            }
    200            return weight;
    201        }
    202
    203        @Override
    204        protected double getBound(Request r) {
    205            double bound = super.getBound(r);
    206            if (r instanceof CourseRequest) {
    207                Set<Section> preferred = iPreferredSections.get(r);
    208                if (preferred != null && !preferred.isEmpty())
    209                    bound *= (1.0 + iPreferenceFactor);
    210            }
    211            return bound;
    212        }
    213
    214    }
    215
    216    @Override
    217    public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) {
    218        iRequiredUnassinged = requiredUnassignedRequests;
    219    }
    220
    221    @Override
    222    public void setMaxOverExpected(double maxOverExpected) {
    223        iMaxOverExpected = maxOverExpected;
    224    }
    225}