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