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