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