001package org.cpsolver.studentsct.constraint; 002 003import java.util.ArrayList; 004import java.util.Collection; 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.Config; 012import org.cpsolver.studentsct.model.Enrollment; 013import org.cpsolver.studentsct.model.Request; 014import org.cpsolver.studentsct.model.Request.RequestPriority; 015import org.cpsolver.studentsct.model.Student.StudentPriority; 016 017 018/** 019 * Configuration limit constraint. This global constraint ensures that a limit of each 020 * configuration is not exceeded. This means that the total sum of weights of course 021 * requests (see {@link Request#getWeight()}) enrolled into a configuration is below 022 * the configuration's limit (see {@link Config#getLimit()}). 023 * 024 * <br> 025 * <br> 026 * Configurations with negative limit are considered unlimited, and therefore 027 * completely ignored by this constraint. 028 * 029 * <br> 030 * <br> 031 * Parameters: 032 * <table border='1' summary='Related Solver Parameters'> 033 * <tr> 034 * <th>Parameter</th> 035 * <th>Type</th> 036 * <th>Comment</th> 037 * </tr> 038 * <tr> 039 * <td>ConfigLimit.PreferDummyStudents</td> 040 * <td>{@link Boolean}</td> 041 * <td>If true, requests of dummy (last-like) students are preferred to be 042 * selected as conflicting.</td> 043 * </tr> 044 * </table> 045 * <br> 046 * <br> 047 * 048 * @version StudentSct 1.3 (Student Sectioning)<br> 049 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 050 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 051 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 052 * <br> 053 * This library is free software; you can redistribute it and/or modify 054 * it under the terms of the GNU Lesser General Public License as 055 * published by the Free Software Foundation; either version 3 of the 056 * License, or (at your option) any later version. <br> 057 * <br> 058 * This library is distributed in the hope that it will be useful, but 059 * WITHOUT ANY WARRANTY; without even the implied warranty of 060 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 061 * Lesser General Public License for more details. <br> 062 * <br> 063 * You should have received a copy of the GNU Lesser General Public 064 * License along with this library; if not see 065 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 066 */ 067public class ConfigLimit extends GlobalConstraint<Request, Enrollment> { 068 069 private static double sNominalWeight = 0.00001; 070 private boolean iPreferDummyStudents = false; 071 private boolean iPreferPriorityStudents = true; 072 073 /** 074 * Constructor 075 * 076 * @param cfg 077 * solver configuration 078 */ 079 public ConfigLimit(DataProperties cfg) { 080 super(); 081 iPreferDummyStudents = cfg.getPropertyBoolean("ConfigLimit.PreferDummyStudents", false); 082 iPreferPriorityStudents = cfg.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 083 } 084 085 086 /** 087 * Enrollment weight of a config 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 configs 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 config is changed to a small nominal weight. 092 * 093 * @param assignment current assignment 094 * @param config 095 * a config 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, Config config, Request request) { 102 return config.getEnrollmentWeight(assignment, request) + request.getWeight() - Math.max(config.getMaxEnrollmentWeight(assignment), request.getWeight()) + sNominalWeight; 103 } 104 105 /** 106 * A given enrollment is conflicting, if the config's enrollment 107 * (computed by {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)}) 108 * exceeds the limit. <br> 109 * If the limit is breached, one or more existing enrollments are 110 * (randomly) selected as conflicting until the overall weight is under the 111 * limit. 112 * 113 * @param enrollment 114 * {@link Enrollment} that is being considered 115 * @param conflicts 116 * all computed conflicting requests are added into this set 117 */ 118 @Override 119 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) { 120 // check reservation can assign over the limit 121 if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit()) 122 return; 123 124 // enrollment's config 125 Config config = enrollment.getConfig(); 126 127 // exclude free time requests 128 if (config == null) 129 return; 130 131 // exclude empty enrollmens 132 if (enrollment.getSections() == null || enrollment.getSections().isEmpty()) 133 return; 134 135 // unlimited config 136 if (config.getLimit() < 0) 137 return; 138 139 // new enrollment weight 140 double enrlWeight = getEnrollmentWeight(assignment, config, enrollment.getRequest()); 141 142 // below limit -> ok 143 if (enrlWeight <= config.getLimit()) 144 return; 145 146 // above limit -> compute adepts (current assignments that are not 147 // yet conflicting) 148 // exclude all conflicts as well 149 ArrayList<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size()); 150 for (Enrollment e : config.getEnrollments(assignment)) { 151 if (e.getRequest().equals(enrollment.getRequest())) 152 continue; 153 if (e.getReservation() != null && e.getReservation().canBatchAssignOverLimit()) 154 continue; 155 if (conflicts.contains(e)) 156 enrlWeight -= e.getRequest().getWeight(); 157 else 158 adepts.add(e); 159 } 160 161 // while above limit -> pick an adept and make it conflicting 162 while (enrlWeight > config.getLimit()) { 163 if (adepts.isEmpty()) { 164 // no adepts -> enrollment cannot be assigned 165 conflicts.add(enrollment); 166 return; 167 } 168 169 // pick adept (prefer dummy students & students w/o reservation), decrease enrollment 170 // weight, make conflict 171 Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get(); 172 adepts.remove(conflict); 173 enrlWeight -= conflict.getRequest().getWeight(); 174 conflicts.add(conflict); 175 } 176 } 177 178 /** 179 * A given enrollment is conflicting, if the config's enrollment (computed by 180 * {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)}) exceeds the 181 * limit. 182 * 183 * @param enrollment 184 * {@link Enrollment} that is being considered 185 * @return true, if the enrollment cannot be assigned without exceeding the limit 186 */ 187 @Override 188 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 189 // check reservation can assign over the limit 190 if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit()) 191 return false; 192 193 // enrollment's config 194 Config config = enrollment.getConfig(); 195 196 // exclude free time requests 197 if (config == null) 198 return false; 199 200 // exclude empty enrollmens 201 if (enrollment.getSections() == null || enrollment.getSections().isEmpty()) 202 return false; 203 204 // unlimited config 205 if (config.getLimit() < 0) 206 return false; 207 208 // new enrollment weight 209 double enrlWeight = getEnrollmentWeight(assignment, config, enrollment.getRequest()); 210 211 // above limit -> conflict 212 return (enrlWeight > config.getLimit()); 213 } 214 215 @Override 216 public String toString() { 217 return "ConfigLimit"; 218 } 219 220 /** 221 * Support class to pick an adept (prefer dummy students & students w/o reservation) 222 */ 223 static class Adepts { 224 private ArrayList<Enrollment> iEnrollments; 225 private double iValue; 226 private boolean iDummy; 227 private StudentPriority iPriority; 228 private RequestPriority iRequestPriority; 229 private boolean iReservation; 230 private boolean iConsiderDummy; 231 private boolean iPriorityFirst; 232 233 public Adepts(boolean preferDummy, boolean priorityFirst) { 234 iConsiderDummy = preferDummy; 235 iPriorityFirst = priorityFirst; 236 iEnrollments = new ArrayList<Enrollment>(); 237 } 238 239 public Adepts(boolean preferDummy, boolean priorityFirst, int size) { 240 iConsiderDummy = preferDummy; 241 iPriorityFirst = priorityFirst; 242 iEnrollments = new ArrayList<Enrollment>(size); 243 } 244 245 public Adepts(boolean preferDummy, boolean priorityFirst, Collection<Enrollment> adepts, Assignment<Request, Enrollment> assignment) { 246 iConsiderDummy = preferDummy; 247 iPriorityFirst = priorityFirst; 248 iEnrollments = new ArrayList<Enrollment>(adepts.size()); 249 for (Enrollment adept: adepts) 250 add(adept, assignment); 251 } 252 253 public void add(Enrollment enrollment, Assignment<Request, Enrollment> assignment) { 254 double value = enrollment.toDouble(assignment, false); 255 boolean dummy = enrollment.getStudent().isDummy(); 256 StudentPriority priority = enrollment.getStudent().getPriority(); 257 boolean reservation = (enrollment.getReservation() != null); 258 RequestPriority rp = enrollment.getRequest().getRequestPriority(); 259 if (iEnrollments.isEmpty()) { // no adepts yet 260 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 261 iEnrollments.add(enrollment); 262 return; 263 } 264 if (iConsiderDummy && iDummy != dummy) { // different dummy 265 if (!dummy) return; // ignore not-dummy students 266 iEnrollments.clear(); 267 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 268 iEnrollments.add(enrollment); 269 return; 270 } 271 if (iPriorityFirst) { 272 if (iPriority != priority) { // different priority 273 if (priority.ordinal() < iPriority.ordinal()) return; // ignore more priority students 274 iEnrollments.clear(); 275 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 276 iEnrollments.add(enrollment); 277 return; 278 } 279 if (iRequestPriority != rp) { // different request priority 280 if (rp.ordinal() < iRequestPriority.ordinal()) return; // ignore more critical courses 281 iEnrollments.clear(); 282 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 283 iEnrollments.add(enrollment); 284 return; 285 } 286 } else { 287 if (iRequestPriority != rp) { // different request priority 288 if (rp.ordinal() < iRequestPriority.ordinal()) return; // ignore more critical courses 289 iEnrollments.clear(); 290 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 291 iEnrollments.add(enrollment); 292 return; 293 } 294 if (iPriority != priority) { // different priority 295 if (priority.ordinal() < iPriority.ordinal()) return; // ignore more priority students 296 iEnrollments.clear(); 297 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 298 iEnrollments.add(enrollment); 299 return; 300 } 301 } 302 if (iReservation != reservation) { // different reservation 303 if (reservation) return; // ignore students with reservation 304 iEnrollments.clear(); 305 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 306 iEnrollments.add(enrollment); 307 return; 308 } 309 // prefer requests with higher value (lower priority) 310 if (value > iValue) { 311 iEnrollments.clear(); 312 iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation; 313 iEnrollments.add(enrollment); 314 } else if (value == iValue) { 315 iEnrollments.add(enrollment); 316 } 317 } 318 319 public Enrollment get() { 320 if (iEnrollments.isEmpty()) return null; 321 return ToolBox.random(iEnrollments); 322 } 323 324 public boolean isEmpty() { 325 return iEnrollments.isEmpty(); 326 } 327 } 328}