001 package net.sf.cpsolver.studentsct.constraint;
002
003 import java.util.ArrayList;
004 import java.util.List;
005 import java.util.Set;
006
007 import net.sf.cpsolver.ifs.model.GlobalConstraint;
008 import net.sf.cpsolver.ifs.util.DataProperties;
009 import net.sf.cpsolver.ifs.util.ToolBox;
010 import net.sf.cpsolver.studentsct.StudentSectioningModel;
011 import net.sf.cpsolver.studentsct.model.Enrollment;
012 import net.sf.cpsolver.studentsct.model.Request;
013 import net.sf.cpsolver.studentsct.model.Section;
014 import net.sf.cpsolver.studentsct.reservation.Reservation;
015
016 /**
017 * Section limit constraint. This global constraint ensures that a limit of each
018 * section is not exceeded. This means that the total sum of weights of course
019 * requests (see {@link Request#getWeight()}) enrolled into a section is below
020 * the section's limit (see {@link Section#getLimit()}).
021 *
022 * <br>
023 * <br>
024 * Sections with negative limit are considered unlimited, and therefore
025 * completely ignored by this constraint.
026 *
027 * <br>
028 * <br>
029 * This constraint also check section reservations.
030 *
031 * <br>
032 * <br>
033 * Parameters:
034 * <table border='1'>
035 * <tr>
036 * <th>Parameter</th>
037 * <th>Type</th>
038 * <th>Comment</th>
039 * </tr>
040 * <tr>
041 * <td>SectionLimit.PreferDummyStudents</td>
042 * <td>{@link Boolean}</td>
043 * <td>If true, requests of dummy (last-like) students are preferred to be
044 * selected as conflicting.</td>
045 * </tr>
046 * </table>
047 * <br>
048 * <br>
049 *
050 * @version StudentSct 1.2 (Student Sectioning)<br>
051 * Copyright (C) 2007 - 2010 Tomas Muller<br>
052 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
053 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
054 * <br>
055 * This library is free software; you can redistribute it and/or modify
056 * it under the terms of the GNU Lesser General Public License as
057 * published by the Free Software Foundation; either version 3 of the
058 * License, or (at your option) any later version. <br>
059 * <br>
060 * This library is distributed in the hope that it will be useful, but
061 * WITHOUT ANY WARRANTY; without even the implied warranty of
062 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
063 * Lesser General Public License for more details. <br>
064 * <br>
065 * You should have received a copy of the GNU Lesser General Public
066 * License along with this library; if not see
067 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
068 */
069 public class SectionLimit extends GlobalConstraint<Request, Enrollment> {
070 private static double sNominalWeight = 0.00001;
071 private boolean iPreferDummyStudents = false;
072
073 /**
074 * Constructor
075 *
076 * @param cfg
077 * solver configuration
078 */
079 public SectionLimit(DataProperties cfg) {
080 super();
081 iPreferDummyStudents = cfg.getPropertyBoolean("SectionLimit.PreferDummyStudents", false);
082 }
083
084 /**
085 * Enrollment weight of a section if the given request is assigned. In order
086 * to overcome rounding problems with last-like students ( e.g., 5 students
087 * are projected to two sections of limit 2 -- each section can have up to 3
088 * of these last-like students), the weight of the request with the highest
089 * weight in the section is changed to a small nominal weight.
090 *
091 * @param section
092 * a section that is of concern
093 * @param request
094 * a request of a student to be assigned containing the given
095 * section
096 * @return section's new weight
097 */
098 public static double getEnrollmentWeight(Section section, Request request) {
099 return section.getEnrollmentWeight(request) + request.getWeight()
100 - Math.max(section.getMaxEnrollmentWeight(), request.getWeight()) + sNominalWeight;
101 }
102
103 /**
104 * Remaining unreserved space in a section if the given request is assigned. In order
105 * to overcome rounding problems with last-like students ( e.g., 5 students
106 * are projected to two sections of limit 2 -- each section can have up to 3
107 * of these last-like students), the weight of the request with the highest
108 * weight in the section is changed to a small nominal weight.
109 *
110 * @param section
111 * a section that is of concern
112 * @param request
113 * a request of a student to be assigned containing the given
114 * section
115 * @return section's new unreserved space
116 */
117 public static double getUnreservedSpace(Section section, Request request) {
118 return section.getUnreservedSpace(request) - request.getWeight()
119 + Math.max(section.getMaxEnrollmentWeight(), request.getWeight()) - sNominalWeight;
120 }
121
122
123 /**
124 * True if the enrollment has reservation for this section.
125 * Everything else is checked in the {@link ReservationLimit} constraint.
126 **/
127 private boolean hasSectionReservation(Enrollment enrollment, Section section) {
128 Reservation reservation = enrollment.getReservation();
129 if (reservation == null) return false;
130 Set<Section> sections = reservation.getSections(section.getSubpart());
131 return sections != null && sections.contains(section);
132 }
133
134 /**
135 * A given enrollment is conflicting, if there is a section which limit
136 * (computed by {@link SectionLimit#getEnrollmentWeight(Section, Request)})
137 * exceeds the section limit. <br>
138 * For each of such sections, one or more existing enrollments are
139 * (randomly) selected as conflicting until the overall weight is under the
140 * limit.
141 *
142 * @param enrollment
143 * {@link Enrollment} that is being considered
144 * @param conflicts
145 * all computed conflicting requests are added into this set
146 */
147 @Override
148 public void computeConflicts(Enrollment enrollment, Set<Enrollment> conflicts) {
149 // check reservation can assign over the limit
150 if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
151 enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
152 return;
153
154 // exclude free time requests
155 if (!enrollment.isCourseRequest())
156 return;
157
158 // for each section
159 for (Section section : enrollment.getSections()) {
160
161 // no reservation -- check the space in the unreserved space in the section
162 if (enrollment.getConfig().getOffering().hasReservations() && !hasSectionReservation(enrollment, section)) {
163 // section is fully reserved by section reservations
164 if (section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) {
165 conflicts.add(enrollment);
166 return;
167 }
168
169 double unreserved = getUnreservedSpace(section, enrollment.getRequest());
170
171 if (unreserved < 0.0) {
172 // no unreserved space available -> cannot be assigned
173 // try to unassign some other enrollments that also do not have reservation
174
175 List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments().size());
176 for (Enrollment e : section.getEnrollments()) {
177 if (e.getRequest().equals(enrollment.getRequest()))
178 continue;
179 if (hasSectionReservation(e, section))
180 continue;
181 if (conflicts.contains(e))
182 unreserved += e.getRequest().getWeight();
183 else
184 adepts.add(e);
185 }
186
187 while (unreserved < 0.0) {
188 if (adepts.isEmpty()) {
189 // no adepts -> enrollment cannot be assigned
190 conflicts.add(enrollment);
191 return;
192 }
193
194 // pick adept (prefer dummy students), decrease unreserved space,
195 // make conflict
196 List<Enrollment> best = new ArrayList<Enrollment>();
197 boolean bestDummy = false;
198 double bestValue = 0;
199 for (Enrollment adept: adepts) {
200 boolean dummy = adept.getStudent().isDummy();
201 double value = adept.toDouble(false);
202
203 if (iPreferDummyStudents && dummy != bestDummy) {
204 if (dummy) {
205 best.clear();
206 best.add(adept);
207 bestDummy = dummy;
208 bestValue = value;
209 }
210 continue;
211 }
212
213 if (best.isEmpty() || value > bestValue) {
214 if (best.isEmpty()) best.clear();
215 best.add(adept);
216 bestDummy = dummy;
217 bestValue = value;
218 } else if (bestValue == value) {
219 best.add(adept);
220 }
221 }
222
223 Enrollment conflict = ToolBox.random(best);
224 adepts.remove(conflict);
225 unreserved += conflict.getRequest().getWeight();
226 conflicts.add(conflict);
227 }
228 }
229 }
230
231 // unlimited section
232 if (section.getLimit() < 0)
233 continue;
234
235 // new enrollment weight
236 double enrlWeight = getEnrollmentWeight(section, enrollment.getRequest());
237
238 // below limit -> ok
239 if (enrlWeight <= section.getLimit())
240 continue;
241
242 // above limit -> compute adepts (current assignments that are not
243 // yet conflicting) exclude all conflicts as well
244 List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments().size());
245 for (Enrollment e : section.getEnrollments()) {
246 if (e.getRequest().equals(enrollment.getRequest()))
247 continue;
248 if (conflicts.contains(e))
249 enrlWeight -= e.getRequest().getWeight();
250 else
251 adepts.add(e);
252 }
253
254 // while above limit -> pick an adept and make it conflicting
255 while (enrlWeight > section.getLimit()) {
256 if (adepts.isEmpty()) {
257 // no adepts -> enrollment cannot be assigned
258 conflicts.add(enrollment);
259 return;
260 }
261
262 // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
263 // weight, make conflict
264 List<Enrollment> best = new ArrayList<Enrollment>();
265 boolean bestDummy = false;
266 double bestValue = 0;
267 boolean bestRes = true;
268 for (Enrollment adept: adepts) {
269 boolean dummy = adept.getStudent().isDummy();
270 double value = adept.toDouble(false);
271 boolean res = hasSectionReservation(adept, section);
272
273 if (iPreferDummyStudents && dummy != bestDummy) {
274 if (dummy) {
275 best.clear();
276 best.add(adept);
277 bestDummy = dummy;
278 bestValue = value;
279 bestRes = res;
280 }
281 continue;
282 }
283
284 if (bestRes != res) {
285 if (!res) {
286 best.clear();
287 best.add(adept);
288 bestDummy = dummy;
289 bestValue = value;
290 bestRes = res;
291 }
292 continue;
293 }
294
295 if (best.isEmpty() || value > bestValue) {
296 if (best.isEmpty()) best.clear();
297 best.add(adept);
298 bestDummy = dummy;
299 bestValue = value;
300 bestRes = res;
301 } else if (bestValue == value) {
302 best.add(adept);
303 }
304 }
305
306 Enrollment conflict = ToolBox.random(best);
307 adepts.remove(conflict);
308 enrlWeight -= conflict.getRequest().getWeight();
309 conflicts.add(conflict);
310 }
311 }
312 }
313
314 /**
315 * A given enrollment is conflicting, if there is a section which
316 * limit(computed by
317 * {@link SectionLimit#getEnrollmentWeight(Section, Request)}) exceeds the
318 * section limit.
319 *
320 * @param enrollment
321 * {@link Enrollment} that is being considered
322 * @return true, if there is a section which will exceed its limit when the
323 * given enrollment is assigned
324 */
325 @Override
326 public boolean inConflict(Enrollment enrollment) {
327 // check reservation can assign over the limit
328 if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
329 enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
330 return false;
331
332 // exclude free time requests
333 if (!enrollment.isCourseRequest())
334 return false;
335
336 // for each section
337 for (Section section : enrollment.getSections()) {
338
339 // not have reservation -> check unreserved space
340 if (enrollment.getConfig().getOffering().hasReservations() &&
341 !hasSectionReservation(enrollment, section) && (
342 section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() ||
343 getUnreservedSpace(section, enrollment.getRequest()) < 0.0))
344 return true;
345
346 // unlimited section
347 if (section.getLimit() < 0)
348 continue;
349
350 // new enrollment weight
351 double enrlWeight = getEnrollmentWeight(section, enrollment.getRequest());
352
353 // above limit -> conflict
354 if (enrlWeight > section.getLimit())
355 return true;
356 }
357
358 // no conflicting section -> no conflict
359 return false;
360 }
361
362 @Override
363 public String toString() {
364 return "SectionLimit";
365 }
366 }