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}