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