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