001package net.sf.cpsolver.studentsct; 002 003import java.text.DecimalFormat; 004import java.util.Enumeration; 005import java.util.HashMap; 006import java.util.List; 007 008import net.sf.cpsolver.coursett.Constants; 009import net.sf.cpsolver.coursett.model.TimeLocation; 010import net.sf.cpsolver.ifs.heuristics.RouletteWheelSelection; 011import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection; 012import net.sf.cpsolver.studentsct.model.Assignment; 013import net.sf.cpsolver.studentsct.model.Config; 014import net.sf.cpsolver.studentsct.model.Course; 015import net.sf.cpsolver.studentsct.model.CourseRequest; 016import net.sf.cpsolver.studentsct.model.Enrollment; 017import net.sf.cpsolver.studentsct.model.FreeTimeRequest; 018import net.sf.cpsolver.studentsct.model.Offering; 019import net.sf.cpsolver.studentsct.model.Request; 020import net.sf.cpsolver.studentsct.model.Section; 021import net.sf.cpsolver.studentsct.model.Student; 022import net.sf.cpsolver.studentsct.model.Subpart; 023 024/** 025 * An attempt to empirically test the case when students can choose their 026 * sections (section times). <br> 027 * <br> 028 * Each student has his/her own order of possible times of the week (selection 029 * of a day and an hour starting 7:30, 8:30, etc.) -- this order is computed 030 * using roulette wheel selection with the distribution of possible times 031 * defined in {@link StudentPreferencePenalties#sStudentRequestDistribution}. <br> 032 * <br> 033 * A penalty for each section is computed proportionally based on this order 034 * (and the number of slots that falls into each time frame), the existing 035 * branch&bound selection is used to section each student one by one (in a 036 * random order). <br> 037 * <br> 038 * Usage:<br> 039 * <code> 040 * for (Enumeration e=students.elements();e.hasMoreElements();) {<br> 041 * // take a student (one by one)<br> 042 * Student student = (Student)e.nextElement();<br> 043 * <br> 044 * // compute and apply penalties using this class<br> 045 * new StudentPreferencePenalties().setPenalties(student);<br> 046 * <br> 047 * // section a student<br> 048 * // for instance, {@link BranchBoundSelection} can be used (with Neighbour.BranchAndBoundMinimizePenalty set to true)<br> 049 * Neighbour neighbour = new BranchBoundSelection(config).getSelection(student).select();<br> 050 * if (neighbour!=null) neighbour.assign(iteration++);<br> 051 * }; 052 * </code> <br> 053 * <br> 054 * 055 * @version StudentSct 1.2 (Student Sectioning)<br> 056 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 057 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 058 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 059 * <br> 060 * This library is free software; you can redistribute it and/or modify 061 * it under the terms of the GNU Lesser General Public License as 062 * published by the Free Software Foundation; either version 3 of the 063 * License, or (at your option) any later version. <br> 064 * <br> 065 * This library is distributed in the hope that it will be useful, but 066 * WITHOUT ANY WARRANTY; without even the implied warranty of 067 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 068 * Lesser General Public License for more details. <br> 069 * <br> 070 * You should have received a copy of the GNU Lesser General Public 071 * License along with this library; if not see 072 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 073 */ 074public class StudentPreferencePenalties { 075 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(StudentPreferencePenalties.class); 076 private static DecimalFormat sDF = new DecimalFormat("0.000"); 077 private static boolean sDebug = false; 078 public static int sDistTypeUniform = 0; 079 public static int sDistTypePreference = 1; 080 public static int sDistTypePreferenceQuadratic = 2; 081 public static int sDistTypePreferenceReverse = 3; 082 083 public static int[][] sStudentRequestDistribution = new int[][] { 084 // morning, 7:30a, 8:30a, 9:30a, 10:30a, 11:30a, 12:30p, 1:30p, 2:30p, 085 // 3:30p, 4:30p, evening 086 { 1, 1, 4, 7, 10, 10, 5, 8, 8, 6, 3, 1 }, // Monday 087 { 1, 2, 4, 7, 10, 10, 5, 8, 8, 6, 3, 1 }, // Tuesday 088 { 1, 2, 4, 7, 10, 10, 5, 8, 8, 6, 3, 1 }, // Wednesday 089 { 1, 2, 4, 7, 10, 10, 5, 8, 8, 6, 3, 1 }, // Thursday 090 { 1, 2, 4, 7, 10, 10, 5, 4, 3, 2, 1, 1 }, // Friday 091 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, // Saturday 092 { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } // Sunday 093 }; 094 private HashMap<String, Double> iWeight = new HashMap<String, Double>(); 095 096 /** 097 * Constructor. All possible times are ordered based on the distribution 098 * defined by {@link StudentPreferencePenalties#sStudentRequestDistribution} 099 * . The first time gets zero penalty, the second 1/nrTimes, the third 100 * 2/nrTimes etc. where nrTimes is the number of times in 101 * {@link StudentPreferencePenalties#sStudentRequestDistribution}. 102 */ 103 public StudentPreferencePenalties(int disributionType) { 104 RouletteWheelSelection<int[]> roulette = new RouletteWheelSelection<int[]>(); 105 for (int d = 0; d < sStudentRequestDistribution.length; d++) 106 for (int t = 0; t < sStudentRequestDistribution[d].length; t++) { 107 if (disributionType == sDistTypeUniform) { 108 roulette.add(new int[] { d, t }, 1); 109 } else if (disributionType == sDistTypePreference) { 110 roulette.add(new int[] { d, t }, sStudentRequestDistribution[d][t]); 111 } else if (disributionType == sDistTypePreferenceQuadratic) { 112 roulette.add(new int[] { d, t }, sStudentRequestDistribution[d][t] 113 * sStudentRequestDistribution[d][t]); 114 } else if (disributionType == sDistTypePreferenceReverse) { 115 roulette.add(new int[] { d, t }, 11 - sStudentRequestDistribution[d][t]); 116 } else { 117 roulette.add(new int[] { d, t }, 1); 118 } 119 } 120 int idx = 0; 121 while (roulette.hasMoreElements()) { 122 int[] dt = roulette.nextElement(); 123 iWeight.put(dt[0] + "." + dt[1], new Double(((double) idx) / (roulette.size() - 1))); 124 if (sDebug) 125 sLog.debug(" -- " + (idx + 1) + ". preference is " + toString(dt[0], dt[1]) + " (P:" 126 + sDF.format(((double) idx) / (roulette.size() - 1)) + ")"); 127 idx++; 128 } 129 } 130 131 /** 132 * Return day index in 133 * {@link StudentPreferencePenalties#sStudentRequestDistribution} for the 134 * given slot. 135 */ 136 public static int day(int slot) { 137 return slot / Constants.SLOTS_PER_DAY; 138 } 139 140 /** 141 * Return time index in 142 * {@link StudentPreferencePenalties#sStudentRequestDistribution} for the 143 * given slot. 144 */ 145 public static int time(int slot) { 146 int s = slot % Constants.SLOTS_PER_DAY; 147 int min = (s * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN); 148 if (min < 450) 149 return 0; // morning 150 int idx = 1 + (min - 450) / 60; 151 return (idx > 11 ? 11 : idx); // 11+ is evening 152 } 153 154 /** 155 * Return time of the given day and time index of 156 * {@link StudentPreferencePenalties#sStudentRequestDistribution}. 157 */ 158 public String toString(int day, int time) { 159 if (time == 0) 160 return Constants.DAY_NAMES_SHORT[day] + " morning"; 161 if (time == 11) 162 return Constants.DAY_NAMES_SHORT[day] + " evening"; 163 return Constants.DAY_NAMES_SHORT[day] + " " + (6 + time) + ":30"; 164 } 165 166 /** 167 * Return penalty of the given time. It is comuted as average of the penalty 168 * for each time slot of the time. 169 **/ 170 public double getPenalty(TimeLocation time) { 171 int nrSlots = 0; 172 double penalty = 0.0; 173 for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) { 174 int slot = e.nextElement(); 175 nrSlots++; 176 penalty += (iWeight.get(day(slot) + "." + time(slot))).doubleValue(); 177 } 178 return penalty / nrSlots; 179 } 180 181 /** 182 * Return penalty of an assignment. It is a penalty of its time (see 183 * {@link Assignment#getTime()}) or zero if the time is null. 184 */ 185 public double getPenalty(Assignment assignment) { 186 return (assignment.getTime() == null ? 0.0 : getPenalty(assignment.getTime())); 187 } 188 189 /** 190 * Return penalty of an enrollment. It is an average penalty of all its 191 * assignments {@link Enrollment#getAssignments()}. 192 */ 193 public double getPenalty(Enrollment enrollment) { 194 double penalty = 0; 195 for (Section section : enrollment.getSections()) { 196 penalty += getPenalty(section); 197 } 198 return penalty / enrollment.getAssignments().size(); 199 } 200 201 /** Minimal penalty of a course request */ 202 public double getMinPenalty(Request request) { 203 if (request instanceof CourseRequest) 204 return getMinPenalty((CourseRequest) request); 205 else if (request instanceof FreeTimeRequest) 206 return getPenalty(((FreeTimeRequest) request).getTime()); 207 return 0; 208 } 209 210 /** Minimal penalty of a course request */ 211 public double getMinPenalty(CourseRequest request) { 212 double min = Double.MAX_VALUE; 213 for (Course course : request.getCourses()) { 214 min = Math.min(min, getMinPenalty(course.getOffering())); 215 } 216 return (min == Double.MAX_VALUE ? 0.0 : min); 217 } 218 219 /** Minimal penalty of an offering */ 220 public double getMinPenalty(Offering offering) { 221 double min = Double.MAX_VALUE; 222 for (Config config : offering.getConfigs()) { 223 min = Math.min(min, getMinPenalty(config)); 224 } 225 return (min == Double.MAX_VALUE ? 0.0 : min); 226 } 227 228 /** Minimal penalty of a config */ 229 public double getMinPenalty(Config config) { 230 double min = 0; 231 for (Subpart subpart : config.getSubparts()) { 232 min += getMinPenalty(subpart); 233 } 234 return min / config.getSubparts().size(); 235 } 236 237 /** Minimal penalty of a subpart */ 238 public double getMinPenalty(Subpart subpart) { 239 double min = Double.MAX_VALUE; 240 for (Section section : subpart.getSections()) { 241 min = Math.min(min, getPenalty(section)); 242 } 243 return (min == Double.MAX_VALUE ? 0.0 : min); 244 } 245 246 /** Maximal penalty of a course request */ 247 public double getMaxPenalty(Request request) { 248 if (request instanceof CourseRequest) 249 return getMaxPenalty((CourseRequest) request); 250 else if (request instanceof FreeTimeRequest) 251 return getPenalty(((FreeTimeRequest) request).getTime()); 252 return 0; 253 } 254 255 /** Maximal penalty of a course request */ 256 public double getMaxPenalty(CourseRequest request) { 257 double max = Double.MIN_VALUE; 258 for (Course course : request.getCourses()) { 259 max = Math.max(max, getMaxPenalty(course.getOffering())); 260 } 261 return (max == Double.MIN_VALUE ? 0.0 : max); 262 } 263 264 /** Maximal penalty of an offering */ 265 public double getMaxPenalty(Offering offering) { 266 double max = Double.MIN_VALUE; 267 for (Config config : offering.getConfigs()) { 268 max = Math.max(max, getMaxPenalty(config)); 269 } 270 return (max == Double.MIN_VALUE ? 0.0 : max); 271 } 272 273 /** Maximal penalty of a config */ 274 public double getMaxPenalty(Config config) { 275 double max = 0; 276 for (Subpart subpart : config.getSubparts()) { 277 max += getMaxPenalty(subpart); 278 } 279 return max / config.getSubparts().size(); 280 } 281 282 /** Maximal penalty of a subpart */ 283 public double getMaxPenalty(Subpart subpart) { 284 double max = Double.MIN_VALUE; 285 for (Section section : subpart.getSections()) { 286 max = Math.max(max, getPenalty(section)); 287 } 288 return (max == Double.MIN_VALUE ? 0.0 : max); 289 } 290 291 /** Minimal and maximal available enrollment penalty of a request */ 292 public double[] getMinMaxAvailableEnrollmentPenalty(Request request) { 293 if (request instanceof CourseRequest) { 294 return getMinMaxAvailableEnrollmentPenalty((CourseRequest) request); 295 } else { 296 double pen = getPenalty(((FreeTimeRequest) request).getTime()); 297 return new double[] { pen, pen }; 298 } 299 } 300 301 /** Minimal and maximal available enrollment penalty of a request */ 302 public double[] getMinMaxAvailableEnrollmentPenalty(CourseRequest request) { 303 List<Enrollment> enrollments = request.getAvaiableEnrollments(); 304 if (enrollments.isEmpty()) 305 return new double[] { 0, 0 }; 306 double min = Double.MAX_VALUE, max = Double.MIN_VALUE; 307 for (Enrollment enrollment : enrollments) { 308 double penalty = getPenalty(enrollment); 309 min = Math.min(min, penalty); 310 max = Math.max(max, penalty); 311 } 312 return new double[] { min, max }; 313 } 314 315 /** Minimal and maximal available enrollment penalty of a request */ 316 public double[] getMinMaxEnrollmentPenalty(Request request) { 317 if (request instanceof CourseRequest) { 318 return getMinMaxEnrollmentPenalty((CourseRequest) request); 319 } else { 320 double pen = getPenalty(((FreeTimeRequest) request).getTime()); 321 return new double[] { pen, pen }; 322 } 323 } 324 325 /** Minimal and maximal available enrollment penalty of a request */ 326 public double[] getMinMaxEnrollmentPenalty(CourseRequest request) { 327 List<Enrollment> enrollments = request.values(); 328 if (enrollments.isEmpty()) 329 return new double[] { 0, 0 }; 330 double min = Double.MAX_VALUE, max = Double.MIN_VALUE; 331 for (Enrollment enrollment : enrollments) { 332 double penalty = getPenalty(enrollment); 333 min = Math.min(min, penalty); 334 max = Math.max(max, penalty); 335 } 336 return new double[] { min, max }; 337 } 338 339 /** 340 * Set the computed penalties to all sections of all requests of the given 341 * student 342 */ 343 public static void setPenalties(Student student, int distributionType) { 344 if (sDebug) 345 sLog.debug("Setting penalties for " + student); 346 StudentPreferencePenalties penalties = new StudentPreferencePenalties(distributionType); 347 for (Request request : student.getRequests()) { 348 if (!(request instanceof CourseRequest)) 349 continue; 350 CourseRequest courseRequest = (CourseRequest) request; 351 if (sDebug) 352 sLog.debug("-- " + courseRequest); 353 for (Course course : courseRequest.getCourses()) { 354 if (sDebug) 355 sLog.debug(" -- " + course.getName()); 356 for (Config config : course.getOffering().getConfigs()) { 357 if (sDebug) 358 sLog.debug(" -- " + config.getName()); 359 for (Subpart subpart : config.getSubparts()) { 360 if (sDebug) 361 sLog.debug(" -- " + subpart.getName()); 362 for (Section section : subpart.getSections()) { 363 section.setPenalty(penalties.getPenalty(section)); 364 if (sDebug) 365 sLog.debug(" -- " + section); 366 } 367 } 368 } 369 } 370 courseRequest.clearCache(); 371 } 372 } 373 374}