001 package net.sf.cpsolver.studentsct.weights;
002
003 import java.text.DecimalFormat;
004 import java.util.ArrayList;
005 import java.util.BitSet;
006 import java.util.HashSet;
007 import java.util.Set;
008
009 import net.sf.cpsolver.coursett.model.Placement;
010 import net.sf.cpsolver.coursett.model.RoomLocation;
011 import net.sf.cpsolver.coursett.model.TimeLocation;
012 import net.sf.cpsolver.ifs.solution.Solution;
013 import net.sf.cpsolver.ifs.util.DataProperties;
014 import net.sf.cpsolver.ifs.util.ToolBox;
015 import net.sf.cpsolver.studentsct.extension.DistanceConflict;
016 import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter;
017 import net.sf.cpsolver.studentsct.model.Assignment;
018 import net.sf.cpsolver.studentsct.model.Config;
019 import net.sf.cpsolver.studentsct.model.Course;
020 import net.sf.cpsolver.studentsct.model.CourseRequest;
021 import net.sf.cpsolver.studentsct.model.Enrollment;
022 import net.sf.cpsolver.studentsct.model.Offering;
023 import net.sf.cpsolver.studentsct.model.Request;
024 import net.sf.cpsolver.studentsct.model.Section;
025 import net.sf.cpsolver.studentsct.model.Student;
026 import net.sf.cpsolver.studentsct.model.Subpart;
027
028 /**
029 * New weighting model. It tries to obey the following principles:
030 * <ul>
031 * <li> Total student weight is between zero and one (one means student got the best schedule)
032 * <li> Weight of the given priority course is higher than sum of the remaining weights the student can get
033 * <li> First alternative is better than the following course
034 * <li> Second alternative is better than the second following course
035 * <li> Distance conflicts are considered secondary (priorities should be maximized first)
036 * <li> If alternative sections are otherwise equal, use the better balanced one
037 * </ul>
038 *
039 * @version StudentSct 1.2 (Student Sectioning)<br>
040 * Copyright (C) 2007 - 2010 Tomas Muller<br>
041 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
042 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
043 * <br>
044 * This library is free software; you can redistribute it and/or modify
045 * it under the terms of the GNU Lesser General Public License as
046 * published by the Free Software Foundation; either version 3 of the
047 * License, or (at your option) any later version. <br>
048 * <br>
049 * This library is distributed in the hope that it will be useful, but
050 * WITHOUT ANY WARRANTY; without even the implied warranty of
051 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
052 * Lesser General Public License for more details. <br>
053 * <br>
054 * You should have received a copy of the GNU Lesser General Public
055 * License along with this library; if not see
056 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
057 */
058
059 public class PriorityStudentWeights implements StudentWeights {
060 protected double iPriorityFactor = 0.5010;
061 protected double iFirstAlternativeFactor = 0.5010;
062 protected double iSecondAlternativeFactor = 0.2510;
063 protected double iDistanceConflict = 0.0100;
064 protected double iTimeOverlapFactor = 0.5000;
065 protected double iTimeOverlapMaxLimit = 0.5000;
066 protected boolean iLeftoverSpread = false;
067 protected double iBalancingFactor = 0.0050;
068 protected double iAlternativeRequestFactor = 0.1260;
069 protected double iProjectedStudentWeight = 0.0100;
070
071 public PriorityStudentWeights(DataProperties config) {
072 iPriorityFactor = config.getPropertyDouble("StudentWeights.Priority", iPriorityFactor);
073 iFirstAlternativeFactor = config.getPropertyDouble("StudentWeights.FirstAlternative", iFirstAlternativeFactor);
074 iSecondAlternativeFactor = config.getPropertyDouble("StudentWeights.SecondAlternative", iSecondAlternativeFactor);
075 iDistanceConflict = config.getPropertyDouble("StudentWeights.DistanceConflict", iDistanceConflict);
076 iTimeOverlapFactor = config.getPropertyDouble("StudentWeights.TimeOverlapFactor", iTimeOverlapFactor);
077 iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit);
078 iLeftoverSpread = config.getPropertyBoolean("StudentWeights.LeftoverSpread", iLeftoverSpread);
079 iBalancingFactor = config.getPropertyDouble("StudentWeights.BalancingFactor", iBalancingFactor);
080 iAlternativeRequestFactor = config.getPropertyDouble("StudentWeights.AlternativeRequestFactor", iAlternativeRequestFactor);
081 iProjectedStudentWeight = config.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight);
082 }
083
084 public double getWeight(Request request) {
085 if (request.getStudent().isDummy() && iProjectedStudentWeight >= 0.0) {
086 double weight = iProjectedStudentWeight;
087 if (request.isAlternative())
088 weight *= iAlternativeRequestFactor;
089 return weight;
090 }
091 double total = 10000.0;
092 int nrReq = request.getStudent().nrRequests();
093 double remain = (iLeftoverSpread ? Math.floor(10000.0 * Math.pow(iPriorityFactor, nrReq) / nrReq) : 0.0);
094 for (int idx = 0; idx < request.getStudent().getRequests().size(); idx++) {
095 Request r = request.getStudent().getRequests().get(idx);
096 boolean last = (idx + 1 == request.getStudent().getRequests().size());
097 boolean lastNotAlt = !r.isAlternative() && (last || request.getStudent().getRequests().get(1 + idx).isAlternative());
098 double w = Math.ceil(iPriorityFactor * total) + remain;
099 if (lastNotAlt || last) {
100 w = total;
101 } else {
102 total -= w;
103 }
104 if (r.equals(request)) {
105 return w / 10000.0;
106 }
107 }
108 return 0.0;
109 }
110
111 public double getCachedWeight(Request request) {
112 Double w = (Double)request.getExtra();
113 if (w == null) {
114 w = getWeight(request);
115 request.setExtra(w);
116 }
117 return w;
118 }
119
120 @Override
121 public double getBound(Request request) {
122 return getCachedWeight(request);
123 }
124
125 protected double round(double value) {
126 return Math.ceil(10000.0 * value) / 10000.0;
127 }
128
129 @Override
130 public double getWeight(Enrollment enrollment) {
131 double weight = getCachedWeight(enrollment.getRequest());
132 switch (enrollment.getPriority()) {
133 case 1: weight *= iFirstAlternativeFactor; break;
134 case 2: weight *= iSecondAlternativeFactor; break;
135 }
136 if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) {
137 double configUsed = enrollment.getConfig().getEnrollmentWeight(enrollment.getRequest()) + enrollment.getRequest().getWeight();
138 double disbalanced = 0;
139 double total = 0;
140 for (Section section: enrollment.getSections()) {
141 Subpart subpart = section.getSubpart();
142 if (subpart.getSections().size() <= 1) continue;
143 double used = section.getEnrollmentWeight(enrollment.getRequest()) + enrollment.getRequest().getWeight();
144 // sections have limits -> desired size is section limit x (total enrollment / total limit)
145 // unlimited sections -> desired size is total enrollment / number of sections
146 double desired = (subpart.getLimit() > 0
147 ? section.getLimit() * (configUsed / subpart.getLimit())
148 : configUsed / subpart.getSections().size());
149 if (used > desired)
150 disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight();
151 else
152 disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight();
153 total ++;
154 }
155 if (disbalanced > 0)
156 weight *= (1.0 - disbalanced / total * iBalancingFactor);
157 }
158 return round(weight);
159 }
160
161 @Override
162 public double getDistanceConflictWeight(DistanceConflict.Conflict c) {
163 if (c.getR1().getPriority() < c.getR2().getPriority()) {
164 return round(getWeight(c.getE2()) * iDistanceConflict);
165 } else {
166 return round(getWeight(c.getE1()) * iDistanceConflict);
167 }
168 }
169
170 @Override
171 public double getTimeOverlapConflictWeight(Enrollment e, TimeOverlapsCounter.Conflict c) {
172 double toc = Math.min(iTimeOverlapMaxLimit * c.getShare() / e.getNrSlots(), iTimeOverlapMaxLimit);
173 return round(getWeight(e) * toc);
174 }
175
176 @Override
177 public double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
178 double base = getWeight(enrollment);
179 double dc = 0.0;
180 if (distanceConflicts != null) {
181 for (DistanceConflict.Conflict c: distanceConflicts) {
182 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
183 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
184 dc += base * iDistanceConflict;
185 else
186 dc += getWeight(other) * iDistanceConflict;
187 }
188 }
189 double toc = 0.0;
190 if (timeOverlappingConflicts != null) {
191 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
192 toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit);
193 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
194 toc += getWeight(other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit);
195 }
196 }
197 return round(base - dc - toc);
198 }
199
200
201 @Override
202 public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) {
203 return currentSolution.getBestInfo() == null || currentSolution.getModel().getTotalValue() < currentSolution.getBestValue();
204 }
205
206 @Override
207 public boolean isFreeTimeAllowOverlaps() {
208 return false;
209 }
210
211 /**
212 * Test case -- run to see the weights for a few courses
213 */
214 public static void main(String[] args) {
215 PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties());
216 DecimalFormat df = new DecimalFormat("0.0000");
217 Student s = new Student(0l);
218 new CourseRequest(1l, 0, false, s, ToolBox.toList(
219 new Course(1, "A", "1", new Offering(0, "A")),
220 new Course(1, "A", "2", new Offering(0, "A")),
221 new Course(1, "A", "3", new Offering(0, "A"))), false, null);
222 new CourseRequest(2l, 1, false, s, ToolBox.toList(
223 new Course(1, "B", "1", new Offering(0, "B")),
224 new Course(1, "B", "2", new Offering(0, "B")),
225 new Course(1, "B", "3", new Offering(0, "B"))), false, null);
226 new CourseRequest(3l, 2, false, s, ToolBox.toList(
227 new Course(1, "C", "1", new Offering(0, "C")),
228 new Course(1, "C", "2", new Offering(0, "C")),
229 new Course(1, "C", "3", new Offering(0, "C"))), false, null);
230 new CourseRequest(4l, 3, false, s, ToolBox.toList(
231 new Course(1, "D", "1", new Offering(0, "D")),
232 new Course(1, "D", "2", new Offering(0, "D")),
233 new Course(1, "D", "3", new Offering(0, "D"))), false, null);
234 new CourseRequest(5l, 4, false, s, ToolBox.toList(
235 new Course(1, "E", "1", new Offering(0, "E")),
236 new Course(1, "E", "2", new Offering(0, "E")),
237 new Course(1, "E", "3", new Offering(0, "E"))), false, null);
238 new CourseRequest(6l, 5, true, s, ToolBox.toList(
239 new Course(1, "F", "1", new Offering(0, "F")),
240 new Course(1, "F", "2", new Offering(0, "F")),
241 new Course(1, "F", "3", new Offering(0, "F"))), false, null);
242 new CourseRequest(7l, 6, true, s, ToolBox.toList(
243 new Course(1, "G", "1", new Offering(0, "G")),
244 new Course(1, "G", "2", new Offering(0, "G")),
245 new Course(1, "G", "3", new Offering(0, "G"))), false, null);
246
247 Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>());
248 for (Request r: s.getRequests()) {
249 CourseRequest cr = (CourseRequest)r;
250 double[] w = new double[] {0.0, 0.0, 0.0};
251 for (int i = 0; i < cr.getCourses().size(); i++) {
252 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
253 Set<Assignment> sections = new HashSet<Assignment>();
254 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
255 Enrollment e = new Enrollment(cr, i, cfg, sections);
256 w[i] = pw.getWeight(e, null, null);
257 }
258 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2]));
259 }
260
261 System.out.println("With one distance conflict:");
262 for (Request r: s.getRequests()) {
263 CourseRequest cr = (CourseRequest)r;
264 double[] w = new double[] {0.0, 0.0, 0.0};
265 for (int i = 0; i < cr.getCourses().size(); i++) {
266 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
267 Set<Assignment> sections = new HashSet<Assignment>();
268 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
269 Enrollment e = new Enrollment(cr, i, cfg, sections);
270 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
271 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
272 w[i] = pw.getWeight(e, dc, null);
273 }
274 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2]));
275 }
276
277 System.out.println("With two distance conflicts:");
278 for (Request r: s.getRequests()) {
279 CourseRequest cr = (CourseRequest)r;
280 double[] w = new double[] {0.0, 0.0, 0.0};
281 for (int i = 0; i < cr.getCourses().size(); i++) {
282 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
283 Set<Assignment> sections = new HashSet<Assignment>();
284 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
285 Enrollment e = new Enrollment(cr, i, cfg, sections);
286 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
287 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
288 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e,
289 new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)));
290 w[i] = pw.getWeight(e, dc, null);
291 }
292 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2]));
293 }
294
295 System.out.println("With 25% time overlapping conflict:");
296 for (Request r: s.getRequests()) {
297 CourseRequest cr = (CourseRequest)r;
298 double[] w = new double[] {0.0, 0.0, 0.0};
299 for (int i = 0; i < cr.getCourses().size(); i++) {
300 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
301 Set<Assignment> sections = new HashSet<Assignment>();
302 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
303 Enrollment e = new Enrollment(cr, i, cfg, sections);
304 Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>();
305 toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next()));
306 w[i] = pw.getWeight(e, null, toc);
307 }
308 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2]));
309 }
310
311 System.out.println("Disbalanced sections (by 2 / 10 students):");
312 for (Request r: s.getRequests()) {
313 CourseRequest cr = (CourseRequest)r;
314 double[] w = new double[] {0.0, 0.0, 0.0};
315 for (int i = 0; i < cr.getCourses().size(); i++) {
316 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
317 Set<Assignment> sections = new HashSet<Assignment>();
318 Subpart x = new Subpart(0, "Lec", "Lec", cfg, null);
319 Section a = new Section(0, 10, "x", x, p, null, null, null);
320 new Section(1, 10, "y", x, p, null, null, null);
321 sections.add(a);
322 a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
323 a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
324 cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
325 cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
326 Enrollment e = new Enrollment(cr, i, cfg, sections);
327 w[i] = pw.getWeight(e, null, null);
328 }
329 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2]));
330 }
331 }
332 }