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