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.StudentQuality; 019import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 020import org.cpsolver.studentsct.model.Config; 021import org.cpsolver.studentsct.model.Course; 022import org.cpsolver.studentsct.model.CourseRequest; 023import org.cpsolver.studentsct.model.Enrollment; 024import org.cpsolver.studentsct.model.Offering; 025import org.cpsolver.studentsct.model.Request; 026import org.cpsolver.studentsct.model.SctAssignment; 027import org.cpsolver.studentsct.model.Section; 028import org.cpsolver.studentsct.model.Student; 029import org.cpsolver.studentsct.model.Subpart; 030 031 032/** 033 * Original weighting that was used before this student weightings model was introduced 034 * 035 * @author Tomáš Müller 036 * @version StudentSct 1.3 (Student Sectioning)<br> 037 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 038 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 039 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 040 * <br> 041 * This library is free software; you can redistribute it and/or modify 042 * it under the terms of the GNU Lesser General Public License as 043 * published by the Free Software Foundation; either version 3 of the 044 * License, or (at your option) any later version. <br> 045 * <br> 046 * This library is distributed in the hope that it will be useful, but 047 * WITHOUT ANY WARRANTY; without even the implied warranty of 048 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 049 * Lesser General Public License for more details. <br> 050 * <br> 051 * You should have received a copy of the GNU Lesser General Public 052 * License along with this library; if not see 053 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 054 */ 055 056public class OriginalStudentWeights implements StudentWeights { 057 private double iPriorityWeight = 0.90; 058 private double iAlterativeWeight = 1.0; 059 private double iInitialWeight = 1.2; 060 private double iSelectedWeight = 1.1; 061 private double iWaitlistedWeight = 1.01; 062 private double iDistConfWeight = 0.95; 063 protected double[] iQalityWeights; 064 /** 065 * Enrollment value: value * sAltValue ^ index, where index is zero for the 066 * first course, one for the second course etc. 067 */ 068 private double iAltValue = 0.5; 069 private double iDummyStudentWeight = 0.5; 070 private double iNormPenalty = 5.0; 071 072 public OriginalStudentWeights(DataProperties config) { 073 iDummyStudentWeight = config.getPropertyDouble("Student.DummyStudentWeight", iDummyStudentWeight); 074 iQalityWeights = new double[StudentQuality.Type.values().length]; 075 for (StudentQuality.Type type: StudentQuality.Type.values()) { 076 iQalityWeights[type.ordinal()] = config.getPropertyDouble(type.getWeightName(), type.getWeightDefault()); 077 } 078 } 079 080 /** 081 * Normalized enrollment penalty -- to be used in 082 * {@link Enrollment#toDouble(Assignment)} 083 * @param penalty given penalty 084 * @return normalized penalty 085 */ 086 public double normalizePenalty(double penalty) { 087 return iNormPenalty / (iNormPenalty + penalty); 088 } 089 090 091 public double getWeight(Request request) { 092 return Math.pow(iPriorityWeight, request.getPriority()) 093 * (request.isAlternative() ? iAlterativeWeight : 1.0) 094 * (request.getStudent().isDummy() ? iDummyStudentWeight : 1.0); 095 } 096 097 @Override 098 public double getBound(Request request) { 099 double w = getWeight(request) * Math.pow(iInitialWeight, (request.getInitialAssignment() == null ? 0 : 1)); 100 if (request instanceof CourseRequest) { 101 CourseRequest cr = (CourseRequest)request; 102 w *= Math.pow(iSelectedWeight, cr.getSelectedChoices().isEmpty() ? 0 : 1); 103 w *= Math.pow(iWaitlistedWeight, cr.getWaitlistedChoices().isEmpty() ? 0 : 1); 104 w *= normalizePenalty(cr.getMinPenalty()); 105 } 106 return w; 107 } 108 109 @Override 110 public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 111 return getWeight(enrollment.getRequest()) 112 * Math.pow(iAltValue, enrollment.getPriority()) 113 * Math.pow(iInitialWeight, enrollment.percentInitial()) 114 * Math.pow(iSelectedWeight, enrollment.percentSelected()) 115 * Math.pow(iWaitlistedWeight, enrollment.percentWaitlisted()) 116 * normalizePenalty(enrollment.getPenalty()); 117 } 118 119 @Override 120 public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 121 int share = 0; 122 if (timeOverlappingConflicts != null) 123 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) 124 share += c.getShare(); 125 return getWeight(assignment, enrollment) 126 * (distanceConflicts == null || distanceConflicts.isEmpty() ? 1.0 : Math.pow(iDistConfWeight, distanceConflicts.size())) 127 * Math.max(share == 0 ? 1.0 : 1.0 - (((double)share) / enrollment.getNrSlots()) / 2.0, 0.5); 128 } 129 130 @Override 131 public double getDistanceConflictWeight(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) { 132 if (c.getR1().getPriority() < c.getR2().getPriority()) { 133 return (1.0 - iDistConfWeight) * getWeight(assignment, c.getE1()); 134 } else { 135 return (1.0 - iDistConfWeight) * getWeight(assignment, c.getE2()); 136 } 137 } 138 139 @Override 140 public double getTimeOverlapConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, TimeOverlapsCounter.Conflict timeOverlap) { 141 return Math.min(0.5 * timeOverlap.getShare() / enrollment.getNrSlots(), 0.5) * getWeight(assignment, enrollment); 142 } 143 144 @Override 145 public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) { 146 if (currentSolution.getBestInfo() == null) return true; 147 int unassigned = currentSolution.getModel().nrUnassignedVariables(currentSolution.getAssignment()); 148 if (currentSolution.getModel().getBestUnassignedVariables() != unassigned) 149 return currentSolution.getModel().getBestUnassignedVariables() > unassigned; 150 return currentSolution.getModel().getTotalValue(currentSolution.getAssignment()) < currentSolution.getBestValue(); 151 } 152 153 /** 154 * Test case -- run to see the weights for a few courses 155 * @param args program arguments 156 */ 157 public static void main(String[] args) { 158 OriginalStudentWeights pw = new OriginalStudentWeights(new DataProperties()); 159 DecimalFormat df = new DecimalFormat("0.000"); 160 Student s = new Student(0l); 161 new CourseRequest(1l, 0, false, s, ToolBox.toList( 162 new Course(1, "A", "1", new Offering(0, "A")), 163 new Course(1, "A", "2", new Offering(0, "A")), 164 new Course(1, "A", "3", new Offering(0, "A"))), false, null); 165 new CourseRequest(2l, 1, false, s, ToolBox.toList( 166 new Course(1, "B", "1", new Offering(0, "B")), 167 new Course(1, "B", "2", new Offering(0, "B")), 168 new Course(1, "B", "3", new Offering(0, "B"))), false, null); 169 new CourseRequest(3l, 2, false, s, ToolBox.toList( 170 new Course(1, "C", "1", new Offering(0, "C")), 171 new Course(1, "C", "2", new Offering(0, "C")), 172 new Course(1, "C", "3", new Offering(0, "C"))), false, null); 173 new CourseRequest(4l, 3, false, s, ToolBox.toList( 174 new Course(1, "D", "1", new Offering(0, "D")), 175 new Course(1, "D", "2", new Offering(0, "D")), 176 new Course(1, "D", "3", new Offering(0, "D"))), false, null); 177 new CourseRequest(5l, 4, false, s, ToolBox.toList( 178 new Course(1, "E", "1", new Offering(0, "E")), 179 new Course(1, "E", "2", new Offering(0, "E")), 180 new Course(1, "E", "3", new Offering(0, "E"))), false, null); 181 new CourseRequest(6l, 5, true, s, ToolBox.toList( 182 new Course(1, "F", "1", new Offering(0, "F")), 183 new Course(1, "F", "2", new Offering(0, "F")), 184 new Course(1, "F", "3", new Offering(0, "F"))), false, null); 185 new CourseRequest(7l, 6, true, s, ToolBox.toList( 186 new Course(1, "G", "1", new Offering(0, "G")), 187 new Course(1, "G", "2", new Offering(0, "G")), 188 new Course(1, "G", "3", new Offering(0, "G"))), false, null); 189 190 Assignment<Request, Enrollment> assignment = new DefaultSingleAssignment<Request, Enrollment>(); 191 Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>()); 192 for (Request r: s.getRequests()) { 193 CourseRequest cr = (CourseRequest)r; 194 double[] w = new double[] {0.0, 0.0, 0.0}; 195 for (int i = 0; i < cr.getCourses().size(); i++) { 196 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 197 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 198 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 199 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 200 w[i] = pw.getWeight(assignment, e, null, null); 201 } 202 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 203 } 204 205 System.out.println("With one distance conflict:"); 206 for (Request r: s.getRequests()) { 207 CourseRequest cr = (CourseRequest)r; 208 double[] w = new double[] {0.0, 0.0, 0.0}; 209 for (int i = 0; i < cr.getCourses().size(); i++) { 210 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 211 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 212 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 213 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 214 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 215 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 216 w[i] = pw.getWeight(assignment, e, dc, null); 217 } 218 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 219 } 220 221 System.out.println("With two distance conflicts:"); 222 for (Request r: s.getRequests()) { 223 CourseRequest cr = (CourseRequest)r; 224 double[] w = new double[] {0.0, 0.0, 0.0}; 225 for (int i = 0; i < cr.getCourses().size(); i++) { 226 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 227 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 228 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 229 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 230 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 231 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 232 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, 233 new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null))); 234 w[i] = pw.getWeight(assignment, e, dc, null); 235 } 236 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 237 } 238 239 System.out.println("With 25% time overlapping conflicts:"); 240 for (Request r: s.getRequests()) { 241 CourseRequest cr = (CourseRequest)r; 242 double[] w = new double[] {0.0, 0.0, 0.0}; 243 for (int i = 0; i < cr.getCourses().size(); i++) { 244 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 245 Set<SctAssignment> sections = new HashSet<SctAssignment>(); 246 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)); 247 Enrollment e = new Enrollment(cr, i, cfg, sections, assignment); 248 Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>(); 249 toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next())); 250 w[i] = pw.getWeight(assignment, e, null, toc); 251 } 252 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 253 } 254 } 255 256 @Override 257 public boolean isFreeTimeAllowOverlaps() { 258 return true; 259 } 260 261 @Override 262 public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> qualityConflicts) { 263 double base = getWeight(assignment, enrollment); 264 double penalty = 0.0; 265 if (qualityConflicts != null) { 266 for (StudentQuality.Conflict c: qualityConflicts) { 267 Enrollment other = c.getOther(enrollment); 268 switch (c.getType().getType()) { 269 case REQUEST: 270 if (enrollment.isCourseRequest()) 271 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 272 else if (other.isCourseRequest()) 273 penalty += getWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 274 break; 275 case BOTH: 276 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 277 if (other.getRequest() != null) 278 penalty += getWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 279 break; 280 case LOWER: 281 other = c.getOther(enrollment); 282 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 283 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 284 else if (other.getRequest() != null) 285 penalty += getWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 286 break; 287 case HIGHER: 288 other = c.getOther(enrollment); 289 if (other.getRequest().getPriority() >= enrollment.getRequest().getPriority()) 290 penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment); 291 else if (other.getRequest() != null) 292 penalty += getWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other); 293 } 294 } 295 } 296 return base - penalty; 297 } 298 299 @Override 300 public double getStudentQualityConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, StudentQuality.Conflict conflict) { 301 switch (conflict.getType().getType()) { 302 case BOTH: 303 if (enrollment == null || enrollment.getRequest() == null) return 0.0; 304 return getWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment); 305 case REQUEST: 306 if (enrollment == null || enrollment.getRequest() == null || !enrollment.isCourseRequest()) return 0.0; 307 return getWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment); 308 case LOWER: 309 if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) { 310 return getWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2()); 311 } else { 312 return getWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1()); 313 } 314 case HIGHER: 315 if (conflict.getR1().getPriority() > conflict.getR2().getPriority()) { 316 return getWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2()); 317 } else { 318 return getWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1()); 319 } 320 default: 321 return 0.0; 322 } 323 } 324}