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