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