001 package net.sf.cpsolver.studentsct;
002
003 import java.text.DecimalFormat;
004 import java.util.Enumeration;
005 import java.util.HashMap;
006 import java.util.List;
007
008 import net.sf.cpsolver.coursett.Constants;
009 import net.sf.cpsolver.coursett.model.TimeLocation;
010 import net.sf.cpsolver.ifs.heuristics.RouletteWheelSelection;
011 import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
012 import net.sf.cpsolver.studentsct.model.Assignment;
013 import net.sf.cpsolver.studentsct.model.Config;
014 import net.sf.cpsolver.studentsct.model.Course;
015 import net.sf.cpsolver.studentsct.model.CourseRequest;
016 import net.sf.cpsolver.studentsct.model.Enrollment;
017 import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
018 import net.sf.cpsolver.studentsct.model.Offering;
019 import net.sf.cpsolver.studentsct.model.Request;
020 import net.sf.cpsolver.studentsct.model.Section;
021 import net.sf.cpsolver.studentsct.model.Student;
022 import 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 Tomas Muller<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 */
074 public 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 }