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