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