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