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