001package net.sf.cpsolver.studentsct.constraint; 002 003import java.util.ArrayList; 004import java.util.List; 005import java.util.Set; 006 007import net.sf.cpsolver.ifs.model.GlobalConstraint; 008import net.sf.cpsolver.ifs.util.DataProperties; 009import net.sf.cpsolver.ifs.util.ToolBox; 010import net.sf.cpsolver.studentsct.StudentSectioningModel; 011import net.sf.cpsolver.studentsct.model.Config; 012import net.sf.cpsolver.studentsct.model.Enrollment; 013import net.sf.cpsolver.studentsct.model.Request; 014import 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 Tomáš Müller<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 */ 061public 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}