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