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 }