001 package net.sf.cpsolver.studentsct.constraint;
002
003 import java.util.Iterator;
004 import java.util.Set;
005 import java.util.Vector;
006
007 import net.sf.cpsolver.ifs.model.GlobalConstraint;
008 import net.sf.cpsolver.ifs.model.Value;
009 import net.sf.cpsolver.ifs.util.DataProperties;
010 import net.sf.cpsolver.ifs.util.ToolBox;
011 import net.sf.cpsolver.studentsct.model.Enrollment;
012 import net.sf.cpsolver.studentsct.model.Request;
013 import net.sf.cpsolver.studentsct.model.Section;
014
015 /**
016 * Section limit constraint. This global constraint ensures that
017 * a limit of each section is not exceeded. This means that the total
018 * sum of weights of course requests (see {@link Request#getWeight()}) enrolled
019 * into a section is below the section's limit (see {@link Section#getLimit()}).
020 *
021 * <br><br>
022 * Sections with negative limit are considered unlimited, and therefore
023 * completely ignored by this constraint.
024 *
025 * <br><br>
026 * Parameters:
027 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
028 * <tr><td>SectionLimit.PreferDummyStudents</td><td>{@link Boolean}</td><td>If true, requests of dummy (last-like) students are preferred to be selected as conflicting.</td></tr>
029 * </table>
030 * <br><br>
031 *
032 * @version
033 * StudentSct 1.1 (Student Sectioning)<br>
034 * Copyright (C) 2007 Tomáš Müller<br>
035 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
036 * Lazenska 391, 76314 Zlin, Czech Republic<br>
037 * <br>
038 * This library is free software; you can redistribute it and/or
039 * modify it under the terms of the GNU Lesser General Public
040 * License as published by the Free Software Foundation; either
041 * version 2.1 of the License, or (at your option) any later version.
042 * <br><br>
043 * This library is distributed in the hope that it will be useful,
044 * but WITHOUT ANY WARRANTY; without even the implied warranty of
045 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
046 * Lesser General Public License for more details.
047 * <br><br>
048 * You should have received a copy of the GNU Lesser General Public
049 * License along with this library; if not, write to the Free Software
050 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
051 */
052 public class SectionLimit extends GlobalConstraint {
053 private static double sNominalWeight = 0.00001;
054 private boolean iPreferDummyStudents = false;
055
056 /**
057 * Constructor
058 * @param cfg solver configuration
059 */
060 public SectionLimit(DataProperties cfg) {
061 super();
062 iPreferDummyStudents = cfg.getPropertyBoolean("SectionLimit.PreferDummyStudents", false);
063 }
064
065
066 /**
067 * Enrollment weight of a section if the given request is assigned.
068 * In order to overcome rounding problems with last-like students (
069 * e.g., 5 students are projected to two sections of limit 2 --
070 * each section can have up to 3 of these last-like students),
071 * the weight of the request with the highest weight in the section is
072 * changed to a small nominal weight.
073 * @param section a section that is of concern
074 * @param request a request of a student to be assigned containing the given section
075 * @return section's new weight
076 */
077 public static double getEnrollmentWeight(Section section, Request request) {
078 return
079 section.getEnrollmentWeight(request) + request.getWeight()
080 - Math.max(section.getMaxEnrollmentWeight(),request.getWeight())
081 + sNominalWeight;
082 }
083
084 /**
085 * A given enrollment is conflicting, if there is a section which limit (computed
086 * by {@link SectionLimit#getEnrollmentWeight(Section, Request)})
087 * exceeds the section limit.
088 * <br>
089 * For each of such sections, one or more existing enrollments are (randomly)
090 * selected as conflicting until the overall weight is under the limit.
091 *
092 * @param value {@link Enrollment} that is being considered
093 * @param conflicts all computed conflicting requests are added into this set
094 */
095 public void computeConflicts(Value value, Set conflicts) {
096 //get enrollment
097 Enrollment enrollment = (Enrollment)value;
098
099 //exclude free time requests
100 if (!enrollment.isCourseRequest()) return;
101
102 //for each section
103 for (Iterator i=enrollment.getAssignments().iterator();i.hasNext();) {
104
105 Section section = (Section)i.next();
106
107 //unlimited section
108 if (section.getLimit()<0) continue;
109
110 //new enrollment weight
111 double enrlWeight = getEnrollmentWeight(section, enrollment.getRequest());
112
113 //below limit -> ok
114 if (enrlWeight<=section.getLimit()) continue;
115
116 //above limit -> compute adepts (current assignments that are not yet conflicting)
117 //exclude all conflicts as well
118 Vector dummyAdepts = new Vector(section.getEnrollments().size());
119 Vector adepts = new Vector(section.getEnrollments().size());
120 for (Iterator j=section.getEnrollments().iterator();j.hasNext();) {
121 Enrollment e = (Enrollment)j.next();
122 if (e.getRequest().equals(enrollment.getRequest())) continue;
123 if (conflicts.contains(e))
124 enrlWeight -= e.getRequest().getWeight();
125 else if (iPreferDummyStudents && e.getStudent().isDummy())
126 dummyAdepts.addElement(e);
127 else
128 adepts.addElement(e);
129 }
130
131 //while above limit -> pick an adept and make it conflicting
132 while (enrlWeight>section.getLimit()) {
133 //pick adept (prefer dummy students), decrease enrollment weight, make conflict
134 if (iPreferDummyStudents && !dummyAdepts.isEmpty()) {
135 Enrollment conflict = (Enrollment)ToolBox.random(dummyAdepts);
136 dummyAdepts.remove(conflict);
137 enrlWeight -= conflict.getRequest().getWeight();
138 conflicts.add(conflict);
139 } else if (!adepts.isEmpty()) {
140 Enrollment conflict = (Enrollment)ToolBox.random(adepts);
141 adepts.remove(conflict);
142 enrlWeight -= conflict.getRequest().getWeight();
143 conflicts.add(conflict);
144 } else {
145 //no adepts -> enrollment cannot be assigned
146 conflicts.add(enrollment); break;
147 }
148 }
149 }
150 }
151
152 /**
153 * A given enrollment is conflicting, if there is a section which limit(computed
154 * by {@link SectionLimit#getEnrollmentWeight(Section, Request)})
155 * exceeds the section limit.
156 *
157 * @param value {@link Enrollment} that is being considered
158 * @return true, if there is a section which will exceed its limit when the given
159 * enrollment is assigned
160 */
161 public boolean inConflict(Value value) {
162 //get enrollment
163 Enrollment enrollment = (Enrollment)value;
164
165 //exclude free time requests
166 if (!enrollment.isCourseRequest()) return false;
167
168 //for each section
169 for (Iterator i=enrollment.getAssignments().iterator();i.hasNext();) {
170
171 Section section = (Section)i.next();
172
173 //unlimited section
174 if (section.getLimit()<0) continue;
175
176 //new enrollment weight
177 double enrlWeight = getEnrollmentWeight(section, enrollment.getRequest());
178
179 //above limit -> conflict
180 if (enrlWeight>section.getLimit()) return true;
181 }
182
183 //no conflicting section -> no conflict
184 return false;
185 }
186
187 public String toString() {
188 return "SectioningLimit";
189 }
190 }