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