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     * &nbsp;&nbsp;// take a student (one by one)<br>
042     * &nbsp;&nbsp;Student student = (Student)e.nextElement();<br>
043     * <br>
044     * &nbsp;&nbsp;// compute and apply penalties using this class<br>
045     * &nbsp;&nbsp;new StudentPreferencePenalties().setPenalties(student);<br>
046     * <br>
047     * &nbsp;&nbsp;// section a student<br>
048     * &nbsp;&nbsp;// for instance, {@link BranchBoundSelection} can be used (with Neighbour.BranchAndBoundMinimizePenalty set to true)<br>
049     * &nbsp;&nbsp;Neighbour neighbour = new BranchBoundSelection(config).getSelection(student).select();<br>
050     * &nbsp;&nbsp;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    }