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 Tomas Muller<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    }
122
123    /** Use student preference penalties 
124     * @return true if student preference penalties are to be used
125     **/
126    public boolean isUseStudentPrefPenalties() {
127        return iUseStudentPrefPenalties;
128    }
129
130    /** Use online penalties 
131     * @return true if online penalties are to be used
132     **/
133    public boolean isUsePenalties() {
134        return iUsePenalties;
135    }
136
137    /**
138     * Set online sectioning penalties to all sections of all courses of the
139     * given student
140     */
141    private static void setPenalties(Assignment<Request, Enrollment> assignment, Student student) {
142        for (Request request : student.getRequests()) {
143            if (!(request instanceof CourseRequest))
144                continue;
145            CourseRequest courseRequest = (CourseRequest) request;
146            for (Course course : courseRequest.getCourses()) {
147                for (Config config : course.getOffering().getConfigs()) {
148                    for (Subpart subpart : config.getSubparts()) {
149                        for (Section section : subpart.getSections()) {
150                            section.setPenalty(section.getOnlineSectioningPenalty(assignment));
151                        }
152                    }
153                }
154            }
155            courseRequest.clearCache();
156        }
157    }
158
159    /** Update online sectioning info after the given student is sectioned 
160     * @param assignment current assignment
161     * @param student student in question
162     **/
163    public void updateSpace(Assignment<Request, Enrollment> assignment, Student student) {
164        for (Request request : student.getRequests()) {
165            if (!(request instanceof CourseRequest))
166                continue;
167            CourseRequest courseRequest = (CourseRequest) request;
168            Enrollment enrollment = assignment.getValue(courseRequest);
169            if (enrollment == null)
170                return; // not enrolled --> no update
171            for (Section section : enrollment.getSections()) {
172                section.setSpaceHeld(section.getSpaceHeld() - courseRequest.getWeight());
173                // sLog.debug("  -- space held for "+section+" decreased by 1 (to "+section.getSpaceHeld()+")");
174            }
175            List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>();
176            for (Enrollment enrl : courseRequest.values(assignment)) {
177                boolean overlaps = false;
178                for (Request otherRequest : courseRequest.getStudent().getRequests()) {
179                    if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest))
180                        continue;
181                    Enrollment otherErollment = assignment.getValue(otherRequest);
182                    if (otherErollment == null)
183                        continue;
184                    if (enrl.isOverlapping(otherErollment)) {
185                        overlaps = true;
186                        break;
187                    }
188                }
189                if (!overlaps)
190                    feasibleEnrollments.add(enrl);
191            }
192            double decrement = courseRequest.getWeight() / feasibleEnrollments.size();
193            for (Enrollment feasibleEnrollment : feasibleEnrollments) {
194                for (Section section : feasibleEnrollment.getSections()) {
195                    section.setSpaceExpected(section.getSpaceExpected() - decrement);
196                    // sLog.debug("  -- space expected for "+section+" decreased by "+decrement+" (to "+section.getSpaceExpected()+")");
197                }
198            }
199        }
200    }
201
202    /**
203     * Branch &amp; bound selection for a student
204     */
205    @Override
206    public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) {
207        if (iUsePenalties)
208            setPenalties(assignment, student);
209        Selection selection = null;
210        if (iBranchBound != null)
211            selection = iBranchBound.getSelection(assignment, student);
212        if (iUseStudentPrefPenalties)
213            selection = new EpsilonSelection(student, assignment, selection);
214        return selection;
215    }
216
217    /**
218     * Branch &amp; bound selection for a student
219     */
220    public class EpsilonSelection extends BranchBoundSelection.Selection {
221        private StudentPreferencePenalties iPenalties = null;
222        private Selection iSelection = null;
223
224        /**
225         * Constructor
226         * 
227         * @param student
228         *            selected student
229         * @param assignment current assignment
230         * @param selection selection
231         */
232        public EpsilonSelection(Student student, Assignment<Request, Enrollment> assignment, Selection selection) {
233            super(student, assignment);
234            iPenalties = new StudentPreferencePenalties(iDistributionType);
235            iSelection = selection;
236        }
237
238        /**
239         * Execute branch &amp; bound, return the best found schedule for the
240         * selected student.
241         */
242        @Override
243        public BranchBoundNeighbour select() {
244            BranchBoundNeighbour onlineSelection = null;
245            if (iSelection != null) {
246                onlineSelection = iSelection.select();
247                if (sDebug)
248                    sLog.debug("Online: " + onlineSelection);
249            }
250            BranchBoundNeighbour neighbour = super.select();
251            if (neighbour != null)
252                return neighbour;
253            if (onlineSelection != null)
254                return onlineSelection;
255            return null;
256        }
257
258        /** Assignment penalty */
259        @Override
260        protected double getAssignmentPenalty(int i) {
261            return iPenalties.getPenalty(iAssignment[i]) + iDistConfWeight * getDistanceConflicts(i).size();
262        }
263
264        public boolean isAllowed(int idx, Enrollment enrollment) {
265            if (iSelection == null || iSelection.getBestAssignment() == null
266                    || iSelection.getBestAssignment()[idx] == null)
267                return true;
268            double bestPenalty = iSelection.getBestAssignment()[idx].getPenalty();
269            double limit = (iEpsilon < 0 ? Math.max(0, bestPenalty) : (bestPenalty < 0 ? 1 - iEpsilon : 1 + iEpsilon)
270                    * bestPenalty);
271            if (enrollment.getPenalty() > limit) {
272                if (sDebug)
273                    sLog.debug("  -- enrollment " + enrollment + " was filtered out " + "(penalty="
274                            + enrollment.getPenalty() + ", best=" + bestPenalty + ", limit=" + limit + ")");
275                return false;
276            }
277            return true;
278        }
279
280        /** First conflicting enrollment */
281        @Override
282        public Enrollment firstConflict(int idx, Enrollment enrollment) {
283            Enrollment conflict = super.firstConflict(idx, enrollment);
284            if (conflict != null)
285                return conflict;
286            return (isAllowed(idx, enrollment) ? null : enrollment);
287        }
288
289        /** Student preference penalties 
290         * @return student preference penalties
291         **/
292        public StudentPreferencePenalties getPenalties() {
293            return iPenalties;
294        }
295    }
296}