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}