001 package net.sf.cpsolver.studentsct.constraint;
002
003 import java.util.ArrayList;
004 import java.util.List;
005 import java.util.Set;
006
007 import net.sf.cpsolver.ifs.model.GlobalConstraint;
008 import net.sf.cpsolver.ifs.util.DataProperties;
009 import net.sf.cpsolver.ifs.util.ToolBox;
010 import net.sf.cpsolver.studentsct.StudentSectioningModel;
011 import net.sf.cpsolver.studentsct.model.Config;
012 import net.sf.cpsolver.studentsct.model.Enrollment;
013 import net.sf.cpsolver.studentsct.model.Request;
014
015 /**
016 * Configuration limit constraint. This global constraint ensures that a limit of each
017 * configuration is not exceeded. This means that the total sum of weights of course
018 * requests (see {@link Request#getWeight()}) enrolled into a configuration is below
019 * the configuration's limit (see {@link Config#getLimit()}).
020 *
021 * <br>
022 * <br>
023 * Configurations with negative limit are considered unlimited, and therefore
024 * completely ignored by this constraint.
025 *
026 * <br>
027 * <br>
028 * Parameters:
029 * <table border='1'>
030 * <tr>
031 * <th>Parameter</th>
032 * <th>Type</th>
033 * <th>Comment</th>
034 * </tr>
035 * <tr>
036 * <td>ConfigLimit.PreferDummyStudents</td>
037 * <td>{@link Boolean}</td>
038 * <td>If true, requests of dummy (last-like) students are preferred to be
039 * selected as conflicting.</td>
040 * </tr>
041 * </table>
042 * <br>
043 * <br>
044 *
045 * @version StudentSct 1.2 (Student Sectioning)<br>
046 * Copyright (C) 2007 - 2010 Tomas Muller<br>
047 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
048 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
049 * <br>
050 * This library is free software; you can redistribute it and/or modify
051 * it under the terms of the GNU Lesser General Public License as
052 * published by the Free Software Foundation; either version 3 of the
053 * License, or (at your option) any later version. <br>
054 * <br>
055 * This library is distributed in the hope that it will be useful, but
056 * WITHOUT ANY WARRANTY; without even the implied warranty of
057 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
058 * Lesser General Public License for more details. <br>
059 * <br>
060 * You should have received a copy of the GNU Lesser General Public
061 * License along with this library; if not see
062 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
063 */
064 public class ConfigLimit extends GlobalConstraint<Request, Enrollment> {
065
066 private static double sNominalWeight = 0.00001;
067 private boolean iPreferDummyStudents = false;
068
069 /**
070 * Constructor
071 *
072 * @param cfg
073 * solver configuration
074 */
075 public ConfigLimit(DataProperties cfg) {
076 super();
077 iPreferDummyStudents = cfg.getPropertyBoolean("ConfigLimit.PreferDummyStudents", false);
078 }
079
080
081 /**
082 * Enrollment weight of a config if the given request is assigned. In order
083 * to overcome rounding problems with last-like students ( e.g., 5 students
084 * are projected to two configs of limit 2 -- each section can have up to 3
085 * of these last-like students), the weight of the request with the highest
086 * weight in the config is changed to a small nominal weight.
087 *
088 * @param config
089 * a config that is of concern
090 * @param request
091 * a request of a student to be assigned containing the given
092 * section
093 * @return section's new weight
094 */
095 public static double getEnrollmentWeight(Config config, Request request) {
096 return config.getEnrollmentWeight(request) + request.getWeight()
097 - Math.max(config.getMaxEnrollmentWeight(), request.getWeight()) + sNominalWeight;
098 }
099
100 /**
101 * A given enrollment is conflicting, if the config's enrollment
102 * (computed by {@link ConfigLimit#getEnrollmentWeight(Config, Request)})
103 * exceeds the limit. <br>
104 * If the limit is breached, one or more existing enrollments are
105 * (randomly) selected as conflicting until the overall weight is under the
106 * limit.
107 *
108 * @param enrollment
109 * {@link Enrollment} that is being considered
110 * @param conflicts
111 * all computed conflicting requests are added into this set
112 */
113 @Override
114 public void computeConflicts(Enrollment enrollment, Set<Enrollment> conflicts) {
115 // check reservation can assign over the limit
116 if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
117 enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
118 return;
119
120 // enrollment's config
121 Config config = enrollment.getConfig();
122
123 // exclude free time requests
124 if (config == null)
125 return;
126
127
128 // unlimited config
129 if (config.getLimit() < 0)
130 return;
131
132 // new enrollment weight
133 double enrlWeight = getEnrollmentWeight(config, enrollment.getRequest());
134
135 // below limit -> ok
136 if (enrlWeight <= config.getLimit())
137 return;
138
139 // above limit -> compute adepts (current assignments that are not
140 // yet conflicting)
141 // exclude all conflicts as well
142 List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments().size());
143 for (Enrollment e : config.getEnrollments()) {
144 if (e.getRequest().equals(enrollment.getRequest()))
145 continue;
146 if (conflicts.contains(e))
147 enrlWeight -= e.getRequest().getWeight();
148 else
149 adepts.add(e);
150 }
151
152 // while above limit -> pick an adept and make it conflicting
153 while (enrlWeight > config.getLimit()) {
154 if (adepts.isEmpty()) {
155 // no adepts -> enrollment cannot be assigned
156 conflicts.add(enrollment);
157 return;
158 }
159
160 // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
161 // weight, make conflict
162 List<Enrollment> best = new ArrayList<Enrollment>();
163 boolean bestDummy = false;
164 double bestValue = 0;
165 boolean bestRes = true;
166 for (Enrollment adept: adepts) {
167 boolean dummy = adept.getStudent().isDummy();
168 double value = adept.toDouble(false);
169 boolean res = (adept.getReservation() != null);
170
171 if (iPreferDummyStudents && dummy != bestDummy) {
172 if (dummy) {
173 best.clear();
174 best.add(adept);
175 bestDummy = dummy;
176 bestValue = value;
177 bestRes = res;
178 }
179 continue;
180 }
181
182 if (bestRes != res) {
183 if (!res) {
184 best.clear();
185 best.add(adept);
186 bestDummy = dummy;
187 bestValue = value;
188 bestRes = res;
189 }
190 continue;
191 }
192
193 if (best.isEmpty() || value > bestValue) {
194 if (best.isEmpty()) best.clear();
195 best.add(adept);
196 bestDummy = dummy;
197 bestValue = value;
198 bestRes = res;
199 } else if (bestValue == value) {
200 best.add(adept);
201 }
202 }
203
204 Enrollment conflict = ToolBox.random(best);
205 adepts.remove(conflict);
206 enrlWeight -= conflict.getRequest().getWeight();
207 conflicts.add(conflict);
208 }
209 }
210
211 /**
212 * A given enrollment is conflicting, if the config's enrollment (computed by
213 * {@link ConfigLimit#getEnrollmentWeight(Config, Request)}) exceeds the
214 * limit.
215 *
216 * @param enrollment
217 * {@link Enrollment} that is being considered
218 * @return true, if the enrollment cannot be assigned without exceeding the limit
219 */
220 @Override
221 public boolean inConflict(Enrollment enrollment) {
222 // check reservation can assign over the limit
223 if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
224 enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
225 return false;
226
227 // enrollment's config
228 Config config = enrollment.getConfig();
229
230 // exclude free time requests
231 if (config == null)
232 return false;
233
234 // unlimited config
235 if (config.getLimit() < 0)
236 return false;
237
238
239 // new enrollment weight
240 double enrlWeight = getEnrollmentWeight(config, enrollment.getRequest());
241
242 // above limit -> conflict
243 return (enrlWeight > config.getLimit());
244 }
245
246 @Override
247 public String toString() {
248 return "ConfigLimit";
249 }
250
251 }