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