001package org.cpsolver.coursett.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashSet; 006import java.util.HashMap; 007import java.util.Iterator; 008import java.util.List; 009 010import org.cpsolver.ifs.assignment.Assignment; 011import org.cpsolver.ifs.util.Progress; 012 013 014/** 015 * Student initial sectioning (before a solver is started). <br> 016 * <br> 017 * Many course offerings consist of multiple classes, with students enrolled in 018 * the course divided among them. These classes are often linked by a set of 019 * constraints, namely: 020 * <ul> 021 * <li>Each class has a limit stating the maximum number of students who can be 022 * enrolled in it. 023 * <li>A student must be enrolled in exactly one class for each subpart of a 024 * course. 025 * <li>If two subparts of a course have a parent-child relationship, a student 026 * enrolled in the parent class must also be enrolled in one of the child 027 * classes. 028 * </ul> 029 * Moreover, some of the classes of an offering may be required or prohibited 030 * for certain students, based on reservations that can be set on an offering, a 031 * configuration, or a class. <br> 032 * Before implementing the solver, an initial sectioning of students into 033 * classes is processed. This sectioning is based on Carter's homogeneous 034 * sectioning and is intended to minimize future student conflicts. However, it 035 * is still possible to improve on the number of student conflicts in the 036 * solution. This can be accomplished by moving students between alternative 037 * classes of the same course during or after the search (see 038 * {@link FinalSectioning}). 039 * 040 * @version CourseTT 1.3 (University Course Timetabling)<br> 041 * Copyright (C) 2006 - 2014 Tomas Muller<br> 042 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 043 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 044 * <br> 045 * This library is free software; you can redistribute it and/or modify 046 * it under the terms of the GNU Lesser General Public License as 047 * published by the Free Software Foundation; either version 3 of the 048 * License, or (at your option) any later version. <br> 049 * <br> 050 * This library is distributed in the hope that it will be useful, but 051 * WITHOUT ANY WARRANTY; without even the implied warranty of 052 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 053 * Lesser General Public License for more details. <br> 054 * <br> 055 * You should have received a copy of the GNU Lesser General Public 056 * License along with this library; if not see 057 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 058 */ 059public class InitialSectioning { 060 protected Collection<Student> iStudents = null; 061 protected Group[] iGroups = null; 062 protected Long iOfferingId = null; 063 protected Progress iProgress = null; 064 065 public InitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, Collection<Student> students) { 066 iOfferingId = offeringId; 067 iStudents = new HashSet<Student>(students); 068 iProgress = progress; 069 070 iGroups = new Group[lectureOrConfigurations.size()]; 071 072 int idx = 0; 073 double total = 0; 074 for (Iterator<?> i = lectureOrConfigurations.iterator(); i.hasNext(); idx++) { 075 Object lectureOrConfiguration = i.next(); 076 if (lectureOrConfiguration instanceof Lecture) { 077 Lecture lecture = (Lecture) lectureOrConfiguration; 078 iGroups[idx] = new Group(lecture); 079 } else { 080 Configuration configuration = (Configuration) lectureOrConfiguration; 081 iGroups[idx] = new Group(configuration); 082 } 083 total += iGroups[idx].getMaxSize(); 084 } 085 086 tweakSizes(total); 087 088 progress.trace("Initial sectioning:"); 089 progress.trace(" going to section " + iStudents.size() + " into " + total + " seats"); 090 for (idx = 0; idx < iGroups.length; idx++) 091 progress.trace(" " + (idx + 1) + ". group can accomodate <" + iGroups[idx].getMinSize() + "," 092 + iGroups[idx].getMaxSize() + "> students"); 093 } 094 095 protected void tweakSizes(double total) { 096 if (total == 0) { 097 for (int idx = 0; idx < iGroups.length; idx++) { 098 iGroups[idx].setMaxSize(1); 099 total++; 100 } 101 } 102 103 double studentsWeight = 0; 104 for (Student s : iStudents) { 105 studentsWeight += s.getOfferingWeight(iOfferingId); 106 } 107 108 double factor = studentsWeight / total; 109 for (int idx = 0; idx < iGroups.length; idx++) { 110 iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize()); 111 iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize())); 112 } 113 } 114 115 public void addStudent(Student student) { 116 iStudents.add(student); 117 } 118 119 private boolean moveAwayOneStudent(Group group) { 120 Group newGroup = null; 121 Student movingStudent = null; 122 double curDist = 0, newDist = 0; 123 124 for (Student student : group.getStudents()) { 125 if (group.isEnrolled(student)) 126 continue; 127 double cd = group.getDistance(student); 128 for (int x = 0; x < iGroups.length; x++) { 129 if (group.equals(iGroups[x])) 130 continue; 131 if (iGroups[x].size() > iGroups[x].getMaxSize()) 132 continue; 133 if (!iGroups[x].canEnroll(student)) 134 continue; 135 double nd = iGroups[x].getDistance(student); 136 if (newGroup == null || newDist - curDist < nd - cd) { 137 newGroup = iGroups[x]; 138 movingStudent = student; 139 curDist = cd; 140 newDist = nd; 141 if (newDist - curDist < 0.01) 142 break; 143 } 144 } 145 } 146 147 if (newGroup != null) { 148 group.removeStudent(movingStudent); 149 newGroup.addStudent(movingStudent); 150 return true; 151 } 152 153 return false; 154 } 155 156 public boolean moveIntoOneStudent(Group group) { 157 Group oldGroup = null; 158 Student movingStudent = null; 159 double curDist = 0, newDist = 0; 160 161 for (int x = 0; x < iGroups.length; x++) { 162 if (group.equals(iGroups[x])) 163 continue; 164 if (iGroups[x].size() <= iGroups[x].getMinSize()) 165 continue; 166 for (Student student : iGroups[x].getStudents()) { 167 if (!group.canEnroll(student)) 168 continue; 169 if (iGroups[x].isEnrolled(student)) 170 continue; 171 double cd = iGroups[x].getDistance(student); 172 double nd = group.getDistance(student); 173 if (oldGroup == null || newDist - curDist < nd - cd) { 174 oldGroup = iGroups[x]; 175 movingStudent = student; 176 curDist = cd; 177 newDist = nd; 178 if (newDist - curDist < 0.01) 179 break; 180 } 181 } 182 } 183 184 if (oldGroup != null) { 185 oldGroup.removeStudent(movingStudent); 186 group.addStudent(movingStudent); 187 return true; 188 } 189 190 return false; 191 } 192 193 public Group[] getGroups() { 194 double minDist = 1.0 / iGroups.length; 195 196 for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) { 197 Student student = i.next(); 198 Group group = null; 199 for (int idx = 0; idx < iGroups.length; idx++) { 200 if (iGroups[idx].isEnrolled(student)) { 201 group = iGroups[idx]; 202 break; 203 } 204 } 205 if (group != null) { 206 group.addStudent(student); 207 i.remove(); 208 } 209 } 210 211 for (Student student : iStudents) { 212 double studentWeight = student.getOfferingWeight(iOfferingId); 213 214 Group group = null; 215 double dist = 0.0; 216 for (int idx = 0; idx < iGroups.length; idx++) { 217 Group g = iGroups[idx]; 218 if (!g.canEnroll(student)) 219 continue; 220 if (g.size() + studentWeight > g.getMaxSize()) 221 continue; 222 double d = g.getDistance(student); 223 if (group == null || d < dist) { 224 group = g; 225 dist = d; 226 if (d < minDist) 227 break; 228 } 229 } 230 231 if (group != null) { 232 group.addStudent(student); 233 continue; 234 } 235 236 // disobey max size, but prefer sections with smallest excess 237 int excess = 0; 238 for (int idx = 0; idx < iGroups.length; idx++) { 239 Group g = iGroups[idx]; 240 if (!g.canEnroll(student)) 241 continue; 242 double d = g.getDistance(student); 243 int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize()); 244 if (group == null || ex < excess || (ex == excess && d < dist)) { 245 group = g; 246 dist = d; 247 excess = ex; 248 } 249 } 250 251 if (group != null) { 252 group.addStudent(student); 253 continue; 254 } 255 256 // disobey max size & can enroll 257 for (int idx = 0; idx < iGroups.length; idx++) { 258 Group g = iGroups[idx]; 259 double d = g.getDistance(student); 260 if (group == null || d < dist) { 261 group = g; 262 dist = d; 263 } 264 } 265 266 iProgress.debug("Unable to find a valid section for student " 267 + student.getId() 268 + ", enrolling to " 269 + (group.getLecture() != null ? group.getLecture().getName() : group.getConfiguration() 270 .getConfigId().toString())); 271 272 group.addStudent(student); 273 } 274 275 for (int idx = 0; idx < iGroups.length; idx++) { 276 Group group = iGroups[idx]; 277 278 while (group.size() > group.getMaxSize()) { 279 if (!moveAwayOneStudent(group)) 280 break; 281 } 282 283 while (group.size() > group.getMaxSize()) { 284 285 Group newGroup = null; 286 Student movingStudent = null; 287 288 for (Student student : group.getStudents()) { 289 if (group.isEnrolled(student)) 290 continue; 291 for (int x = 0; x < iGroups.length; x++) { 292 if (idx == x) 293 continue; 294 if (!iGroups[x].canEnroll(student)) 295 continue; 296 while (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) { 297 if (!moveAwayOneStudent(iGroups[x])) 298 break; 299 } 300 if (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) 301 continue; 302 newGroup = iGroups[x]; 303 movingStudent = student; 304 break; 305 } 306 if (newGroup != null) 307 break; 308 } 309 310 if (newGroup != null) { 311 group.removeStudent(movingStudent); 312 newGroup.addStudent(movingStudent); 313 } else { 314 break; 315 } 316 } 317 318 while (group.size() < group.getMinSize()) { 319 if (!moveIntoOneStudent(group)) 320 break; 321 } 322 } 323 324 return iGroups; 325 } 326 327 public class Group { 328 private ArrayList<Student> iStudents = new ArrayList<Student>(); 329 private Lecture iLecture = null; 330 private Configuration iConfiguration = null; 331 private Double iDist = null; 332 private double iMinSize = 0, iMaxSize = 0; 333 private HashMap<Student, Double> iDistCache = new HashMap<Student, Double>(); 334 private double iSize = 0.0; 335 336 public Group(Lecture lecture) { 337 iLecture = lecture; 338 iMinSize = lecture.minClassLimit(); 339 iMaxSize = lecture.maxAchievableClassLimit(); 340 } 341 342 public Group(Configuration configuration) { 343 iConfiguration = configuration; 344 iMinSize = iMaxSize = iConfiguration.getLimit(); 345 } 346 347 public Configuration getConfiguration() { 348 return iConfiguration; 349 } 350 351 public Lecture getLecture() { 352 return iLecture; 353 } 354 355 public double getMinSize() { 356 return iMinSize; 357 } 358 359 public double getMaxSize() { 360 return iMaxSize; 361 } 362 363 public void setMinSize(double minSize) { 364 iMinSize = minSize; 365 } 366 367 public void setMaxSize(double maxSize) { 368 iMaxSize = maxSize; 369 } 370 371 public double getDistance() { 372 if (iDist == null) { 373 double dist = 0.0; 374 double prob = 10.0 / iStudents.size(); 375 int cnt = 0; 376 for (Student s1 : iStudents) { 377 if (Math.random() < prob) { 378 for (Student s2 : iStudents) { 379 if (s1.getId().compareTo(s2.getId()) <= 0) 380 continue; 381 if (Math.random() < prob) { 382 dist += s1.getDistance(s2); 383 cnt++; 384 } 385 } 386 } 387 } 388 iDist = new Double(dist / cnt); 389 } 390 return iDist.doubleValue(); 391 } 392 393 public double getDistance(Student student) { 394 Double cachedDist = iDistCache.get(student); 395 if (cachedDist != null) 396 return cachedDist.doubleValue(); 397 double dist = 0.0; 398 double prob = 10.0 / iStudents.size(); 399 int cnt = 0; 400 for (Student s : iStudents) { 401 if (prob >= 1.0 || Math.random() < prob) { 402 dist += s.getDistance(student); 403 cnt++; 404 } 405 } 406 iDistCache.put(student, new Double(dist / cnt)); 407 return dist / cnt; 408 } 409 410 public void addStudent(Student student) { 411 iStudents.add(student); 412 iSize += student.getOfferingWeight(iOfferingId); 413 iDist = null; 414 iDistCache.clear(); 415 } 416 417 public void removeStudent(Student student) { 418 iStudents.remove(student); 419 iSize -= student.getOfferingWeight(iOfferingId); 420 iDist = null; 421 iDistCache.clear(); 422 } 423 424 public List<Student> getStudents() { 425 return iStudents; 426 } 427 428 public double size() { 429 return iSize; 430 } 431 432 @Override 433 public String toString() { 434 return "{" + size() + "-" + getDistance() + "/" + getStudents() + "}"; 435 } 436 437 public boolean canEnroll(Student student) { 438 if (getLecture() != null) { 439 return student.canEnroll(getLecture()); 440 } else { 441 for (Long subpartId: getConfiguration().getTopSubpartIds()) { 442 boolean canEnrollThisSubpart = false; 443 for (Lecture lecture : getConfiguration().getTopLectures(subpartId)) { 444 if (student.canEnroll(lecture)) { 445 canEnrollThisSubpart = true; 446 break; 447 } 448 } 449 if (!canEnrollThisSubpart) 450 return false; 451 } 452 return true; 453 } 454 } 455 456 public boolean isEnrolled(Student student) { 457 if (getLecture() != null) { 458 return student.getLectures().contains(getLecture()); 459 } else { 460 for (Lecture lect : student.getLectures()) { 461 if (lect.getConfiguration().equals(getConfiguration())) 462 return true; 463 } 464 return false; 465 } 466 467 } 468 } 469 470 public static void initialSectioningCfg(Assignment<Lecture, Placement> assignment, Progress p, Long offeringId, String courseName, Collection<Student> students, 471 List<Configuration> configurations) { 472 if (students == null || students.isEmpty()) 473 return; 474 if (configurations == null || configurations.isEmpty()) 475 return; 476 if (configurations.size() == 1) { 477 Configuration cfg = configurations.get(0); 478 for (Student st : students) { 479 st.addConfiguration(cfg); 480 } 481 for (Long subpartId: cfg.getTopSubpartIds()) { 482 initialSectioning(assignment, p, offeringId, courseName, students, cfg.getTopLectures(subpartId)); 483 } 484 } else { 485 p.trace("sectioning " + students.size() + " students of course " + courseName + " into " 486 + configurations.size() + " configurations"); 487 InitialSectioning sect = new InitialSectioning(p, offeringId, configurations, students); 488 Group[] studentsPerSection = sect.getGroups(); 489 for (int i = 0; i < configurations.size(); i++) { 490 Group group = studentsPerSection[i]; 491 p.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" 492 + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")"); 493 for (Student st : group.getStudents()) { 494 st.addConfiguration(group.getConfiguration()); 495 } 496 for (Long subpartId: group.getConfiguration().getTopSubpartIds()) { 497 initialSectioning(assignment, p, offeringId, courseName, group.getStudents(), group.getConfiguration().getTopLectures(subpartId)); 498 } 499 } 500 } 501 } 502 503 private static String getClassLabel(Lecture lecture) { 504 return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>"; 505 } 506 507 private static void initialSectioning(Assignment<Lecture, Placement> assignment, Progress p, Long offeringId, String parentName, Collection<Student> students, 508 Collection<Lecture> lectures) { 509 if (lectures == null || lectures.isEmpty()) 510 return; 511 if (students == null || students.isEmpty()) 512 return; 513 for (Lecture lecture : lectures) { 514 if (lecture.classLimit(assignment) == 0 && !lecture.isCommitted()) 515 p.warn("Class " + getClassLabel(lecture) + " has zero class limit."); 516 } 517 518 p.trace("sectioning " + students.size() + " students of course " + parentName + " into " + lectures.size() 519 + " sections"); 520 if (lectures.size() == 1) { 521 Lecture lect = lectures.iterator().next(); 522 for (Student st : students) { 523 if (!st.canEnroll(lect)) { 524 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 525 } 526 lect.addStudent(assignment, st); 527 st.addLecture(lect); 528 } 529 if (lect.hasAnyChildren()) { 530 for (Long subpartId: lect.getChildrenSubpartIds()) { 531 List<Lecture> children = lect.getChildren(subpartId); 532 initialSectioning(assignment, p, offeringId, lect.getName(), students, children); 533 } 534 } 535 } else { 536 InitialSectioning sect = new InitialSectioning(p, offeringId, lectures, students); 537 Group[] studentsPerSection = sect.getGroups(); 538 for (int i = 0; i < studentsPerSection.length; i++) { 539 Group group = studentsPerSection[i]; 540 Lecture lect = group.getLecture(); 541 if (group.getStudents().isEmpty()) { 542 p.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit(assignment) + ")"); 543 continue; 544 } 545 p.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() 546 + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit(assignment) + ")"); 547 List<Student> studentsThisSection = group.getStudents(); 548 for (Student st : studentsThisSection) { 549 if (!st.canEnroll(lect)) { 550 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 551 } 552 lect.addStudent(assignment, st); 553 st.addLecture(lect); 554 } 555 if (lect.hasAnyChildren()) { 556 for (Long subpartId: lect.getChildrenSubpartIds()) { 557 List<Lecture> children = lect.getChildren(subpartId); 558 initialSectioning(assignment, p, offeringId, lect.getName(), studentsThisSection, children); 559 } 560 } 561 } 562 } 563 } 564 565}