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.studentsct.constraint.ConfigLimit.Adepts; 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 Tomáš Müller<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 private boolean iPreferPriorityStudents = true; 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 iPreferPriorityStudents = cfg.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 077 } 078 079 080 /** 081 * Remaining unreserved space in a config if the given request is assigned. In order 082 * to overcome rounding problems with last-like students ( e.g., 5 students 083 * are projected to two sections of limit 2 -- each section can have up to 3 084 * of these last-like students), the weight of the request with the highest 085 * weight in the section is changed to a small nominal weight. 086 * 087 * @param assignment current assignment 088 * @param config 089 * a config that is of concern 090 * @param request 091 * a request of a student to be assigned containing the given 092 * section 093 * @param hasReservation 094 * true if the enrollment in question has a reservation (only not matching the given configuration) 095 * @return config's new unreserved space 096 */ 097 public static double getUnreservedSpace(Assignment<Request, Enrollment> assignment, Config config, Request request, boolean hasReservation) { 098 if (hasReservation) // only check the config's unreserved space 099 return config.getUnreservedSpace(assignment, request) - request.getWeight() + Math.max(config.getMaxEnrollmentWeight(assignment), request.getWeight()) - sNominalWeight; 100 else // no reservation -- also check offering's unreserved space 101 return Math.min(config.getUnreservedSpace(assignment, request), config.getOffering().getUnreservedSpace(assignment, request)) 102 - request.getWeight() + Math.max(config.getMaxEnrollmentWeight(assignment), request.getWeight()) - sNominalWeight; 103 } 104 105 106 /** 107 * A given enrollment is conflicting, if the reservation's remaining available space 108 * (computed by {@link Reservation#getReservedAvailableSpace(Assignment, Request)}) 109 * is below the requests weight {@link Request#getWeight()}. <br> 110 * If the limit is breached, one or more existing enrollments are 111 * selected as conflicting until there is enough space in the reservation. 112 * Similarly, if the enrollment does not have the reservation, it is checked 113 * that there is enough unreserved space in the desired configuration. 114 * 115 * @param enrollment 116 * {@link Enrollment} that is being considered 117 * @param conflicts 118 * all computed conflicting requests are added into this set 119 */ 120 @Override 121 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) { 122 // enrollment's config 123 Config config = enrollment.getConfig(); 124 125 // exclude free time requests 126 if (config == null) 127 return; 128 129 // exclude empty enrollmens 130 if (enrollment.getSections() == null || enrollment.getSections().isEmpty()) 131 return; 132 133 // no reservations 134 if (!config.getOffering().hasReservations()) 135 return; 136 137 // enrollment's reservation 138 Reservation reservation = enrollment.getReservation(); 139 140 // check space in the reservation reservation 141 if (reservation != null) { 142 // check reservation too 143 double reserved = reservation.getReservedAvailableSpace(assignment, enrollment.getRequest()); 144 145 if (reservation.getLimit() >= 0 && reserved < enrollment.getRequest().getWeight()) { 146 // reservation is not unlimited and there is not enough space in it 147 148 // try to free some space in the reservation 149 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 150 for (Enrollment e : config.getEnrollments(assignment)) { 151 if (e.getRequest().equals(enrollment.getRequest())) 152 continue; 153 if (!reservation.equals(e.getReservation())) 154 continue; 155 if (conflicts.contains(e)) 156 reserved += e.getRequest().getWeight(); 157 else 158 adepts.add(e); 159 } 160 161 while (reserved < enrollment.getRequest().getWeight()) { 162 if (adepts.isEmpty()) { 163 // no adepts -> enrollment cannot be assigned 164 conflicts.add(enrollment); 165 return; 166 } 167 168 // pick adept (prefer dummy students), decrease unreserved space, 169 // make conflict 170 Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get(); 171 adepts.remove(conflict); 172 reserved += conflict.getRequest().getWeight(); 173 conflicts.add(conflict); 174 } 175 } 176 177 // if not configuration reservation -> check configuration unavailable space 178 if (!hasConfigReservation(enrollment)) { 179 // check reservation can assign over the limit 180 if (reservation.canBatchAssignOverLimit()) 181 return; 182 183 // check the total first (basically meaning that there will never be enough space in 184 // the section for an enrollment w/o configuration reservation 185 if (config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) { 186 conflicts.add(enrollment); 187 return; 188 } 189 190 double unreserved = getUnreservedSpace(assignment, config, enrollment.getRequest(), true); 191 192 if (unreserved < 0.0) { 193 // no unreserved space available -> cannot be assigned 194 // try to unassign some other enrollments that also do not have config reservation 195 196 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 197 for (Enrollment e : config.getEnrollments(assignment)) { 198 if (e.getRequest().equals(enrollment.getRequest())) 199 continue; 200 if (hasConfigReservation(e)) 201 continue; 202 if (conflicts.contains(e)) 203 unreserved += e.getRequest().getWeight(); 204 else 205 adepts.add(e); 206 } 207 208 while (unreserved < 0.0) { 209 if (adepts.isEmpty()) { 210 // no adepts -> enrollment cannot be assigned 211 conflicts.add(enrollment); 212 return; 213 } 214 215 // pick adept (prefer dummy students), decrease unreserved space, 216 // make conflict 217 Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get(); 218 adepts.remove(conflict); 219 unreserved += conflict.getRequest().getWeight(); 220 conflicts.add(conflict); 221 } 222 } 223 } 224 } else { // no reservation at all 225 // check the total first (basically meaning that there will never be enough space in 226 // the section for an enrollment w/o reservation 227 if (config.getOffering().getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 228 config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) { 229 conflicts.add(enrollment); 230 return; 231 } 232 233 // check configuration unavailable space too 234 double unreserved = getUnreservedSpace(assignment, config, enrollment.getRequest(), false); 235 236 if (unreserved < 0.0) { 237 // no unreserved space available -> cannot be assigned 238 // try to unassign some other enrollments that also do not have reservation 239 240 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 241 for (Enrollment e : config.getEnrollments(assignment)) { 242 if (e.getRequest().equals(enrollment.getRequest())) 243 continue; 244 if (e.getReservation() != null) 245 continue; 246 if (conflicts.contains(e)) 247 unreserved += e.getRequest().getWeight(); 248 else 249 adepts.add(e); 250 } 251 252 while (unreserved < 0.0) { 253 if (adepts.isEmpty()) { 254 // no adepts -> enrollment cannot be assigned 255 conflicts.add(enrollment); 256 return; 257 } 258 259 // pick adept (prefer dummy students), decrease unreserved space, 260 // make conflict 261 Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get(); 262 adepts.remove(conflict); 263 unreserved += conflict.getRequest().getWeight(); 264 conflicts.add(conflict); 265 } 266 } 267 } 268 } 269 270 /** 271 * True if the enrollment has reservation for this configuration. 272 **/ 273 private boolean hasConfigReservation(Enrollment enrollment) { 274 if (enrollment.getConfig() == null) return false; 275 Reservation reservation = enrollment.getReservation(); 276 if (reservation == null) return false; 277 return reservation.getConfigs().contains(enrollment.getConfig()); 278 } 279 280 281 /** 282 * A given enrollment is conflicting, if the config's enrollment (computed by 283 * {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)}) exceeds the 284 * limit. 285 * 286 * @param enrollment 287 * {@link Enrollment} that is being considered 288 * @return true, if the enrollment cannot be assigned without exceeding the limit 289 */ 290 @Override 291 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 292 // enrollment's config 293 Config config = enrollment.getConfig(); 294 295 // exclude free time requests 296 if (config == null) 297 return false; 298 299 // exclude empty enrollmens 300 if (enrollment.getSections() == null || enrollment.getSections().isEmpty()) 301 return false; 302 303 // enrollment's reservation 304 Reservation reservation = enrollment.getReservation(); 305 306 // check reservation 307 if (reservation != null) { 308 // unlimited reservation 309 if (reservation.getLimit() < 0) 310 return false; 311 312 // check remaning space 313 if (reservation.getReservedAvailableSpace(assignment, enrollment.getRequest()) < enrollment.getRequest().getWeight()) 314 return true; 315 316 // check reservation can assign over the limit 317 if (reservation.canBatchAssignOverLimit()) 318 return false; 319 320 // if not configuration reservation, check configuration unreserved space too 321 return (!hasConfigReservation(enrollment) && 322 getUnreservedSpace(assignment, config, enrollment.getRequest(), true) < 0.0); 323 } else { 324 // check unreserved space; 325 return config.getOffering().getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 326 config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 327 getUnreservedSpace(assignment, config, enrollment.getRequest(), false) < 0.0; 328 } 329 } 330 331 @Override 332 public String toString() { 333 return "ReservationLimit"; 334 } 335 336}