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