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