    001package org.cpsolver.studentsct.heuristics.selection;
    002
    003import java.util.ArrayList;
    004import java.util.List;
    005
    006
    007import org.apache.log4j.Logger;
    008import org.cpsolver.ifs.assignment.Assignment;
    009import org.cpsolver.ifs.solver.Solver;
    010import org.cpsolver.ifs.util.DataProperties;
    011import org.cpsolver.studentsct.StudentPreferencePenalties;
    012import org.cpsolver.studentsct.model.Config;
    013import org.cpsolver.studentsct.model.Course;
    014import org.cpsolver.studentsct.model.CourseRequest;
    015import org.cpsolver.studentsct.model.Enrollment;
    016import org.cpsolver.studentsct.model.Request;
    017import org.cpsolver.studentsct.model.Section;
    018import org.cpsolver.studentsct.model.Student;
    019import org.cpsolver.studentsct.model.Subpart;
    020
    021/**
    022 * Section given student using branch &amp; bound algorithm with no unassignments
    023 * allowed.
    024 *
    025 * <br>
    026 * <br>
    027 * Parameters: <br>
    028 * <table border='1' summary='Related Solver Parameters'>
    029 * <tr>
    030 * <th>Parameter</th>
    031 * <th>Type</th>
    032 * <th>Comment</th>
    033 * </tr>
    034 * <tr>
    035 * <td>Sectioning.UseStudentPreferencePenalties</td>
    036 * <td>{@link Boolean}</td>
    037 * <td>If true, {@link StudentPreferencePenalties} are used</td>
    038 * </tr>
    039 * <tr>
    040 * <td>Sectioning.Distribution</td>
    041 * <td>{@link Integer}</td>
    042 * <td>When student preference penalties are used, defines which distribution is
    043 * to be used (one of {@link StudentPreferencePenalties#sDistTypePreference},
    044 * {@link StudentPreferencePenalties#sDistTypePreferenceQuadratic},
    045 * {@link StudentPreferencePenalties#sDistTypePreferenceReverse},
    046 * {@link StudentPreferencePenalties#sDistTypeUniform})</td>
    047 * </tr>
    048 * <tr>
    049 * <td>Sectioning.UseOnlinePenalties</td>
    050 * <td>{@link Boolean}</td>
    051 * <td>If true, online sectioning penalties computed based on held/expected
    052 * space are used.</td>
    053 * </tr>
    054 * <tr>
    055 * <td>Sectioning.Epsilon</td>
    056 * <td>{@link Double}</td>
    057 * <td>When both online penalties and student preference penalties are used: a
    058 * solution based on online penalties is computed first, this solution (and the
    059 * given epsilon) is then used to setup bounds on online penalties for the
    060 * solution that minimizes student preference penalties. Limit on online penalty
    061 * is computed as (1+Section.Epsilon) {@link BranchBoundSelection.Selection#getPenalty()}, i.e., only
    062 * sections with penalty equal or below this limit can be used -- among these
    063 * the solution that minimizes student preference penalties is computed.</td>
    064 * </tr>
    065 * </table>
    066 * <br>
    067 * <br>
    068 *
    069 * @version StudentSct 1.3 (Student Sectioning)<br>
    070 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    071 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    072 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    073 * <br>
    074 *          This library is free software; you can redistribute it and/or modify
    075 *          it under the terms of the GNU Lesser General Public License as
    076 *          published by the Free Software Foundation; either version 3 of the
    077 *          License, or (at your option) any later version. <br>
    078 * <br>
    079 *          This library is distributed in the hope that it will be useful, but
    080 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    081 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    082 *          Lesser General Public License for more details. <br>
    083 * <br>
    084 *          You should have received a copy of the GNU Lesser General Public
    085 *          License along with this library; if not see
    086 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    087 */
    088
    089public class OnlineSelection extends BranchBoundSelection {
    090    private static Logger sLog = Logger.getLogger(OnlineSelection.class);
    091    private int iDistributionType = -1;
    092    private double iEpsilon = 0.05;
    093    private boolean iUsePenalties = true;
    094    private boolean iUseStudentPrefPenalties = false;
    095    private BranchBoundSelection iBranchBound = null;
    096
    097    /**
    098     * Constructor
    099     *
    100     * @param properties
    101     *            configuration
    102     */
    103    public OnlineSelection(DataProperties properties) {
    104        super(properties);
    105        iUseStudentPrefPenalties = properties.getPropertyBoolean("Sectioning.UseStudentPreferencePenalties",
    106                iUseStudentPrefPenalties);
    107        iDistributionType = properties.getPropertyInt("Sectioning.Distribution",
    108                StudentPreferencePenalties.sDistTypePreference);
    109        iEpsilon = properties.getPropertyDouble("Sectioning.Epsilon", iEpsilon);
    110        iUsePenalties = properties.getPropertyBoolean("Sectioning.UseOnlinePenalties", iUsePenalties);
    111        if (iUseStudentPrefPenalties && !properties.containsPropery("Sectioning.UseOnlinePenalties"))
    112            iUsePenalties = false;
    113        if (iUsePenalties || !iUseStudentPrefPenalties)
    114            iBranchBound = new BranchBoundSelection(properties);
    115        iMinimizePenalty = true;
    116    }
    117
    118    @Override
    119    public void init(Solver<Request, Enrollment> solver) {
    120        init(solver, "Online...");
    121        if (iBranchBound != null)
    122            iBranchBound.init(solver, "Online...");
    123    }
    124
    125    /** Use student preference penalties
    126     * @return true if student preference penalties are to be used
    127     **/
    128    public boolean isUseStudentPrefPenalties() {
    129        return iUseStudentPrefPenalties;
    130    }
    131
    132    /** Use online penalties
    133     * @return true if online penalties are to be used
    134     **/
    135    public boolean isUsePenalties() {
    136        return iUsePenalties;
    137    }
    138
    139    /**
    140     * Set online sectioning penalties to all sections of all courses of the
    141     * given student
    142     */
    143    private static void setPenalties(Assignment<Request, Enrollment> assignment, Student student) {
    144        for (Request request : student.getRequests()) {
    145            if (!(request instanceof CourseRequest))
    146                continue;
    147            CourseRequest courseRequest = (CourseRequest) request;
    148            for (Course course : courseRequest.getCourses()) {
    149                for (Config config : course.getOffering().getConfigs()) {
    150                    for (Subpart subpart : config.getSubparts()) {
    151                        for (Section section : subpart.getSections()) {
    152                            section.setPenalty(section.getOnlineSectioningPenalty(assignment));
    153                        }
    154                    }
    155                }
    156            }
    157            courseRequest.clearCache();
    158        }
    159    }
    160
    161    /** Update online sectioning info after the given student is sectioned
    162     * @param assignment current assignment
    163     * @param student student in question
    164     **/
    165    public void updateSpace(Assignment<Request, Enrollment> assignment, Student student) {
    166        for (Request request : student.getRequests()) {
    167            if (!(request instanceof CourseRequest))
    168                continue;
    169            CourseRequest courseRequest = (CourseRequest) request;
    170            Enrollment enrollment = assignment.getValue(courseRequest);
    171            if (enrollment == null)
    172                return; // not enrolled --> no update
    173            for (Section section : enrollment.getSections()) {
    174                section.setSpaceHeld(section.getSpaceHeld() - courseRequest.getWeight());
    175                // sLog.debug("  -- space held for "+section+" decreased by 1 (to "+section.getSpaceHeld()+")");
    176            }
    177            List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>();
    178            for (Enrollment enrl : courseRequest.values(assignment)) {
    179                boolean overlaps = false;
    180                for (Request otherRequest : courseRequest.getStudent().getRequests()) {
    181                    if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest))
    182                        continue;
    183                    Enrollment otherErollment = assignment.getValue(otherRequest);
    184                    if (otherErollment == null)
    185                        continue;
    186                    if (enrl.isOverlapping(otherErollment)) {
    187                        overlaps = true;
    188                        break;
    189                    }
    190                }
    191                if (!overlaps)
    192                    feasibleEnrollments.add(enrl);
    193            }
    194            double decrement = courseRequest.getWeight() / feasibleEnrollments.size();
    195            for (Enrollment feasibleEnrollment : feasibleEnrollments) {
    196                for (Section section : feasibleEnrollment.getSections()) {
    197                    section.setSpaceExpected(section.getSpaceExpected() - decrement);
    198                    // sLog.debug("  -- space expected for "+section+" decreased by "+decrement+" (to "+section.getSpaceExpected()+")");
    199                }
    200            }
    201        }
    202    }
    203
    204    /**
    205     * Branch &amp; bound selection for a student
    206     */
    207    @Override
    208    public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) {
    209        if (iUsePenalties)
    210            setPenalties(assignment, student);
    211        Selection selection = null;
    212        if (iBranchBound != null)
    213            selection = iBranchBound.getSelection(assignment, student);
    214        if (iUseStudentPrefPenalties)
    215            selection = new EpsilonSelection(student, assignment, selection);
    216        return selection;
    217    }
    218
    219    /**
    220     * Branch &amp; bound selection for a student
    221     */
    222    public class EpsilonSelection extends BranchBoundSelection.Selection {
    223        private StudentPreferencePenalties iPenalties = null;
    224        private Selection iSelection = null;
    225
    226        /**
    227         * Constructor
    228         *
    229         * @param student
    230         *            selected student
    231         * @param assignment current assignment
    232         * @param selection selection
    233         */
    234        public EpsilonSelection(Student student, Assignment<Request, Enrollment> assignment, Selection selection) {
    235            super(student, assignment);
    236            iPenalties = new StudentPreferencePenalties(iDistributionType);
    237            iSelection = selection;
    238        }
    239
    240        /**
    241         * Execute branch &amp; bound, return the best found schedule for the
    242         * selected student.
    243         */
    244        @Override
    245        public BranchBoundNeighbour select() {
    246            BranchBoundNeighbour onlineSelection = null;
    247            if (iSelection != null) {
    248                onlineSelection = iSelection.select();
    249                if (sDebug)
    250                    sLog.debug("Online: " + onlineSelection);
    251            }
    252            BranchBoundNeighbour neighbour = super.select();
    253            if (neighbour != null)
    254                return neighbour;
    255            if (onlineSelection != null)
    256                return onlineSelection;
    257            return null;
    258        }
    259
    260        /** Assignment penalty */
    261        @Override
    262        protected double getAssignmentPenalty(int i) {
    263            return iPenalties.getPenalty(iAssignment[i]) + iDistConfWeight * getDistanceConflicts(i).size();
    264        }
    265
    266        public boolean isAllowed(int idx, Enrollment enrollment) {
    267            if (iSelection == null || iSelection.getBestAssignment() == null
    268                    || iSelection.getBestAssignment()[idx] == null)
    269                return true;
    270            double bestPenalty = iSelection.getBestAssignment()[idx].getPenalty();
    271            double limit = (iEpsilon < 0 ? Math.max(0, bestPenalty) : (bestPenalty < 0 ? 1 - iEpsilon : 1 + iEpsilon)
    272                    * bestPenalty);
    273            if (enrollment.getPenalty() > limit) {
    274                if (sDebug)
    275                    sLog.debug("  -- enrollment " + enrollment + " was filtered out " + "(penalty="
    276                            + enrollment.getPenalty() + ", best=" + bestPenalty + ", limit=" + limit + ")");
    277                return false;
    278            }
    279            return true;
    280        }
    281
    282        /** First conflicting enrollment */
    283        @Override
    284        public Enrollment firstConflict(int idx, Enrollment enrollment) {
    285            Enrollment conflict = super.firstConflict(idx, enrollment);
    286            if (conflict != null)
    287                return conflict;
    288            return (isAllowed(idx, enrollment) ? null : enrollment);
    289        }
    290
    291        /** Student preference penalties
    292         * @return student preference penalties
    293         **/
    294        public StudentPreferencePenalties getPenalties() {
    295            return iPenalties;
    296        }
    297    }
    298}