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 Tomáš Müller<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 if (lecture.getConfiguration() == null) continue; 144 offeringIds.add(lecture.getConfiguration().getOfferingId()); 145 Match m = match.get(lecture.getSchedulingSubpartId()); 146 if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); } 147 m.inc(lecture); 148 } 149 double value = 0.0; 150 for (Match m: match.values()) 151 value += m.value(); 152 ret += value / offeringIds.size(); 153 } 154 return ret; 155 } 156 157 /** 158 * Student group percentage of a solution subset 159 */ 160 public static double gp(TimetableModel model, Collection<Lecture> variables) { 161 if (model.getStudentGroups().isEmpty()) return 0.0; 162 double ret = 0; int count = 0; 163 for (StudentGroup group: model.getStudentGroups()) { 164 Map<Long, Match> match = new HashMap<Long, Match>(); 165 Set<Long> offeringIds = new HashSet<Long>(); 166 for (Student student: group.getStudents()) 167 for (Lecture lecture: student.getLectures()) { 168 if (lecture.getConfiguration() == null) continue; 169 if (variables != null && !variables.contains(lecture)) continue; 170 offeringIds.add(lecture.getConfiguration().getOfferingId()); 171 Match m = match.get(lecture.getSchedulingSubpartId()); 172 if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); } 173 m.inc(lecture); 174 } 175 if (match.isEmpty()) continue; 176 double value = 0.0; 177 for (Match m: match.values()) 178 value += m.value(); 179 ret += value / offeringIds.size(); 180 count ++; 181 } 182 return 100.0 * ret / count; 183 } 184 185 /** 186 * Student group percentage of a solution 187 */ 188 public static double gp(TimetableModel model) { 189 if (model.getStudentGroups().isEmpty()) return 0.0; 190 return 100.0 * group(model) / model.getStudentGroups().size(); 191 } 192 193 /** 194 * Student group percentage of a solution 195 */ 196 public static double gp(Solution<Lecture, Placement> solution) { 197 return gp((TimetableModel)solution.getModel()); 198 } 199 200 /** 201 * Combined weight of a solution 202 */ 203 protected double value(Solution<Lecture, Placement> solution) { 204 return objective(solution) + iGroupWeight * (iModel.getStudentGroups().size() - group(iModel)); 205 } 206 207 @Override 208 public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) { 209 long it = 0, lastImp = 0; 210 double t0 = JProf.currentTimeMillis(); 211 DataProperties cfg = ((TimetableModel)solution.getModel()).getProperties(); 212 long maxIdle = cfg.getPropertyInt("StudentSwaps.MaxIdle", 100000); 213 214 getProgress().setStatus("Student Sectioning..."); 215 getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)"); 216 getProgress().setPhase("Swapping students [HC]...", 1000); 217 StudentSwapGenerator g = new StudentSwapGenerator(); 218 while ((it - lastImp) < maxIdle && (termination == null || termination.canContinue(solution))) { 219 it ++; 220 if ((it % 1000) == 0) { 221 long prg = Math.round(1000.0 * (it - lastImp) / maxIdle); 222 if (getProgress().getProgress() < prg) 223 getProgress().setProgress(prg); 224 if ((it % 10000) == 0) 225 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" + 226 ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%"); 227 } 228 Neighbour<Lecture, Placement> n = g.selectNeighbour(solution); 229 if (n == null) continue; 230 double v = value(n, solution.getAssignment()); 231 if (v < -sEps) { lastImp = it; } 232 if (v <= 0) { n.assign(solution.getAssignment(), it); } 233 } 234 getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)"); 235 236 double f = cfg.getPropertyDouble("StudentSwaps.Deluge.Factor", 0.9999999); 237 double ub = cfg.getPropertyDouble("StudentSwaps.Deluge.UpperBound", 1.10); 238 double lb = cfg.getPropertyDouble("StudentSwaps.Deluge.LowerBound", 0.90); 239 double total = value(solution); 240 double bound = ub * total; 241 double best = total; 242 243 it = 0; lastImp = 0; t0 = JProf.currentTimeMillis(); 244 getProgress().setPhase("Swapping students [GD]...", 1000); 245 while (bound > lb * total && total > 0 && (termination == null || termination.canContinue(solution))) { 246 Neighbour<Lecture, Placement> n = g.selectNeighbour(solution); 247 if (n != null) { 248 double value = value(n, solution.getAssignment()); 249 if (value < 0) { lastImp = it; } 250 if (value <= 0.0 || total + value < bound) { 251 n.assign(solution.getAssignment(), it); 252 if (total + value < best) { 253 best = total + value; 254 } 255 total += value; 256 } 257 } 258 bound *= f; 259 it++; 260 if ((it % 1000) == 0) { 261 long prg = 1000 - Math.round(1000.0 * (bound - lb * best) / (ub * best - lb * best)); 262 if (getProgress().getProgress() < prg) 263 getProgress().setProgress(prg); 264 if ((it % 10000) == 0) { 265 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" + 266 ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%"); 267 getProgress().info("Bound is " + sDF2.format(bound) + ", " + "best value is " + sDF2.format(best) + " (" + sDF2.format(100.0 * bound / best) + "%), " + 268 "current value is " + sDF2.format(total) + " (" + sDF2.format(100.0 * bound / total) + "%)"); 269 } 270 } 271 } 272 getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)"); 273 } 274 275 @Override 276 public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) { 277 if (lecture.students().isEmpty()) return; 278 StudentSwapGenerator g = new StudentSwapGenerator(); 279 long nrIdle = 0, it = 0; 280 while (nrIdle < iMaxIdleResection) { 281 nrIdle ++; it ++; 282 Neighbour<Lecture, Placement> n = g.selectNeighbour(assignment, lecture); 283 if (n == null) continue; 284 double v = value(n, assignment); 285 if (v < -sEps) nrIdle = 0; 286 if (v <= 0.0) n.assign(assignment, it); 287 } 288 } 289 290 /** 291 * Matching students within a scheduling subpart (for student group weight computation) 292 */ 293 private static class Match { 294 private int iTotal = 0; 295 private double iFraction = 1.0; 296 private Map<Long, Integer> iMatch = new HashMap<Long, Integer>(); 297 298 /** 299 * Constructor 300 * @param group student group 301 * @param offeringId offering id 302 */ 303 Match(StudentGroup group, Configuration config) { 304 iTotal = group.countStudents(config.getOfferingId()); 305 iFraction = 1.0 / config.countSubparts(); 306 } 307 308 /** 309 * Increment given lecture 310 */ 311 void inc(Lecture lecture) { 312 Integer val = iMatch.get(lecture.getClassId()); 313 iMatch.put(lecture.getClassId(), 1 + (val == null ? 0 : val.intValue())); 314 } 315 316 /** 317 * Value (an overall probability of two students being in the same lecture) 318 */ 319 double value() { 320 if (iTotal <= 1) return iFraction; 321 double value = 0.0; 322 for (Integer m: iMatch.values()) 323 if (m > 1) 324 value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0)); 325 return iFraction * value; 326 } 327 328 @Override 329 public String toString() { 330 return iTotal + "/" + iMatch; 331 } 332 } 333 334 protected boolean hasStudentGroups(Collection<Student> students) { 335 for (Student student: students) 336 if (!student.getGroups().isEmpty()) return true; 337 return false; 338 } 339 340 @Override 341 protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) { 342 if (hasStudentGroups(students)) { 343 GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students); 344 return sect.getGroups(); 345 } else { 346 return super.studentsToConfigurations(offeringId, students, configurations); 347 } 348 } 349 350 @Override 351 protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) { 352 if (hasStudentGroups(students)) { 353 Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() { 354 @Override 355 public int compare(Lecture l1, Lecture l2) { 356 return l1.getClassId().compareTo(l2.getClassId()); 357 } 358 }); 359 sortedLectures.addAll(lectures); 360 GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students); 361 return sect.getGroups(); 362 } else { 363 return super.studentsToLectures(offeringId, students, lectures); 364 } 365 } 366}