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 (hasSectionReservation(e, section)) 180 continue; 181 if (conflicts.contains(e)) 182 unreserved += e.getRequest().getWeight(); 183 else 184 adepts.add(e); 185 } 186 187 while (unreserved < 0.0) { 188 if (adepts.isEmpty()) { 189 // no adepts -> enrollment cannot be assigned 190 conflicts.add(enrollment); 191 return; 192 } 193 194 // pick adept (prefer dummy students), decrease unreserved space, 195 // make conflict 196 List<Enrollment> best = new ArrayList<Enrollment>(); 197 boolean bestDummy = false; 198 double bestValue = 0; 199 for (Enrollment adept: adepts) { 200 boolean dummy = adept.getStudent().isDummy(); 201 double value = adept.toDouble(assignment, false); 202 203 if (iPreferDummyStudents && dummy != bestDummy) { 204 if (dummy) { 205 best.clear(); 206 best.add(adept); 207 bestDummy = dummy; 208 bestValue = value; 209 } 210 continue; 211 } 212 213 if (best.isEmpty() || value > bestValue) { 214 if (best.isEmpty()) best.clear(); 215 best.add(adept); 216 bestDummy = dummy; 217 bestValue = value; 218 } else if (bestValue == value) { 219 best.add(adept); 220 } 221 } 222 223 Enrollment conflict = ToolBox.random(best); 224 adepts.remove(conflict); 225 unreserved += conflict.getRequest().getWeight(); 226 conflicts.add(conflict); 227 } 228 } 229 } 230 231 // unlimited section 232 if (section.getLimit() < 0) 233 continue; 234 235 // new enrollment weight 236 double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest()); 237 238 // below limit -> ok 239 if (enrlWeight <= section.getLimit()) 240 continue; 241 242 // above limit -> compute adepts (current assignments that are not 243 // yet conflicting) exclude all conflicts as well 244 List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments(assignment).size()); 245 for (Enrollment e : section.getEnrollments(assignment)) { 246 if (e.getRequest().equals(enrollment.getRequest())) 247 continue; 248 if (conflicts.contains(e)) 249 enrlWeight -= e.getRequest().getWeight(); 250 else 251 adepts.add(e); 252 } 253 254 // while above limit -> pick an adept and make it conflicting 255 while (enrlWeight > section.getLimit()) { 256 if (adepts.isEmpty()) { 257 // no adepts -> enrollment cannot be assigned 258 conflicts.add(enrollment); 259 return; 260 } 261 262 // pick adept (prefer dummy students & students w/o reservation), decrease enrollment 263 // weight, make conflict 264 List<Enrollment> best = new ArrayList<Enrollment>(); 265 boolean bestDummy = false; 266 double bestValue = 0; 267 boolean bestRes = true; 268 for (Enrollment adept: adepts) { 269 boolean dummy = adept.getStudent().isDummy(); 270 double value = adept.toDouble(assignment, false); 271 boolean res = hasSectionReservation(adept, section); 272 273 if (iPreferDummyStudents && dummy != bestDummy) { 274 if (dummy) { 275 best.clear(); 276 best.add(adept); 277 bestDummy = dummy; 278 bestValue = value; 279 bestRes = res; 280 } 281 continue; 282 } 283 284 if (bestRes != res) { 285 if (!res) { 286 best.clear(); 287 best.add(adept); 288 bestDummy = dummy; 289 bestValue = value; 290 bestRes = res; 291 } 292 continue; 293 } 294 295 if (best.isEmpty() || value > bestValue) { 296 if (best.isEmpty()) best.clear(); 297 best.add(adept); 298 bestDummy = dummy; 299 bestValue = value; 300 bestRes = res; 301 } else if (bestValue == value) { 302 best.add(adept); 303 } 304 } 305 306 Enrollment conflict = ToolBox.random(best); 307 adepts.remove(conflict); 308 enrlWeight -= conflict.getRequest().getWeight(); 309 conflicts.add(conflict); 310 } 311 } 312 } 313 314 /** 315 * A given enrollment is conflicting, if there is a section which 316 * limit(computed by 317 * {@link SectionLimit#getEnrollmentWeight(Assignment, Section, Request)}) exceeds the 318 * section limit. 319 * 320 * @param enrollment 321 * {@link Enrollment} that is being considered 322 * @return true, if there is a section which will exceed its limit when the 323 * given enrollment is assigned 324 */ 325 @Override 326 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 327 // check reservation can assign over the limit 328 if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit()) 329 return false; 330 331 // exclude free time requests 332 if (!enrollment.isCourseRequest()) 333 return false; 334 335 // for each section 336 for (Section section : enrollment.getSections()) { 337 338 // not have reservation -> check unreserved space 339 if (enrollment.getConfig().getOffering().hasReservations() && 340 !hasSectionReservation(enrollment, section) && ( 341 section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 342 getUnreservedSpace(assignment, section, enrollment.getRequest()) < 0.0)) 343 return true; 344 345 // unlimited section 346 if (section.getLimit() < 0) 347 continue; 348 349 // new enrollment weight 350 double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest()); 351 352 // above limit -> conflict 353 if (enrlWeight > section.getLimit()) 354 return true; 355 } 356 357 // no conflicting section -> no conflict 358 return false; 359 } 360 361 @Override 362 public String toString() { 363 return "SectionLimit"; 364 } 365}