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