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.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 Tomáš Müller<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 private boolean iPreferPriorityStudents = true; 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 iPreferPriorityStudents = cfg.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 085 } 086 087 /** 088 * Enrollment weight of a section if the given request is assigned. In order 089 * to overcome rounding problems with last-like students ( e.g., 5 students 090 * are projected to two sections of limit 2 -- each section can have up to 3 091 * of these last-like students), the weight of the request with the highest 092 * weight in the section is changed to a small nominal weight. 093 * 094 * @param assignment current assignment 095 * @param section 096 * a section that is of concern 097 * @param request 098 * a request of a student to be assigned containing the given 099 * section 100 * @return section's new weight 101 */ 102 public static double getEnrollmentWeight(Assignment<Request, Enrollment> assignment, Section section, Request request) { 103 return section.getEnrollmentWeight(assignment, request) + request.getWeight() - Math.max(section.getMaxEnrollmentWeight(assignment), request.getWeight()) + sNominalWeight; 104 } 105 106 /** 107 * Remaining unreserved space in a section if the given request is assigned. In order 108 * to overcome rounding problems with last-like students ( e.g., 5 students 109 * are projected to two sections of limit 2 -- each section can have up to 3 110 * of these last-like students), the weight of the request with the highest 111 * weight in the section is changed to a small nominal weight. 112 * 113 * @param assignment current assignment 114 * @param section 115 * a section that is of concern 116 * @param request 117 * a request of a student to be assigned containing the given 118 * section 119 * @return section's new unreserved space 120 */ 121 public static double getUnreservedSpace(Assignment<Request, Enrollment> assignment, Section section, Request request) { 122 return section.getUnreservedSpace(assignment, request) - request.getWeight() + Math.max(section.getMaxEnrollmentWeight(assignment), request.getWeight()) - sNominalWeight; 123 } 124 125 126 /** 127 * True if the enrollment has reservation for this section. 128 * Everything else is checked in the {@link ReservationLimit} constraint. 129 **/ 130 private boolean hasSectionReservation(Enrollment enrollment, Section section) { 131 Reservation reservation = enrollment.getReservation(); 132 if (reservation == null) return false; 133 Set<Section> sections = reservation.getSections(section.getSubpart()); 134 return sections != null && sections.contains(section); 135 } 136 137 /** 138 * A given enrollment is conflicting, if there is a section which limit 139 * (computed by {@link SectionLimit#getEnrollmentWeight(Assignment, Section, Request)}) 140 * exceeds the section limit. <br> 141 * For each of such sections, one or more existing enrollments are 142 * (randomly) selected as conflicting until the overall weight is under the 143 * limit. 144 * 145 * @param enrollment 146 * {@link Enrollment} that is being considered 147 * @param conflicts 148 * all computed conflicting requests are added into this set 149 */ 150 @Override 151 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) { 152 // check reservation can assign over the limit 153 if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit()) 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 (e.getReservation() != null && e.getReservation().canBatchAssignOverLimit()) 182 continue; 183 if (hasSectionReservation(e, section)) 184 continue; 185 if (conflicts.contains(e)) 186 unreserved += e.getRequest().getWeight(); 187 else 188 adepts.add(e); 189 } 190 191 while (unreserved < 0.0) { 192 if (adepts.isEmpty()) { 193 // no adepts -> enrollment cannot be assigned 194 conflicts.add(enrollment); 195 return; 196 } 197 198 // pick adept (prefer dummy students), decrease unreserved space, 199 // make conflict 200 Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get(); 201 adepts.remove(conflict); 202 unreserved += conflict.getRequest().getWeight(); 203 conflicts.add(conflict); 204 } 205 } 206 } 207 208 // unlimited section 209 if (section.getLimit() < 0) 210 continue; 211 212 // new enrollment weight 213 double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest()); 214 215 // below limit -> ok 216 if (enrlWeight <= section.getLimit()) 217 continue; 218 219 // above limit -> compute adepts (current assignments that are not 220 // yet conflicting) exclude all conflicts as well 221 List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments(assignment).size()); 222 for (Enrollment e : section.getEnrollments(assignment)) { 223 if (e.getRequest().equals(enrollment.getRequest())) 224 continue; 225 if (conflicts.contains(e)) 226 enrlWeight -= e.getRequest().getWeight(); 227 else 228 adepts.add(e); 229 } 230 231 // while above limit -> pick an adept and make it conflicting 232 while (enrlWeight > section.getLimit()) { 233 if (adepts.isEmpty()) { 234 // no adepts -> enrollment cannot be assigned 235 conflicts.add(enrollment); 236 return; 237 } 238 239 // pick adept (prefer dummy students & students w/o reservation), decrease enrollment 240 // weight, make conflict 241 Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get(); 242 adepts.remove(conflict); 243 enrlWeight -= conflict.getRequest().getWeight(); 244 conflicts.add(conflict); 245 } 246 } 247 } 248 249 /** 250 * A given enrollment is conflicting, if there is a section which 251 * limit(computed by 252 * {@link SectionLimit#getEnrollmentWeight(Assignment, Section, Request)}) exceeds the 253 * section limit. 254 * 255 * @param enrollment 256 * {@link Enrollment} that is being considered 257 * @return true, if there is a section which will exceed its limit when the 258 * given enrollment is assigned 259 */ 260 @Override 261 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 262 // check reservation can assign over the limit 263 if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit()) 264 return false; 265 266 // exclude free time requests 267 if (!enrollment.isCourseRequest()) 268 return false; 269 270 // for each section 271 for (Section section : enrollment.getSections()) { 272 273 // not have reservation -> check unreserved space 274 if (enrollment.getConfig().getOffering().hasReservations() && 275 !hasSectionReservation(enrollment, section) && ( 276 section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 277 getUnreservedSpace(assignment, section, enrollment.getRequest()) < 0.0)) 278 return true; 279 280 // unlimited section 281 if (section.getLimit() < 0) 282 continue; 283 284 // new enrollment weight 285 double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest()); 286 287 // above limit -> conflict 288 if (enrlWeight > section.getLimit()) 289 return true; 290 } 291 292 // no conflicting section -> no conflict 293 return false; 294 } 295 296 @Override 297 public String toString() { 298 return "SectionLimit"; 299 } 300}