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