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}