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