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