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 * Original weighting that was used before this student weightings model was introduced 030 * 031 * @version StudentSct 1.2 (Student Sectioning)<br> 032 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 033 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 034 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 035 * <br> 036 * This library is free software; you can redistribute it and/or modify 037 * it under the terms of the GNU Lesser General Public License as 038 * published by the Free Software Foundation; either version 3 of the 039 * License, or (at your option) any later version. <br> 040 * <br> 041 * This library is distributed in the hope that it will be useful, but 042 * WITHOUT ANY WARRANTY; without even the implied warranty of 043 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 044 * Lesser General Public License for more details. <br> 045 * <br> 046 * You should have received a copy of the GNU Lesser General Public 047 * License along with this library; if not see 048 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 049 */ 050 051public class OriginalStudentWeights implements StudentWeights { 052 private double iPriorityWeight = 0.90; 053 private double iAlterativeWeight = 1.0; 054 private double iInitialWeight = 1.2; 055 private double iSelectedWeight = 1.1; 056 private double iWaitlistedWeight = 1.01; 057 private double iDistConfWeight = 0.95; 058 /** 059 * Enrollment value: value * sAltValue ^ index, where index is zero for the 060 * first course, one for the second course etc. 061 */ 062 private double iAltValue = 0.5; 063 private double iDummyStudentWeight = 0.5; 064 private double iNormPenalty = 5.0; 065 066 public OriginalStudentWeights(DataProperties config) { 067 iDummyStudentWeight = config.getPropertyDouble("Student.DummyStudentWeight", iDummyStudentWeight); 068 } 069 070 /** 071 * Normalized enrollment penalty -- to be used in 072 * {@link Enrollment#toDouble()} 073 */ 074 public double normalizePenalty(double penalty) { 075 return iNormPenalty / (iNormPenalty + penalty); 076 } 077 078 079 public double getWeight(Request request) { 080 return Math.pow(iPriorityWeight, request.getPriority()) 081 * (request.isAlternative() ? iAlterativeWeight : 1.0) 082 * (request.getStudent().isDummy() ? iDummyStudentWeight : 1.0); 083 } 084 085 @Override 086 public double getBound(Request request) { 087 double w = getWeight(request) * Math.pow(iInitialWeight, (request.getInitialAssignment() == null ? 0 : 1)); 088 if (request instanceof CourseRequest) { 089 CourseRequest cr = (CourseRequest)request; 090 w *= Math.pow(iSelectedWeight, cr.getSelectedChoices().isEmpty() ? 0 : 1); 091 w *= Math.pow(iWaitlistedWeight, cr.getWaitlistedChoices().isEmpty() ? 0 : 1); 092 w *= normalizePenalty(cr.getMinPenalty()); 093 } 094 return w; 095 } 096 097 @Override 098 public double getWeight(Enrollment enrollment) { 099 return getWeight(enrollment.getRequest()) 100 * Math.pow(iAltValue, enrollment.getPriority()) 101 * Math.pow(iInitialWeight, enrollment.percentInitial()) 102 * Math.pow(iSelectedWeight, enrollment.percentSelected()) 103 * Math.pow(iWaitlistedWeight, enrollment.percentWaitlisted()) 104 * normalizePenalty(enrollment.getPenalty()); 105 } 106 107 @Override 108 public double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 109 int share = 0; 110 if (timeOverlappingConflicts != null) 111 for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) 112 share += c.getShare(); 113 return getWeight(enrollment) 114 * (distanceConflicts == null || distanceConflicts.isEmpty() ? 1.0 : Math.pow(iDistConfWeight, distanceConflicts.size())) 115 * Math.max(share == 0 ? 1.0 : 1.0 - (((double)share) / enrollment.getNrSlots()) / 2.0, 0.5); 116 } 117 118 @Override 119 public double getDistanceConflictWeight(DistanceConflict.Conflict c) { 120 if (c.getR1().getPriority() < c.getR2().getPriority()) { 121 return (1.0 - iDistConfWeight) * getWeight(c.getE1()); 122 } else { 123 return (1.0 - iDistConfWeight) * getWeight(c.getE2()); 124 } 125 } 126 127 @Override 128 public double getTimeOverlapConflictWeight(Enrollment enrollment, TimeOverlapsCounter.Conflict timeOverlap) { 129 return Math.min(0.5 * timeOverlap.getShare() / enrollment.getNrSlots(), 0.5) * getWeight(enrollment); 130 } 131 132 @Override 133 public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) { 134 if (currentSolution.getBestInfo() == null) return true; 135 int unassigned = currentSolution.getModel().nrUnassignedVariables(); 136 if (currentSolution.getModel().getBestUnassignedVariables() != unassigned) 137 return currentSolution.getModel().getBestUnassignedVariables() > unassigned; 138 return currentSolution.getModel().getTotalValue() < currentSolution.getBestValue(); 139 } 140 141 /** 142 * Test case -- run to see the weights for a few courses 143 */ 144 public static void main(String[] args) { 145 OriginalStudentWeights pw = new OriginalStudentWeights(new DataProperties()); 146 DecimalFormat df = new DecimalFormat("0.000"); 147 Student s = new Student(0l); 148 new CourseRequest(1l, 0, false, s, ToolBox.toList( 149 new Course(1, "A", "1", new Offering(0, "A")), 150 new Course(1, "A", "2", new Offering(0, "A")), 151 new Course(1, "A", "3", new Offering(0, "A"))), false, null); 152 new CourseRequest(2l, 1, false, s, ToolBox.toList( 153 new Course(1, "B", "1", new Offering(0, "B")), 154 new Course(1, "B", "2", new Offering(0, "B")), 155 new Course(1, "B", "3", new Offering(0, "B"))), false, null); 156 new CourseRequest(3l, 2, false, s, ToolBox.toList( 157 new Course(1, "C", "1", new Offering(0, "C")), 158 new Course(1, "C", "2", new Offering(0, "C")), 159 new Course(1, "C", "3", new Offering(0, "C"))), false, null); 160 new CourseRequest(4l, 3, false, s, ToolBox.toList( 161 new Course(1, "D", "1", new Offering(0, "D")), 162 new Course(1, "D", "2", new Offering(0, "D")), 163 new Course(1, "D", "3", new Offering(0, "D"))), false, null); 164 new CourseRequest(5l, 4, false, s, ToolBox.toList( 165 new Course(1, "E", "1", new Offering(0, "E")), 166 new Course(1, "E", "2", new Offering(0, "E")), 167 new Course(1, "E", "3", new Offering(0, "E"))), false, null); 168 new CourseRequest(6l, 5, true, s, ToolBox.toList( 169 new Course(1, "F", "1", new Offering(0, "F")), 170 new Course(1, "F", "2", new Offering(0, "F")), 171 new Course(1, "F", "3", new Offering(0, "F"))), false, null); 172 new CourseRequest(7l, 6, true, s, ToolBox.toList( 173 new Course(1, "G", "1", new Offering(0, "G")), 174 new Course(1, "G", "2", new Offering(0, "G")), 175 new Course(1, "G", "3", new Offering(0, "G"))), false, null); 176 177 Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>()); 178 for (Request r: s.getRequests()) { 179 CourseRequest cr = (CourseRequest)r; 180 double[] w = new double[] {0.0, 0.0, 0.0}; 181 for (int i = 0; i < cr.getCourses().size(); i++) { 182 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 183 Set<Assignment> sections = new HashSet<Assignment>(); 184 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 185 Enrollment e = new Enrollment(cr, i, cfg, sections); 186 w[i] = pw.getWeight(e, null, null); 187 } 188 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 189 } 190 191 System.out.println("With one distance conflict:"); 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<Assignment> sections = new HashSet<Assignment>(); 198 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 199 Enrollment e = new Enrollment(cr, i, cfg, sections); 200 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 201 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 202 w[i] = pw.getWeight(e, dc, null); 203 } 204 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 205 } 206 207 System.out.println("With two distance conflicts:"); 208 for (Request r: s.getRequests()) { 209 CourseRequest cr = (CourseRequest)r; 210 double[] w = new double[] {0.0, 0.0, 0.0}; 211 for (int i = 0; i < cr.getCourses().size(); i++) { 212 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 213 Set<Assignment> sections = new HashSet<Assignment>(); 214 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 215 Enrollment e = new Enrollment(cr, i, cfg, sections); 216 Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>(); 217 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next())); 218 dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, 219 new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null))); 220 w[i] = pw.getWeight(e, dc, null); 221 } 222 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 223 } 224 225 System.out.println("With 25% time overlapping conflicts:"); 226 for (Request r: s.getRequests()) { 227 CourseRequest cr = (CourseRequest)r; 228 double[] w = new double[] {0.0, 0.0, 0.0}; 229 for (int i = 0; i < cr.getCourses().size(); i++) { 230 Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering()); 231 Set<Assignment> sections = new HashSet<Assignment>(); 232 sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)); 233 Enrollment e = new Enrollment(cr, i, cfg, sections); 234 Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>(); 235 toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next())); 236 w[i] = pw.getWeight(e, null, toc); 237 } 238 System.out.println(cr + ": " + df.format(w[0]) + " " + df.format(w[1]) + " " + df.format(w[2])); 239 } 240 } 241 242 @Override 243 public boolean isFreeTimeAllowOverlaps() { 244 return true; 245 } 246}