    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}