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}