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