    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 = new Double(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}