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}