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