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