001package net.sf.cpsolver.studentsct.weights; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.BitSet; 006import java.util.HashSet; 007import java.util.Set; 008 009import net.sf.cpsolver.coursett.model.Placement; 010import net.sf.cpsolver.coursett.model.RoomLocation; 011import net.sf.cpsolver.coursett.model.TimeLocation; 012import net.sf.cpsolver.ifs.solution.Solution; 013import net.sf.cpsolver.ifs.util.DataProperties; 014import net.sf.cpsolver.ifs.util.ToolBox; 015import net.sf.cpsolver.studentsct.extension.DistanceConflict; 016import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter; 017import net.sf.cpsolver.studentsct.model.Assignment; 018import net.sf.cpsolver.studentsct.model.Config; 019import net.sf.cpsolver.studentsct.model.Course; 020import net.sf.cpsolver.studentsct.model.CourseRequest; 021import net.sf.cpsolver.studentsct.model.Enrollment; 022import net.sf.cpsolver.studentsct.model.Offering; 023import net.sf.cpsolver.studentsct.model.Request; 024import net.sf.cpsolver.studentsct.model.Section; 025import net.sf.cpsolver.studentsct.model.Student; 026import 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 Tomáš Müller<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 059public 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}