001    package net.sf.cpsolver.studentsct.heuristics.selection;
002    
003    import java.util.ArrayList;
004    import java.util.List;
005    
006    import net.sf.cpsolver.ifs.solver.Solver;
007    import net.sf.cpsolver.ifs.util.DataProperties;
008    import net.sf.cpsolver.studentsct.StudentPreferencePenalties;
009    import net.sf.cpsolver.studentsct.model.Config;
010    import net.sf.cpsolver.studentsct.model.Course;
011    import net.sf.cpsolver.studentsct.model.CourseRequest;
012    import net.sf.cpsolver.studentsct.model.Enrollment;
013    import net.sf.cpsolver.studentsct.model.Request;
014    import net.sf.cpsolver.studentsct.model.Section;
015    import net.sf.cpsolver.studentsct.model.Student;
016    import net.sf.cpsolver.studentsct.model.Subpart;
017    
018    import 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 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 Tomas Muller<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    
088    public 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    }