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 /** 207 * Test case -- run to see the weights for a few courses 208 */ 209 public static void main(String[] args) { 210 PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties()); 211 DecimalFormat df = new DecimalFormat("0.0000"); 212 Student s = new Student(0l); 213 new CourseRequest(1l, 0, false, s, ToolBox.toList( 214 new Course(1, "A", "1", new Offering(0, "A")), 215 new Course(1, "A", "2", new Offering(0, "A")), 216 new Course(1, "A", "3", new Offering(0, "A"))), false, null); 217 new CourseRequest(2l, 1, false, s, ToolBox.toList( 218 new Course(1, "B", "1", new Offering(0, "B")), 219 new Course(1, "B", "2", new Offering(0, "B")), 220 new Course(1, "B", "3", new Offering(0, "B"))), false, null); 221 new CourseRequest(3l, 2, false, s, ToolBox.toList( 222 new Course(1, "C", "1", new Offering(0, "C")), 223 new Course(1, "C", "2", new Offering(0, "C")), 224 new Course(1, "C", "3", new Offering(0, "C"))), false, null); 225 new CourseRequest(4l, 3, false, s, ToolBox.toList( 226 new Course(1, "D", "1", new Offering(0, "D")), 227 new Course(1, "D", "2", new Offering(0, "D")), 228 new Course(1, "D", "3", new Offering(0, "D"))), false, null); 229 new CourseRequest(5l, 4, false, s, ToolBox.toList( 230 new Course(1, "E", "1", new Offering(0, "E")), 231 new Course(1, "E", "2", new Offering(0, "E")), 232 new Course(1, "E", "3", new Offering(0, "E"))), false, null); 233 new CourseRequest(6l, 5, true, s, ToolBox.toList( 234 new Course(1, "F", "1", new Offering(0, "F")), 235 new Course(1, "F", "2", new Offering(0, "F")), 236 new Course(1, "F", "3", new Offering(0, "F"))), false, null); 237 new CourseRequest(7l, 6, true, s, ToolBox.toList( 238 new Course(1, "G", "1", new Offering(0, "G")), 239 new Course(1, "G", "2", new Offering(0, "G")), 240 new Course(1, "G", "3", new Offering(0, "G"))), false, null); 241 242 Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>()); 243 for (Request r: s.getRequests()) { 244 CourseRequest cr = (CourseRequest)r; 245 double[] w = new double[] {0.0, 0.0, 0.0}; 246 for (int i = 0; i < cr.getCourses().size(); i++) { 247 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 248 Set<Assignment> sections = new HashSet<Assignment>(); 249 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 250 Enrollment e = new Enrollment(cr, i, cfg, sections); 251 w[i] = pw.getWeight(e, null, null); 252 } 253 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 254 } 255 256 System.out.println("With one distance conflict:"); 257 for (Request r: s.getRequests()) { 258 CourseRequest cr = (CourseRequest)r; 259 double[] w = new double[] {0.0, 0.0, 0.0}; 260 for (int i = 0; i < cr.getCourses().size(); i++) { 261 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 262 Set<Assignment> sections = new HashSet<Assignment>(); 263 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 264 Enrollment e = new Enrollment(cr, i, cfg, sections); 265 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 266 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 267 w[i] = pw.getWeight(e, dc, null); 268 } 269 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 270 } 271 272 System.out.println("With two distance conflicts:"); 273 for (Request r: s.getRequests()) { 274 CourseRequest cr = (CourseRequest)r; 275 double[] w = new double[] {0.0, 0.0, 0.0}; 276 for (int i = 0; i < cr.getCourses().size(); i++) { 277 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 278 Set<Assignment> sections = new HashSet<Assignment>(); 279 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 280 Enrollment e = new Enrollment(cr, i, cfg, sections); 281 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 282 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 283 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, 284 new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null))); 285 w[i] = pw.getWeight(e, dc, null); 286 } 287 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 288 } 289 290 System.out.println("With 25% time overlapping conflict:"); 291 for (Request r: s.getRequests()) { 292 CourseRequest cr = (CourseRequest)r; 293 double[] w = new double[] {0.0, 0.0, 0.0}; 294 for (int i = 0; i < cr.getCourses().size(); i++) { 295 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 296 Set<Assignment> sections = new HashSet<Assignment>(); 297 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 298 Enrollment e = new Enrollment(cr, i, cfg, sections); 299 Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>(); 300 toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next())); 301 w[i] = pw.getWeight(e, null, toc); 302 } 303 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 304 } 305 306 System.out.println("Disbalanced sections (by 2 / 10 students):"); 307 for (Request r: s.getRequests()) { 308 CourseRequest cr = (CourseRequest)r; 309 double[] w = new double[] {0.0, 0.0, 0.0}; 310 for (int i = 0; i < cr.getCourses().size(); i++) { 311 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 312 Set<Assignment> sections = new HashSet<Assignment>(); 313 Subpart x = new Subpart(0, "Lec", "Lec", cfg, null); 314 Section a = new Section(0, 10, "x", x, p, null, null, null); 315 new Section(1, 10, "y", x, p, null, null, null); 316 sections.add(a); 317 a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections)); 318 a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections)); 319 cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections)); 320 cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections)); 321 Enrollment e = new Enrollment(cr, i, cfg, sections); 322 w[i] = pw.getWeight(e, null, null); 323 } 324 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 325 } 326 } 327 }