    001package org.cpsolver.studentsct.online.selection;
    002
    003import java.util.Hashtable;
    004import java.util.Set;
    005
    006import org.cpsolver.ifs.assignment.Assignment;
    007import org.cpsolver.ifs.solution.Solution;
    008import org.cpsolver.ifs.util.DataProperties;
    009import org.cpsolver.studentsct.extension.DistanceConflict;
    010import org.cpsolver.studentsct.extension.StudentQuality;
    011import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
    012import org.cpsolver.studentsct.model.Config;
    013import org.cpsolver.studentsct.model.Course;
    014import org.cpsolver.studentsct.model.CourseRequest;
    015import org.cpsolver.studentsct.model.Enrollment;
    016import org.cpsolver.studentsct.model.Request;
    017import org.cpsolver.studentsct.model.Section;
    018import org.cpsolver.studentsct.model.Subpart;
    019import org.cpsolver.studentsct.online.OnlineSectioningModel;
    020import org.cpsolver.studentsct.online.expectations.MoreSpaceThanExpected;
    021import org.cpsolver.studentsct.online.expectations.OverExpectedCriterion;
    022import org.cpsolver.studentsct.weights.EqualStudentWeights;
    023import org.cpsolver.studentsct.weights.PriorityStudentWeights;
    024import org.cpsolver.studentsct.weights.StudentWeights;
    025
    026/**
    027 * Online variant of {@link StudentWeights} model. It is either based on
    028 * {@link PriorityStudentWeights} (when StudentWeights.PriorityWeighting=true) or
    029 * on {@link EqualStudentWeights}. Following criteria are included:
    030 * <ul>
    031 *      <li>StudentWeights.NoTimeFactor .. penalization of sections with no time assigned (arrange hours)
    032 *      <li>StudentWeights.SelectionFactor .. penalization of sections that are not selected (if there are selected sections given
    033 *      for a course request, see {@link CourseRequest#getSelectedChoices()})
    034 *      <li>StudentWeights.PenaltyFactor .. penalization for over-expected sections (using {@link OverExpectedCriterion#getOverExpected(Assignment, Section, Request)}
    035 *      <li>StudentWeights.AvgPenaltyFactor .. penalization of section penalties (see {@link Section#getPenalty()}), using average penalty per request
    036 *      <li>StudentWeights.AvailabilityFactor .. penalization of unbalanced sections (portion of the section over the target fill, averaged per request)
    037 * </ul>
    038 *
    039 * @version StudentSct 1.3 (Student Sectioning)<br>
    040 *          Copyright (C) 2014 Tomáš Müller<br>
    041 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    042 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    043 * <br>
    044 *          This library is free software; you can redistribute it and/or modify
    045 *          it under the terms of the GNU Lesser General Public License as
    046 *          published by the Free Software Foundation; either version 3 of the
    047 *          License, or (at your option) any later version. <br>
    048 * <br>
    049 *          This library is distributed in the hope that it will be useful, but
    050 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    051 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    052 *          Lesser General Public License for more details. <br>
    053 * <br>
    054 *          You should have received a copy of the GNU Lesser General Public
    055 *          License along with this library; if not see <a
    056 *          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
    057 *
    058 */
    059public class StudentSchedulingAssistantWeights implements StudentWeights {
    060    /** deduction for section with no time assignment */
    061    private double iNoTimeFactor = 0.050;
    062    /**
    063     * deduction for sections that are not preferred (different time &
    064     * instructor)
    065     */
    066    private double iSelectionFactor = 0.125;
    067    /** deduction for over expected sections */
    068    private double iOverExpectedFactor = 0.250;
    069    /** similar to balancing factor on {@link PriorityStudentWeights} */
    070    private double iAvailabilityFactor = 0.050;
    071    /** negative penalty means there is space available */
    072    private double iPenaltyFactor = 0.001;
    073
    074    private Hashtable<CourseRequest, double[]> iCache = new Hashtable<CourseRequest, double[]>();
    075
    076    private boolean iPriorityWeighting = true;
    077
    078    private StudentWeights iParent;
    079
    080    public StudentSchedulingAssistantWeights(DataProperties properties) {
    081        iNoTimeFactor = properties.getPropertyDouble("StudentWeights.NoTimeFactor", iNoTimeFactor);
    082        iSelectionFactor = properties.getPropertyDouble("StudentWeights.SelectionFactor", iSelectionFactor);
    083        iOverExpectedFactor = properties.getPropertyDouble("StudentWeights.PenaltyFactor", iOverExpectedFactor);
    084        iPenaltyFactor = properties.getPropertyDouble("StudentWeights.AvgPenaltyFactor", iPenaltyFactor);
    085        iAvailabilityFactor = properties.getPropertyDouble("StudentWeights.AvailabilityFactor", iAvailabilityFactor);
    086        iPriorityWeighting = properties.getPropertyBoolean("StudentWeights.PriorityWeighting", iPriorityWeighting);
    087        if (iPriorityWeighting)
    088            iParent = new PriorityStudentWeights(properties);
    089        else
    090            iParent = new EqualStudentWeights(properties);
    091    }
    092
    093    public void clearBestCache() {
    094        iCache.clear();
    095    }
    096
    097    private double getOverExpected(Assignment<Request, Enrollment> assignment, Section section, Request request) {
    098        if (request.getModel() == null || !(request.getModel() instanceof OnlineSectioningModel))
    099            return new MoreSpaceThanExpected().getOverExpected(assignment, section, request);
    100        return ((OnlineSectioningModel) request.getModel()).getOverExpected(assignment, section, request);
    101    }
    102
    103    private double[] best(Assignment<Request, Enrollment> assignment, CourseRequest cr) {
    104        double[] cached = iCache.get(cr);
    105        if (cached != null)
    106            return cached;
    107        double bestTime = 0;
    108        Double bestOverExpected = null;
    109        Double bestAvgPenalty = null;
    110        double bestSelected = 0.0;
    111        for (Course course : cr.getCourses()) {
    112            for (Config config : course.getOffering().getConfigs()) {
    113                int size = config.getSubparts().size();
    114                double sectionsWithTime = 0;
    115                double overExpected = 0;
    116                double penalty = 0;
    117                double selectedSections = 0;
    118                for (Subpart subpart : config.getSubparts()) {
    119                    boolean hasTime = false;
    120                    Double sectionPenalty = null;
    121                    Double sectionOverExpected = null;
    122                    boolean hasSelection = false;
    123                    for (Section section : subpart.getSections()) {
    124                        if (section.getLimit() == 0)
    125                            continue;
    126                        if (section.getTime() != null)
    127                            hasTime = true;
    128                        if (!cr.getSelectedChoices().isEmpty() && cr.isSelected(section))
    129                            hasSelection = true;
    130                        if (sectionPenalty == null || sectionPenalty > section.getPenalty())
    131                            sectionPenalty = section.getPenalty();
    132                        double oexp = getOverExpected(assignment, section, cr);
    133                        if (sectionOverExpected == null || sectionOverExpected > oexp)
    134                            sectionOverExpected = oexp;
    135                    }
    136                    if (hasTime)
    137                        sectionsWithTime++;
    138                    if (sectionPenalty != null)
    139                        penalty += sectionPenalty;
    140                    if (hasSelection)
    141                        selectedSections++;
    142                    if (sectionOverExpected != null)
    143                        overExpected += sectionOverExpected;
    144                }
    145                if (sectionsWithTime / size > bestTime)
    146                    bestTime = sectionsWithTime / size;
    147                if (bestOverExpected == null || overExpected < bestOverExpected)
    148                    bestOverExpected = overExpected;
    149                if (bestAvgPenalty == null || penalty / size < bestAvgPenalty)
    150                    bestAvgPenalty = penalty / size;
    151                if (selectedSections / size > bestSelected)
    152                    bestSelected = selectedSections / size;
    153            }
    154        }
    155        cached = new double[] { bestTime, (bestOverExpected == null ? 0.0 : bestOverExpected),
    156                (bestAvgPenalty == null ? 0.0 : bestAvgPenalty), bestSelected };
    157        iCache.put(cr, cached);
    158        return cached;
    159    }
    160
    161    public double getBaseWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
    162        return iParent.getWeight(assignment, enrollment);
    163    }
    164
    165    @Override
    166    public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
    167        if (!enrollment.isCourseRequest())
    168            return getBaseWeight(assignment, enrollment);
    169        if (enrollment.getAssignments().isEmpty())
    170            return 0;
    171
    172        double base = getBaseWeight(assignment, enrollment);
    173        double weight = base;
    174
    175        int size = enrollment.getAssignments().size();
    176
    177        CourseRequest cr = (CourseRequest) enrollment.getRequest();
    178        double[] best = best(assignment, cr);
    179
    180        double hasTime = 0;
    181        double oexp = 0;
    182        double penalty = 0.0;
    183        for (Section section : enrollment.getSections()) {
    184            if (section.getTime() != null)
    185                hasTime++;
    186            oexp += getOverExpected(assignment, section, cr);
    187            penalty += section.getPenalty();
    188        }
    189        double noTime = best[0] - (hasTime / size);
    190        double overExpected = oexp - best[1];
    191        double avgPenalty = (penalty / size) - best[2];
    192
    193        double nrSelected = 0;
    194        if (!cr.getSelectedChoices().isEmpty()) {
    195            for (Section section : enrollment.getSections())
    196                if (cr.isSelected(section))
    197                    nrSelected++;
    198        }
    199        double unselectedFraction = best[3] - (nrSelected / size);
    200
    201        double unavailableSize = 0;
    202        double altSectionsWithLimit = 0;
    203        for (Section section : enrollment.getSections()) {
    204            Subpart subpart = section.getSubpart();
    205            // skip unlimited and single section subparts
    206            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
    207                continue;
    208            // average size
    209            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
    210            // section is below average
    211            if (section.getLimit() < averageSize)
    212                unavailableSize += (averageSize - section.getLimit()) / averageSize;
    213            altSectionsWithLimit++;
    214        }
    215        double unavailableSizeFraction = (unavailableSize > 0 ? unavailableSize / altSectionsWithLimit : 0.0);
    216
    217        weight -= overExpected * base * iOverExpectedFactor;
    218
    219        weight -= unselectedFraction * base * iSelectionFactor;
    220
    221        weight -= noTime * base * iNoTimeFactor;
    222
    223        weight -= unavailableSizeFraction * base * iAvailabilityFactor;
    224
    225        weight -= avgPenalty * iPenaltyFactor;
    226
    227        return round(weight);
    228    }
    229
    230    @Override
    231    public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment,
    232            Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
    233        if (enrollment.getAssignments().isEmpty())
    234            return 0;
    235
    236        double weight = getWeight(assignment, enrollment);
    237
    238        if (distanceConflicts != null)
    239            for (DistanceConflict.Conflict c : distanceConflicts) {
    240                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
    241                if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
    242                    weight -= getDistanceConflictWeight(assignment, c);
    243            }
    244
    245        if (timeOverlappingConflicts != null)
    246            for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) {
    247                weight -= getTimeOverlapConflictWeight(assignment, enrollment, c);
    248            }
    249
    250        return weight;
    251
    252    }
    253
    254    protected double round(double value) {
    255        return Math.ceil(10000.0 * value) / 10000.0;
    256    }
    257
    258    @Override
    259    public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) {
    260        return iParent.isBetterThanBestSolution(currentSolution);
    261    }
    262
    263    @Override
    264    public double getBound(Request request) {
    265        return iParent.getBound(request);
    266    }
    267
    268    @Override
    269    @Deprecated
    270    public double getDistanceConflictWeight(Assignment<Request, Enrollment> assignment,
    271            DistanceConflict.Conflict distanceConflict) {
    272        return iParent.getDistanceConflictWeight(assignment, distanceConflict);
    273    }
    274
    275    @Override
    276    @Deprecated
    277    public double getTimeOverlapConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment,
    278            TimeOverlapsCounter.Conflict timeOverlap) {
    279        return iParent.getTimeOverlapConflictWeight(assignment, enrollment, timeOverlap);
    280    }
    281
    282    @Override
    283    public boolean isFreeTimeAllowOverlaps() {
    284        return iParent.isFreeTimeAllowOverlaps();
    285    }
    286
    287    @Override
    288    public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> qualityConflicts) {
    289        if (enrollment.getAssignments().isEmpty()) return 0;
    290
    291        double weight = getWeight(assignment, enrollment);
    292
    293        if (qualityConflicts != null) {
    294            for (StudentQuality.Conflict c: qualityConflicts) {
    295                switch (c.getType().getType()) {
    296                    case BOTH:
    297                        weight -= getStudentQualityConflictWeight(assignment, enrollment, c);
    298                        break;
    299                    case REQUEST:
    300                        if (enrollment.isCourseRequest())
    301                            weight -= getStudentQualityConflictWeight(assignment, enrollment, c);
    302                        break;
    303                    case LOWER:
    304                        Enrollment other = c.getOther(enrollment);
    305                        if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
    306                            weight -= getStudentQualityConflictWeight(assignment, enrollment, c);
    307                        break;
    308                    case HIGHER:
    309                        other = c.getOther(enrollment);
    310                        if (other.getRequest().getPriority() >= enrollment.getRequest().getPriority())
    311                            weight -= getStudentQualityConflictWeight(assignment, enrollment, c);
    312                        break;
    313                }
    314            }
    315        }
    316        return weight;
    317
    318    }
    319
    320    @Override
    321    public double getStudentQualityConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, StudentQuality.Conflict conflict) {
    322        return iParent.getStudentQualityConflictWeight(assignment, enrollment, conflict);
    323    }
    324}