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 // exclude empty enrollmens 128 if (enrollment.getSections() == null || enrollment.getSections().isEmpty()) 129 return; 130 131 // no reservations 132 if (!config.getOffering().hasReservations()) 133 return; 134 135 // enrollment's reservation 136 Reservation reservation = enrollment.getReservation(); 137 138 // check space in the reservation reservation 139 if (reservation != null) { 140 // check reservation too 141 double reserved = reservation.getReservedAvailableSpace(assignment, enrollment.getRequest()); 142 143 if (reservation.getLimit() >= 0 && reserved < enrollment.getRequest().getWeight()) { 144 // reservation is not unlimited and there is not enough space in it 145 146 // try to free some space in the reservation 147 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 148 for (Enrollment e : config.getEnrollments(assignment)) { 149 if (e.getRequest().equals(enrollment.getRequest())) 150 continue; 151 if (!reservation.equals(e.getReservation())) 152 continue; 153 if (conflicts.contains(e)) 154 reserved += e.getRequest().getWeight(); 155 else 156 adepts.add(e); 157 } 158 159 while (reserved < enrollment.getRequest().getWeight()) { 160 if (adepts.isEmpty()) { 161 // no adepts -> enrollment cannot be assigned 162 conflicts.add(enrollment); 163 return; 164 } 165 166 // pick adept (prefer dummy students), decrease unreserved space, 167 // make conflict 168 List<Enrollment> best = new ArrayList<Enrollment>(); 169 boolean bestDummy = false; 170 double bestValue = 0; 171 for (Enrollment adept: adepts) { 172 boolean dummy = adept.getStudent().isDummy(); 173 double value = adept.toDouble(assignment, false); 174 175 if (iPreferDummyStudents && dummy != bestDummy) { 176 if (dummy) { 177 best.clear(); 178 best.add(adept); 179 bestDummy = dummy; 180 bestValue = value; 181 } 182 continue; 183 } 184 185 if (best.isEmpty() || value > bestValue) { 186 if (best.isEmpty()) best.clear(); 187 best.add(adept); 188 bestDummy = dummy; 189 bestValue = value; 190 } else if (bestValue == value) { 191 best.add(adept); 192 } 193 } 194 195 Enrollment conflict = ToolBox.random(best); 196 adepts.remove(conflict); 197 reserved += conflict.getRequest().getWeight(); 198 conflicts.add(conflict); 199 } 200 } 201 202 // if not configuration reservation -> check configuration unavailable space 203 if (!hasConfigReservation(enrollment)) { 204 // check reservation can assign over the limit 205 if (reservation.canBatchAssignOverLimit()) 206 return; 207 208 // check the total first (basically meaning that there will never be enough space in 209 // the section for an enrollment w/o configuration reservation 210 if (config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) { 211 conflicts.add(enrollment); 212 return; 213 } 214 215 double unreserved = getUnreservedSpace(assignment, config, enrollment.getRequest(), true); 216 217 if (unreserved < 0.0) { 218 // no unreserved space available -> cannot be assigned 219 // try to unassign some other enrollments that also do not have config reservation 220 221 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 222 for (Enrollment e : config.getEnrollments(assignment)) { 223 if (e.getRequest().equals(enrollment.getRequest())) 224 continue; 225 if (hasConfigReservation(e)) 226 continue; 227 if (conflicts.contains(e)) 228 unreserved += e.getRequest().getWeight(); 229 else 230 adepts.add(e); 231 } 232 233 while (unreserved < 0.0) { 234 if (adepts.isEmpty()) { 235 // no adepts -> enrollment cannot be assigned 236 conflicts.add(enrollment); 237 return; 238 } 239 240 // pick adept (prefer dummy students), decrease unreserved space, 241 // make conflict 242 List<Enrollment> best = new ArrayList<Enrollment>(); 243 boolean bestDummy = false; 244 double bestValue = 0; 245 for (Enrollment adept: adepts) { 246 boolean dummy = adept.getStudent().isDummy(); 247 double value = adept.toDouble(assignment, false); 248 249 if (iPreferDummyStudents && dummy != bestDummy) { 250 if (dummy) { 251 best.clear(); 252 best.add(adept); 253 bestDummy = dummy; 254 bestValue = value; 255 } 256 continue; 257 } 258 259 if (best.isEmpty() || value > bestValue) { 260 if (best.isEmpty()) best.clear(); 261 best.add(adept); 262 bestDummy = dummy; 263 bestValue = value; 264 } else if (bestValue == value) { 265 best.add(adept); 266 } 267 } 268 269 Enrollment conflict = ToolBox.random(best); 270 adepts.remove(conflict); 271 unreserved += conflict.getRequest().getWeight(); 272 conflicts.add(conflict); 273 } 274 } 275 } 276 } else { // no reservation at all 277 // check the total first (basically meaning that there will never be enough space in 278 // the section for an enrollment w/o reservation 279 if (config.getOffering().getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 280 config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) { 281 conflicts.add(enrollment); 282 return; 283 } 284 285 // check configuration unavailable space too 286 double unreserved = getUnreservedSpace(assignment, config, enrollment.getRequest(), false); 287 288 if (unreserved < 0.0) { 289 // no unreserved space available -> cannot be assigned 290 // try to unassign some other enrollments that also do not have reservation 291 292 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 293 for (Enrollment e : config.getEnrollments(assignment)) { 294 if (e.getRequest().equals(enrollment.getRequest())) 295 continue; 296 if (e.getReservation() != null) 297 continue; 298 if (conflicts.contains(e)) 299 unreserved += e.getRequest().getWeight(); 300 else 301 adepts.add(e); 302 } 303 304 while (unreserved < 0.0) { 305 if (adepts.isEmpty()) { 306 // no adepts -> enrollment cannot be assigned 307 conflicts.add(enrollment); 308 return; 309 } 310 311 // pick adept (prefer dummy students), decrease unreserved space, 312 // make conflict 313 List<Enrollment> best = new ArrayList<Enrollment>(); 314 boolean bestDummy = false; 315 double bestValue = 0; 316 for (Enrollment adept: adepts) { 317 boolean dummy = adept.getStudent().isDummy(); 318 double value = adept.toDouble(assignment, false); 319 320 if (iPreferDummyStudents && dummy != bestDummy) { 321 if (dummy) { 322 best.clear(); 323 best.add(adept); 324 bestDummy = dummy; 325 bestValue = value; 326 } 327 continue; 328 } 329 330 if (best.isEmpty() || value > bestValue) { 331 if (best.isEmpty()) best.clear(); 332 best.add(adept); 333 bestDummy = dummy; 334 bestValue = value; 335 } else if (bestValue == value) { 336 best.add(adept); 337 } 338 } 339 340 Enrollment conflict = ToolBox.random(best); 341 adepts.remove(conflict); 342 unreserved += conflict.getRequest().getWeight(); 343 conflicts.add(conflict); 344 } 345 } 346 } 347 } 348 349 /** 350 * True if the enrollment has reservation for this configuration. 351 **/ 352 private boolean hasConfigReservation(Enrollment enrollment) { 353 if (enrollment.getConfig() == null) return false; 354 Reservation reservation = enrollment.getReservation(); 355 if (reservation == null) return false; 356 return reservation.getConfigs().contains(enrollment.getConfig()); 357 } 358 359 360 /** 361 * A given enrollment is conflicting, if the config's enrollment (computed by 362 * {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)}) exceeds the 363 * limit. 364 * 365 * @param enrollment 366 * {@link Enrollment} that is being considered 367 * @return true, if the enrollment cannot be assigned without exceeding the limit 368 */ 369 @Override 370 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 371 // enrollment's config 372 Config config = enrollment.getConfig(); 373 374 // exclude free time requests 375 if (config == null) 376 return false; 377 378 // exclude empty enrollmens 379 if (enrollment.getSections() == null || enrollment.getSections().isEmpty()) 380 return false; 381 382 // enrollment's reservation 383 Reservation reservation = enrollment.getReservation(); 384 385 // check reservation 386 if (reservation != null) { 387 // unlimited reservation 388 if (reservation.getLimit() < 0) 389 return false; 390 391 // check remaning space 392 if (reservation.getReservedAvailableSpace(assignment, enrollment.getRequest()) < enrollment.getRequest().getWeight()) 393 return true; 394 395 // check reservation can assign over the limit 396 if (reservation.canBatchAssignOverLimit()) 397 return false; 398 399 // if not configuration reservation, check configuration unreserved space too 400 return (!hasConfigReservation(enrollment) && 401 getUnreservedSpace(assignment, config, enrollment.getRequest(), true) < 0.0); 402 } else { 403 // check unreserved space; 404 return config.getOffering().getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 405 config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 406 getUnreservedSpace(assignment, config, enrollment.getRequest(), false) < 0.0; 407 } 408 } 409 410 @Override 411 public String toString() { 412 return "ReservationLimit"; 413 } 414 415}