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 & 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}