001package org.cpsolver.coursett.sectioning; 002 003import java.util.Collection; 004import java.util.Comparator; 005import java.util.HashMap; 006import java.util.HashSet; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010import java.util.TreeSet; 011 012import org.cpsolver.coursett.constraint.JenrlConstraint; 013import org.cpsolver.coursett.criteria.StudentConflict; 014import org.cpsolver.coursett.model.Configuration; 015import org.cpsolver.coursett.model.DefaultStudentSectioning; 016import org.cpsolver.coursett.model.InitialSectioning.Group; 017import org.cpsolver.coursett.model.Lecture; 018import org.cpsolver.coursett.model.Placement; 019import org.cpsolver.coursett.model.Student; 020import org.cpsolver.coursett.model.StudentGroup; 021import org.cpsolver.coursett.model.TimetableModel; 022import org.cpsolver.coursett.sectioning.SctSectioning.GroupBasedInitialSectioning; 023import org.cpsolver.ifs.assignment.Assignment; 024import org.cpsolver.ifs.model.InfoProvider; 025import org.cpsolver.ifs.model.Neighbour; 026import org.cpsolver.ifs.solution.Solution; 027import org.cpsolver.ifs.termination.TerminationCondition; 028import org.cpsolver.ifs.util.DataProperties; 029import org.cpsolver.ifs.util.JProf; 030 031/** 032 * Student sectioning implementation based on local search. A student swap is 033 * generated in each iteration using Hill Climbing and Great Deluge algorithms. 034 * 035 * @version CourseTT 1.3 (University Course Timetabling)<br> 036 * Copyright (C) 2017 Tomáš Müller<br> 037 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 038 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 039 * <br> 040 * This library is free software; you can redistribute it and/or modify 041 * it under the terms of the GNU Lesser General Public License as 042 * published by the Free Software Foundation; either version 3 of the 043 * License, or (at your option) any later version. <br> 044 * <br> 045 * This library is distributed in the hope that it will be useful, but 046 * WITHOUT ANY WARRANTY; without even the implied warranty of 047 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 048 * Lesser General Public License for more details. <br> 049 * <br> 050 * You should have received a copy of the GNU Lesser General Public 051 * License along with this library; if not see 052 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 053 */ 054public class StudentSwapSectioning extends DefaultStudentSectioning implements InfoProvider<Lecture, Placement> { 055 private static double sEps = 0.0001; 056 private double iGroupWeight = 0.1; 057 private int iMaxIdleResection = 1000; 058 059 public StudentSwapSectioning(TimetableModel model) { 060 super(model); 061 iGroupWeight = model.getProperties().getPropertyDouble("StudentSwaps.GroupWeight", 10.0); 062 iMaxIdleResection = model.getProperties().getPropertyInt("StudentSwaps.MaxIdleResection", 1000); 063 } 064 065 protected List<StudentConflict> getStudentConflictCriteria() { 066 if (iModel != null) return iModel.getStudentConflictCriteria(); 067 return null; 068 } 069 070 @Override 071 public boolean hasFinalSectioning() { 072 return true; 073 } 074 075 /** 076 * Student conflict weight change of a student swap 077 */ 078 protected double objective(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) { 079 if (n instanceof StudentMove) 080 return ((StudentMove)n).value(getStudentConflictCriteria(), assignment); 081 return n.value(assignment); 082 } 083 084 /** 085 * Student group weight change of a student swap 086 */ 087 protected double group(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) { 088 if (n instanceof StudentMove) 089 return ((StudentMove)n).group(getStudentConflictCriteria(), assignment); 090 return 0.0; 091 } 092 093 /** 094 * Combined weight change of a student swap 095 */ 096 protected double value(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) { 097 if (n instanceof StudentMove) 098 return ((StudentMove)n).value(getStudentConflictCriteria(), assignment) - iGroupWeight * ((StudentMove)n).group(getStudentConflictCriteria(), assignment); 099 return n.value(assignment); 100 } 101 102 /** 103 * Student conflict weight of a solution 104 */ 105 protected double objective(Solution<Lecture, Placement> solution) { 106 List<StudentConflict> criteria = getStudentConflictCriteria(); 107 108 if (criteria == null) { 109 double value = 0.0; 110 for (JenrlConstraint constraint: ((TimetableModel)solution.getModel()).getJenrlConstraints()) { 111 if (constraint.isInConflict(solution.getAssignment())) value += constraint.jenrl(); 112 } 113 return value; 114 } 115 116 double value = 0.0; 117 for (StudentConflict criterion: criteria) 118 value += criterion.getWeightedValue(solution.getAssignment()); 119 return value; 120 } 121 122 /** 123 * Student group weight of a solution 124 */ 125 public static double group(TimetableModel model) { 126 double ret = 0; 127 for (StudentGroup group: model.getStudentGroups()) { 128 Map<Long, Match> match = new HashMap<Long, Match>(); 129 Set<Long> offeringIds = new HashSet<Long>(); 130 for (Student student: group.getStudents()) 131 for (Lecture lecture: student.getLectures()) { 132 if (lecture.getConfiguration() == null) continue; 133 offeringIds.add(lecture.getConfiguration().getOfferingId()); 134 Match m = match.get(lecture.getSchedulingSubpartId()); 135 if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); } 136 m.inc(lecture); 137 } 138 double value = 0.0; 139 for (Match m: match.values()) 140 value += m.value(); 141 ret += value / offeringIds.size(); 142 } 143 return ret; 144 } 145 146 /** 147 * Student group percentage of a solution subset 148 */ 149 public static double gp(TimetableModel model, Collection<Lecture> variables) { 150 if (model.getStudentGroups().isEmpty()) return 0.0; 151 double ret = 0; int count = 0; 152 for (StudentGroup group: model.getStudentGroups()) { 153 Map<Long, Match> match = new HashMap<Long, Match>(); 154 Set<Long> offeringIds = new HashSet<Long>(); 155 for (Student student: group.getStudents()) 156 for (Lecture lecture: student.getLectures()) { 157 if (lecture.getConfiguration() == null) continue; 158 if (variables != null && !variables.contains(lecture)) continue; 159 offeringIds.add(lecture.getConfiguration().getOfferingId()); 160 Match m = match.get(lecture.getSchedulingSubpartId()); 161 if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); } 162 m.inc(lecture); 163 } 164 if (match.isEmpty()) continue; 165 double value = 0.0; 166 for (Match m: match.values()) 167 value += m.value(); 168 ret += value / offeringIds.size(); 169 count ++; 170 } 171 return 100.0 * ret / count; 172 } 173 174 /** 175 * Student group percentage of a solution 176 */ 177 public static double gp(TimetableModel model) { 178 if (model.getStudentGroups().isEmpty()) return 0.0; 179 return 100.0 * group(model) / model.getStudentGroups().size(); 180 } 181 182 /** 183 * Student group percentage of a solution 184 */ 185 public static double gp(Solution<Lecture, Placement> solution) { 186 return gp((TimetableModel)solution.getModel()); 187 } 188 189 /** 190 * Combined weight of a solution 191 */ 192 protected double value(Solution<Lecture, Placement> solution) { 193 return objective(solution) + iGroupWeight * (iModel.getStudentGroups().size() - group(iModel)); 194 } 195 196 @Override 197 public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) { 198 long it = 0, lastImp = 0; 199 double t0 = JProf.currentTimeMillis(); 200 DataProperties cfg = ((TimetableModel)solution.getModel()).getProperties(); 201 long maxIdle = cfg.getPropertyInt("StudentSwaps.MaxIdle", 100000); 202 203 getProgress().setStatus("Student Sectioning..."); 204 getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)"); 205 getProgress().setPhase("Swapping students [HC]...", 1000); 206 StudentSwapGenerator g = new StudentSwapGenerator(); 207 while ((it - lastImp) < maxIdle && (termination == null || termination.canContinue(solution))) { 208 it ++; 209 if ((it % 1000) == 0) { 210 long prg = Math.round(1000.0 * (it - lastImp) / maxIdle); 211 if (getProgress().getProgress() < prg) 212 getProgress().setProgress(prg); 213 if ((it % 10000) == 0) 214 getProgress().info("Iter=" + (it / 1000)+"k, Idle=" + sDF2.format((it - lastImp)/1000.0)+"k, Speed=" + sDF2.format(1000.0 * it / (JProf.currentTimeMillis() - t0))+" it/s" + 215 ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%"); 216 } 217 Neighbour<Lecture, Placement> n = g.selectNeighbour(solution); 218 if (n == null) continue; 219 double v = value(n, solution.getAssignment()); 220 if (v < -sEps) { lastImp = it; } 221 if (v <= 0) { n.assign(solution.getAssignment(), it); } 222 } 223 getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)"); 224 225 double f = cfg.getPropertyDouble("StudentSwaps.Deluge.Factor", 0.9999999); 226 double ub = cfg.getPropertyDouble("StudentSwaps.Deluge.UpperBound", 1.10); 227 double lb = cfg.getPropertyDouble("StudentSwaps.Deluge.LowerBound", 0.90); 228 double total = value(solution); 229 double bound = ub * total; 230 double best = total; 231 232 it = 0; lastImp = 0; t0 = JProf.currentTimeMillis(); 233 getProgress().setPhase("Swapping students [GD]...", 1000); 234 while (bound > lb * total && total > 0 && (termination == null || termination.canContinue(solution))) { 235 Neighbour<Lecture, Placement> n = g.selectNeighbour(solution); 236 if (n != null) { 237 double value = value(n, solution.getAssignment()); 238 if (value < 0) { lastImp = it; } 239 if (value <= 0.0 || total + value < bound) { 240 n.assign(solution.getAssignment(), it); 241 if (total + value < best) { 242 best = total + value; 243 } 244 total += value; 245 } 246 } 247 bound *= f; 248 it++; 249 if ((it % 1000) == 0) { 250 long prg = 1000 - Math.round(1000.0 * (bound - lb * best) / (ub * best - lb * best)); 251 if (getProgress().getProgress() < prg) 252 getProgress().setProgress(prg); 253 if ((it % 10000) == 0) { 254 getProgress().info("Iter=" + (it / 1000)+"k, Idle=" + sDF2.format((it - lastImp)/1000.0)+"k, Speed=" + sDF2.format(1000.0 * it / (JProf.currentTimeMillis() - t0))+" it/s" + 255 ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%"); 256 getProgress().info("Bound is " + sDF2.format(bound) + ", " + "best value is " + sDF2.format(best) + " (" + sDF2.format(100.0 * bound / best) + "%), " + 257 "current value is " + sDF2.format(total) + " (" + sDF2.format(100.0 * bound / total) + "%)"); 258 } 259 } 260 } 261 getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)"); 262 } 263 264 @Override 265 public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) { 266 if (lecture.students().isEmpty()) return; 267 StudentSwapGenerator g = new StudentSwapGenerator(); 268 long nrIdle = 0, it = 0; 269 while (nrIdle < iMaxIdleResection) { 270 nrIdle ++; it ++; 271 Neighbour<Lecture, Placement> n = g.selectNeighbour(assignment, lecture); 272 if (n == null) continue; 273 double v = value(n, assignment); 274 if (v < -sEps) nrIdle = 0; 275 if (v <= 0.0) n.assign(assignment, it); 276 } 277 } 278 279 /** 280 * Matching students within a scheduling subpart (for student group weight computation) 281 */ 282 private static class Match { 283 private int iTotal = 0; 284 private double iFraction = 1.0; 285 private Map<Long, Integer> iMatch = new HashMap<Long, Integer>(); 286 287 /** 288 * Constructor 289 * @param group student group 290 * @param offeringId offering id 291 */ 292 Match(StudentGroup group, Configuration config) { 293 iTotal = group.countStudents(config.getOfferingId()); 294 iFraction = 1.0 / config.countSubparts(); 295 } 296 297 /** 298 * Increment given lecture 299 */ 300 void inc(Lecture lecture) { 301 Integer val = iMatch.get(lecture.getClassId()); 302 iMatch.put(lecture.getClassId(), 1 + (val == null ? 0 : val.intValue())); 303 } 304 305 /** 306 * Value (an overall probability of two students being in the same lecture) 307 */ 308 double value() { 309 if (iTotal <= 1) return iFraction; 310 double value = 0.0; 311 for (Integer m: iMatch.values()) 312 if (m > 1) 313 value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0)); 314 return iFraction * value; 315 } 316 317 @Override 318 public String toString() { 319 return iTotal + "/" + iMatch; 320 } 321 } 322 323 protected boolean hasStudentGroups(Collection<Student> students) { 324 for (Student student: students) 325 if (!student.getGroups().isEmpty()) return true; 326 return false; 327 } 328 329 @Override 330 protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) { 331 if (hasStudentGroups(students)) { 332 GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students); 333 return sect.getGroups(); 334 } else { 335 return super.studentsToConfigurations(offeringId, students, configurations); 336 } 337 } 338 339 @Override 340 protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) { 341 if (hasStudentGroups(students)) { 342 Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() { 343 @Override 344 public int compare(Lecture l1, Lecture l2) { 345 return l1.getClassId().compareTo(l2.getClassId()); 346 } 347 }); 348 sortedLectures.addAll(lectures); 349 GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students); 350 return sect.getGroups(); 351 } else { 352 return super.studentsToLectures(offeringId, students, lectures); 353 } 354 } 355}