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