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 Tomáš Müller<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 protected static double sNominalWeight = 0.00001; 065 066 public InitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, Collection<Student> students) { 067 iOfferingId = offeringId; 068 iStudents = new HashSet<Student>(students); 069 iProgress = progress; 070 071 iGroups = new Group[lectureOrConfigurations.size()]; 072 073 int idx = 0; 074 double total = 0; 075 for (Iterator<?> i = lectureOrConfigurations.iterator(); i.hasNext(); idx++) { 076 Object lectureOrConfiguration = i.next(); 077 if (lectureOrConfiguration instanceof Lecture) { 078 Lecture lecture = (Lecture) lectureOrConfiguration; 079 iGroups[idx] = new Group(lecture); 080 } else { 081 Configuration configuration = (Configuration) lectureOrConfiguration; 082 iGroups[idx] = new Group(configuration); 083 } 084 total += iGroups[idx].getMaxSize(); 085 } 086 087 tweakSizes(total); 088 089 progress.trace("Initial sectioning:"); 090 progress.trace(" going to section " + iStudents.size() + " into " + total + " seats"); 091 for (idx = 0; idx < iGroups.length; idx++) 092 progress.trace(" " + (idx + 1) + ". group can accomodate <" + iGroups[idx].getMinSize() + "," 093 + iGroups[idx].getMaxSize() + "> students"); 094 } 095 096 protected Progress getProgress() { 097 return iProgress; 098 } 099 100 protected void tweakSizes(double total) { 101 if (total == 0) { 102 for (int idx = 0; idx < iGroups.length; idx++) { 103 iGroups[idx].setMaxSize(1); 104 total++; 105 } 106 } 107 108 double studentsWeight = 0; 109 for (Student s : iStudents) { 110 studentsWeight += s.getOfferingWeight(iOfferingId); 111 } 112 113 double factor = studentsWeight / total; 114 for (int idx = 0; idx < iGroups.length; idx++) { 115 iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize()); 116 iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize())); 117 } 118 } 119 120 public void addStudent(Student student) { 121 iStudents.add(student); 122 } 123 124 private boolean moveAwayOneStudent(Group group) { 125 Group newGroup = null; 126 Student movingStudent = null; 127 double curDist = 0, newDist = 0; 128 129 for (Student student : group.getStudents()) { 130 if (group.isEnrolled(student)) 131 continue; 132 double cd = group.getDistance(student); 133 for (int x = 0; x < iGroups.length; x++) { 134 if (group.equals(iGroups[x])) 135 continue; 136 if (iGroups[x].size(student) > iGroups[x].getMaxSize()) 137 continue; 138 if (!iGroups[x].canEnroll(student)) 139 continue; 140 double nd = iGroups[x].getDistance(student); 141 if (newGroup == null || newDist - curDist > nd - cd) { 142 newGroup = iGroups[x]; 143 movingStudent = student; 144 curDist = cd; 145 newDist = nd; 146 if (newDist - curDist < 0.01) 147 break; 148 } 149 } 150 } 151 152 if (newGroup != null) { 153 group.removeStudent(movingStudent); 154 newGroup.addStudent(movingStudent); 155 return true; 156 } 157 158 return false; 159 } 160 161 public boolean moveIntoOneStudent(Group group) { 162 Group oldGroup = null; 163 Student movingStudent = null; 164 double curDist = 0, newDist = 0; 165 166 for (int x = 0; x < iGroups.length; x++) { 167 if (group.equals(iGroups[x])) 168 continue; 169 if (iGroups[x].size() <= iGroups[x].getMinSize()) 170 continue; 171 for (Student student : iGroups[x].getStudents()) { 172 if (!group.canEnroll(student)) 173 continue; 174 if (iGroups[x].isEnrolled(student)) 175 continue; 176 double cd = iGroups[x].getDistance(student); 177 double nd = group.getDistance(student); 178 if (oldGroup == null || newDist - curDist > nd - cd) { 179 oldGroup = iGroups[x]; 180 movingStudent = student; 181 curDist = cd; 182 newDist = nd; 183 if (newDist - curDist < 0.01) 184 break; 185 } 186 } 187 } 188 189 if (oldGroup != null) { 190 oldGroup.removeStudent(movingStudent); 191 group.addStudent(movingStudent); 192 return true; 193 } 194 195 return false; 196 } 197 198 public Group[] getGroups() { 199 for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) { 200 Student student = i.next(); 201 Group group = null; 202 for (int idx = 0; idx < iGroups.length; idx++) { 203 if (iGroups[idx].isEnrolled(student)) { 204 group = iGroups[idx]; 205 break; 206 } 207 } 208 if (group != null) { 209 group.addStudent(student); 210 i.remove(); 211 } 212 } 213 214 for (Student student : iStudents) { 215 double studentWeight = student.getOfferingWeight(iOfferingId); 216 217 Group group = null; 218 double dist = 0.0; double size = 0.0; 219 for (int idx = 0; idx < iGroups.length; idx++) { 220 Group g = iGroups[idx]; 221 if (!g.canEnroll(student)) 222 continue; 223 if (g.size(student) > g.getMaxSize()) 224 continue; 225 double d = g.getDistance(student); 226 if (group == null || d < dist || (d == dist || size < g.size())) { 227 group = g; 228 dist = d; 229 size = g.size(); 230 } 231 } 232 233 if (group != null) { 234 group.addStudent(student); 235 continue; 236 } 237 238 // disobey max size, but prefer sections with smallest excess 239 int excess = 0; 240 for (int idx = 0; idx < iGroups.length; idx++) { 241 Group g = iGroups[idx]; 242 if (!g.canEnroll(student)) 243 continue; 244 double d = g.getDistance(student); 245 int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize()); 246 if (group == null || ex < excess || (ex == excess && d < dist)) { 247 group = g; 248 dist = d; 249 excess = ex; 250 } 251 } 252 253 if (group != null) { 254 group.addStudent(student); 255 continue; 256 } 257 258 // disobey max size & can enroll 259 for (int idx = 0; idx < iGroups.length; idx++) { 260 Group g = iGroups[idx]; 261 double d = g.getDistance(student); 262 if (group == null || d < dist) { 263 group = g; 264 dist = d; 265 } 266 } 267 268 iProgress.debug("Unable to find a valid section for student " 269 + student.getId() 270 + ", enrolling to " 271 + (group.getLecture() != null ? group.getLecture().getName() : group.getConfiguration() 272 .getConfigId().toString())); 273 274 group.addStudent(student); 275 } 276 277 for (int idx = 0; idx < iGroups.length; idx++) { 278 Group group = iGroups[idx]; 279 280 while (group.size(null) > group.getMaxSize()) { 281 if (!moveAwayOneStudent(group)) 282 break; 283 } 284 285 while (group.size(null) > group.getMaxSize()) { 286 287 Group newGroup = null; 288 Student movingStudent = null; 289 290 for (Student student : group.getStudents()) { 291 if (group.isEnrolled(student)) 292 continue; 293 for (int x = 0; x < iGroups.length; x++) { 294 if (idx == x) 295 continue; 296 if (!iGroups[x].canEnroll(student)) 297 continue; 298 while (iGroups[x].size(student) > iGroups[x].getMaxSize()) { 299 if (!moveAwayOneStudent(iGroups[x])) 300 break; 301 } 302 if (iGroups[x].size(student) > iGroups[x].getMaxSize()) 303 continue; 304 newGroup = iGroups[x]; 305 movingStudent = student; 306 break; 307 } 308 if (newGroup != null) 309 break; 310 } 311 312 if (newGroup != null) { 313 group.removeStudent(movingStudent); 314 newGroup.addStudent(movingStudent); 315 } else { 316 break; 317 } 318 } 319 320 while (group.size() < group.getMinSize()) { 321 if (!moveIntoOneStudent(group)) 322 break; 323 } 324 } 325 326 return iGroups; 327 } 328 329 public class Group { 330 private ArrayList<Student> iStudents = new ArrayList<Student>(); 331 private Lecture iLecture = null; 332 private Configuration iConfiguration = null; 333 private Double iDist = null; 334 private double iMinSize = 0, iMaxSize = 0; 335 private HashMap<Student, Double> iDistCache = new HashMap<Student, Double>(); 336 private double iSize = 0.0; 337 338 public Group(Lecture lecture) { 339 iLecture = lecture; 340 iMinSize = lecture.minClassLimit(); 341 iMaxSize = lecture.maxAchievableClassLimit(); 342 } 343 344 public Group(Configuration configuration) { 345 iConfiguration = configuration; 346 iMinSize = iMaxSize = iConfiguration.getLimit(); 347 } 348 349 public Configuration getConfiguration() { 350 return iConfiguration; 351 } 352 353 public Lecture getLecture() { 354 return iLecture; 355 } 356 357 public double getMinSize() { 358 return iMinSize; 359 } 360 361 public double getMaxSize() { 362 return iMaxSize; 363 } 364 365 public void setMinSize(double minSize) { 366 iMinSize = minSize; 367 } 368 369 public void setMaxSize(double maxSize) { 370 iMaxSize = maxSize; 371 } 372 373 public double getStudentWeight(Student student) { 374 double max = 0.0; 375 for (Student s: iStudents) { 376 double w = s.getOfferingWeight(iOfferingId); 377 if (w > max) max = w; 378 } 379 if (student != null) { 380 double w = student.getOfferingWeight(iOfferingId); 381 if (w > max) max = w; 382 } 383 return (student == null ? 0.0 : student.getOfferingWeight(iOfferingId)) + sNominalWeight - max; 384 } 385 386 public double getDistance() { 387 if (iDist == null) { 388 double dist = 0.0; 389 double prob = 10.0 / iStudents.size(); 390 int cnt = 0; 391 for (Student s1 : iStudents) { 392 if (Math.random() < prob) { 393 for (Student s2 : iStudents) { 394 if (s1.getId().compareTo(s2.getId()) <= 0) 395 continue; 396 if (Math.random() < prob) { 397 dist += s1.getDistance(s2); 398 cnt++; 399 } 400 } 401 } 402 } 403 iDist = Double.valueOf(dist / cnt); 404 } 405 return iDist.doubleValue(); 406 } 407 408 public double getDistance(Student student) { 409 if (iStudents.isEmpty()) return 0.0; 410 Double cachedDist = iDistCache.get(student); 411 if (cachedDist != null) 412 return cachedDist.doubleValue(); 413 double dist = 0.0; 414 int cnt = 0; 415 for (Student s : iStudents) { 416 dist += s.getDistance(student); 417 cnt++; 418 } 419 iDistCache.put(student, dist / cnt); 420 return dist / cnt; 421 } 422 423 public void addStudent(Student student) { 424 iStudents.add(student); 425 iSize += student.getOfferingWeight(iOfferingId); 426 iDist = null; 427 iDistCache.clear(); 428 } 429 430 public void removeStudent(Student student) { 431 iStudents.remove(student); 432 iSize -= student.getOfferingWeight(iOfferingId); 433 iDist = null; 434 iDistCache.clear(); 435 } 436 437 public List<Student> getStudents() { 438 return iStudents; 439 } 440 441 public double size() { 442 return iSize; 443 } 444 445 public double size(Student student) { 446 return iSize + getStudentWeight(student); 447 } 448 449 @Override 450 public String toString() { 451 return "{" + size() + "-" + getDistance() + "/" + getStudents() + "}"; 452 } 453 454 public boolean canEnroll(Student student) { 455 if (getLecture() != null) { 456 return student.canEnroll(getLecture()); 457 } else { 458 for (Long subpartId: getConfiguration().getTopSubpartIds()) { 459 boolean canEnrollThisSubpart = false; 460 for (Lecture lecture : getConfiguration().getTopLectures(subpartId)) { 461 if (student.canEnroll(lecture)) { 462 canEnrollThisSubpart = true; 463 break; 464 } 465 } 466 if (!canEnrollThisSubpart) 467 return false; 468 } 469 return true; 470 } 471 } 472 473 public boolean isEnrolled(Student student) { 474 if (getLecture() != null) { 475 return student.getLectures().contains(getLecture()); 476 } else { 477 for (Lecture lect : student.getLectures()) { 478 if (lect.getConfiguration().equals(getConfiguration())) 479 return true; 480 } 481 return false; 482 } 483 484 } 485 } 486 487 public static void initialSectioningCfg(Assignment<Lecture, Placement> assignment, Progress p, Long offeringId, String courseName, Collection<Student> students, 488 List<Configuration> configurations) { 489 if (students == null || students.isEmpty()) 490 return; 491 if (configurations == null || configurations.isEmpty()) 492 return; 493 if (configurations.size() == 1) { 494 Configuration cfg = configurations.get(0); 495 for (Student st : students) { 496 st.addConfiguration(cfg); 497 } 498 for (Long subpartId: cfg.getTopSubpartIds()) { 499 initialSectioning(assignment, p, offeringId, courseName, students, cfg.getTopLectures(subpartId)); 500 } 501 } else { 502 p.trace("sectioning " + students.size() + " students of course " + courseName + " into " 503 + configurations.size() + " configurations"); 504 InitialSectioning sect = new InitialSectioning(p, offeringId, configurations, students); 505 Group[] studentsPerSection = sect.getGroups(); 506 for (int i = 0; i < configurations.size(); i++) { 507 Group group = studentsPerSection[i]; 508 p.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" 509 + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")"); 510 for (Student st : group.getStudents()) { 511 st.addConfiguration(group.getConfiguration()); 512 } 513 for (Long subpartId: group.getConfiguration().getTopSubpartIds()) { 514 initialSectioning(assignment, p, offeringId, courseName, group.getStudents(), group.getConfiguration().getTopLectures(subpartId)); 515 } 516 } 517 } 518 } 519 520 private static String getClassLabel(Lecture lecture) { 521 return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>"; 522 } 523 524 private static void initialSectioning(Assignment<Lecture, Placement> assignment, Progress p, Long offeringId, String parentName, Collection<Student> students, 525 Collection<Lecture> lectures) { 526 if (lectures == null || lectures.isEmpty()) 527 return; 528 if (students == null || students.isEmpty()) 529 return; 530 for (Lecture lecture : lectures) { 531 if (lecture.classLimit(assignment) == 0 && !lecture.isCommitted()) 532 p.warn("Class " + getClassLabel(lecture) + " has zero class limit."); 533 } 534 535 p.trace("sectioning " + students.size() + " students of course " + parentName + " into " + lectures.size() 536 + " sections"); 537 if (lectures.size() == 1) { 538 Lecture lect = lectures.iterator().next(); 539 for (Student st : students) { 540 if (!st.canEnroll(lect)) { 541 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 542 } 543 lect.addStudent(assignment, st); 544 st.addLecture(lect); 545 } 546 if (lect.hasAnyChildren()) { 547 for (Long subpartId: lect.getChildrenSubpartIds()) { 548 List<Lecture> children = lect.getChildren(subpartId); 549 initialSectioning(assignment, p, offeringId, lect.getName(), students, children); 550 } 551 } 552 } else { 553 InitialSectioning sect = new InitialSectioning(p, offeringId, lectures, students); 554 Group[] studentsPerSection = sect.getGroups(); 555 for (int i = 0; i < studentsPerSection.length; i++) { 556 Group group = studentsPerSection[i]; 557 Lecture lect = group.getLecture(); 558 if (group.getStudents().isEmpty()) { 559 p.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit(assignment) + ")"); 560 continue; 561 } 562 p.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() 563 + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit(assignment) + ")"); 564 List<Student> studentsThisSection = group.getStudents(); 565 for (Student st : studentsThisSection) { 566 if (!st.canEnroll(lect)) { 567 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 568 } 569 lect.addStudent(assignment, st); 570 st.addLecture(lect); 571 } 572 if (lect.hasAnyChildren()) { 573 for (Long subpartId: lect.getChildrenSubpartIds()) { 574 List<Lecture> children = lect.getChildren(subpartId); 575 initialSectioning(assignment, p, offeringId, lect.getName(), studentsThisSection, children); 576 } 577 } 578 } 579 } 580 } 581 582}