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