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.Enrollment; 013import org.cpsolver.studentsct.model.Request; 014import org.cpsolver.studentsct.model.Section; 015import org.cpsolver.studentsct.reservation.Reservation; 016 017 018/** 019 * Section limit constraint. This global constraint ensures that a limit of each 020 * section is not exceeded. This means that the total sum of weights of course 021 * requests (see {@link Request#getWeight()}) enrolled into a section is below 022 * the section's limit (see {@link Section#getLimit()}). 023 * 024 * <br> 025 * <br> 026 * Sections with negative limit are considered unlimited, and therefore 027 * completely ignored by this constraint. 028 * 029 * <br> 030 * <br> 031 * This constraint also check section reservations. 032 * 033 * <br> 034 * <br> 035 * Parameters: 036 * <table border='1' summary='Related Solver Parameters'> 037 * <tr> 038 * <th>Parameter</th> 039 * <th>Type</th> 040 * <th>Comment</th> 041 * </tr> 042 * <tr> 043 * <td>SectionLimit.PreferDummyStudents</td> 044 * <td>{@link Boolean}</td> 045 * <td>If true, requests of dummy (last-like) students are preferred to be 046 * selected as conflicting.</td> 047 * </tr> 048 * </table> 049 * <br> 050 * <br> 051 * 052 * @version StudentSct 1.3 (Student Sectioning)<br> 053 * Copyright (C) 2007 - 2014 Tomas Muller<br> 054 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 055 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 056 * <br> 057 * This library is free software; you can redistribute it and/or modify 058 * it under the terms of the GNU Lesser General Public License as 059 * published by the Free Software Foundation; either version 3 of the 060 * License, or (at your option) any later version. <br> 061 * <br> 062 * This library is distributed in the hope that it will be useful, but 063 * WITHOUT ANY WARRANTY; without even the implied warranty of 064 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 065 * Lesser General Public License for more details. <br> 066 * <br> 067 * You should have received a copy of the GNU Lesser General Public 068 * License along with this library; if not see 069 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 070 */ 071public class SectionLimit extends GlobalConstraint<Request, Enrollment> { 072 private static double sNominalWeight = 0.00001; 073 private boolean iPreferDummyStudents = false; 074 075 /** 076 * Constructor 077 * 078 * @param cfg 079 * solver configuration 080 */ 081 public SectionLimit(DataProperties cfg) { 082 super(); 083 iPreferDummyStudents = cfg.getPropertyBoolean("SectionLimit.PreferDummyStudents", false); 084 } 085 086 /** 087 * Enrollment weight of a section if the given request is assigned. In order 088 * to overcome rounding problems with last-like students ( e.g., 5 students 089 * are projected to two sections of limit 2 -- each section can have up to 3 090 * of these last-like students), the weight of the request with the highest 091 * weight in the section is changed to a small nominal weight. 092 * 093 * @param assignment current assignment 094 * @param section 095 * a section that is of concern 096 * @param request 097 * a request of a student to be assigned containing the given 098 * section 099 * @return section's new weight 100 */ 101 public static double getEnrollmentWeight(Assignment<Request, Enrollment> assignment, Section section, Request request) { 102 return section.getEnrollmentWeight(assignment, request) + request.getWeight() - Math.max(section.getMaxEnrollmentWeight(assignment), request.getWeight()) + sNominalWeight; 103 } 104 105 /** 106 * Remaining unreserved space in a section if the given request is assigned. In order 107 * to overcome rounding problems with last-like students ( e.g., 5 students 108 * are projected to two sections of limit 2 -- each section can have up to 3 109 * of these last-like students), the weight of the request with the highest 110 * weight in the section is changed to a small nominal weight. 111 * 112 * @param assignment current assignment 113 * @param section 114 * a section that is of concern 115 * @param request 116 * a request of a student to be assigned containing the given 117 * section 118 * @return section's new unreserved space 119 */ 120 public static double getUnreservedSpace(Assignment<Request, Enrollment> assignment, Section section, Request request) { 121 return section.getUnreservedSpace(assignment, request) - request.getWeight() + Math.max(section.getMaxEnrollmentWeight(assignment), request.getWeight()) - sNominalWeight; 122 } 123 124 125 /** 126 * True if the enrollment has reservation for this section. 127 * Everything else is checked in the {@link ReservationLimit} constraint. 128 **/ 129 private boolean hasSectionReservation(Enrollment enrollment, Section section) { 130 Reservation reservation = enrollment.getReservation(); 131 if (reservation == null) return false; 132 Set<Section> sections = reservation.getSections(section.getSubpart()); 133 return sections != null && sections.contains(section); 134 } 135 136 /** 137 * A given enrollment is conflicting, if there is a section which limit 138 * (computed by {@link SectionLimit#getEnrollmentWeight(Assignment, Section, Request)}) 139 * exceeds the section limit. <br> 140 * For each of such sections, one or more existing enrollments are 141 * (randomly) selected as conflicting until the overall weight is under the 142 * limit. 143 * 144 * @param enrollment 145 * {@link Enrollment} that is being considered 146 * @param conflicts 147 * all computed conflicting requests are added into this set 148 */ 149 @Override 150 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) { 151 // check reservation can assign over the limit 152 if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() && 153 enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit()) 154 return; 155 156 // exclude free time requests 157 if (!enrollment.isCourseRequest()) 158 return; 159 160 // for each section 161 for (Section section : enrollment.getSections()) { 162 163 // no reservation -- check the space in the unreserved space in the section 164 if (enrollment.getConfig().getOffering().hasReservations() && !hasSectionReservation(enrollment, section)) { 165 // section is fully reserved by section reservations 166 if (section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) { 167 conflicts.add(enrollment); 168 return; 169 } 170 171 double unreserved = getUnreservedSpace(assignment, section, enrollment.getRequest()); 172 173 if (unreserved < 0.0) { 174 // no unreserved space available -> cannot be assigned 175 // try to unassign some other enrollments that also do not have reservation 176 177 List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments(assignment).size()); 178 for (Enrollment e : section.getEnrollments(assignment)) { 179 if (e.getRequest().equals(enrollment.getRequest())) 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 (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() && 331 enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit()) 332 return false; 333 334 // exclude free time requests 335 if (!enrollment.isCourseRequest()) 336 return false; 337 338 // for each section 339 for (Section section : enrollment.getSections()) { 340 341 // not have reservation -> check unreserved space 342 if (enrollment.getConfig().getOffering().hasReservations() && 343 !hasSectionReservation(enrollment, section) && ( 344 section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 345 getUnreservedSpace(assignment, section, enrollment.getRequest()) < 0.0)) 346 return true; 347 348 // unlimited section 349 if (section.getLimit() < 0) 350 continue; 351 352 // new enrollment weight 353 double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest()); 354 355 // above limit -> conflict 356 if (enrlWeight > section.getLimit()) 357 return true; 358 } 359 360 // no conflicting section -> no conflict 361 return false; 362 } 363 364 @Override 365 public String toString() { 366 return "SectionLimit"; 367 } 368}