    001package org.cpsolver.coursett.sectioning;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Comparator;
    006import java.util.HashMap;
    007import java.util.HashSet;
    008import java.util.List;
    009import java.util.Map;
    010import java.util.Set;
    011import java.util.TreeSet;
    012
    013import org.cpsolver.coursett.constraint.JenrlConstraint;
    014import org.cpsolver.coursett.criteria.StudentConflict;
    015import org.cpsolver.coursett.model.Configuration;
    016import org.cpsolver.coursett.model.DefaultStudentSectioning;
    017import org.cpsolver.coursett.model.InitialSectioning.Group;
    018import org.cpsolver.coursett.model.Lecture;
    019import org.cpsolver.coursett.model.Placement;
    020import org.cpsolver.coursett.model.Student;
    021import org.cpsolver.coursett.model.StudentGroup;
    022import org.cpsolver.coursett.model.TimetableModel;
    023import org.cpsolver.coursett.sectioning.SctSectioning.GroupBasedInitialSectioning;
    024import org.cpsolver.ifs.assignment.Assignment;
    025import org.cpsolver.ifs.criteria.Criterion;
    026import org.cpsolver.ifs.model.InfoProvider;
    027import org.cpsolver.ifs.model.Neighbour;
    028import org.cpsolver.ifs.solution.Solution;
    029import org.cpsolver.ifs.termination.TerminationCondition;
    030import org.cpsolver.ifs.util.DataProperties;
    031import org.cpsolver.ifs.util.JProf;
    032
    033/**
    034 * Student sectioning implementation based on local search. A student swap is
    035 * generated in each iteration using Hill Climbing and Great Deluge algorithms.
    036 *
    037 * @version CourseTT 1.3 (University Course Timetabling)<br>
    038 *          Copyright (C) 2017 Tomáš Müller<br>
    039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    041 * <br>
    042 *          This library is free software; you can redistribute it and/or modify
    043 *          it under the terms of the GNU Lesser General Public License as
    044 *          published by the Free Software Foundation; either version 3 of the
    045 *          License, or (at your option) any later version. <br>
    046 * <br>
    047 *          This library is distributed in the hope that it will be useful, but
    048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    050 *          Lesser General Public License for more details. <br>
    051 * <br>
    052 *          You should have received a copy of the GNU Lesser General Public
    053 *          License along with this library; if not see
    054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    055 */
    056public class StudentSwapSectioning extends DefaultStudentSectioning implements InfoProvider<Lecture, Placement> {
    057    List<StudentConflict> iStudentConflictCriteria = null;
    058    private static double sEps = 0.0001;
    059    private double iGroupWeight = 0.1;
    060    private boolean iUseCriteria = true;
    061    private int iMaxIdleResection = 1000;
    062
    063    public StudentSwapSectioning(TimetableModel model) {
    064        super(model);
    065        iUseCriteria = model.getProperties().getPropertyBoolean("StudentSwaps.UseCriteria", true);
    066        iGroupWeight = model.getProperties().getPropertyDouble("StudentSwaps.GroupWeight", 10.0);
    067        iMaxIdleResection = model.getProperties().getPropertyInt("StudentSwaps.MaxIdleResection", 1000);
    068    }
    069
    070    protected List<StudentConflict> getStudentConflictCriteria() {
    071        if (!iUseCriteria) return null;
    072        if (iStudentConflictCriteria == null && iModel != null) {
    073            iStudentConflictCriteria = new ArrayList<StudentConflict>();
    074            for (Criterion<Lecture, Placement> criterion: iModel.getCriteria())
    075                if (criterion instanceof StudentConflict)
    076                    iStudentConflictCriteria.add((StudentConflict)criterion);
    077        }
    078        return iStudentConflictCriteria;
    079    }
    080
    081    @Override
    082    public boolean hasFinalSectioning() {
    083        return true;
    084    }
    085
    086    /**
    087     * Student conflict weight change of a student swap
    088     */
    089    protected double objective(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) {
    090        if (n instanceof StudentMove)
    091            return ((StudentMove)n).value(getStudentConflictCriteria(), assignment);
    092        return n.value(assignment);
    093    }
    094
    095    /**
    096     * Student group weight change of a student swap
    097     */
    098    protected double group(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) {
    099        if (n instanceof StudentMove)
    100            return ((StudentMove)n).group(getStudentConflictCriteria(), assignment);
    101        return 0.0;
    102    }
    103
    104    /**
    105     * Combined weight change of a student swap
    106     */
    107    protected double value(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) {
    108        if (n instanceof StudentMove)
    109            return ((StudentMove)n).value(getStudentConflictCriteria(), assignment) - iGroupWeight * ((StudentMove)n).group(getStudentConflictCriteria(), assignment);
    110        return n.value(assignment);
    111    }
    112
    113    /**
    114     * Student conflict weight of a solution
    115     */
    116    protected double objective(Solution<Lecture, Placement> solution) {
    117        List<StudentConflict> criteria = getStudentConflictCriteria();
    118
    119        if (criteria == null) {
    120            double value = 0.0;
    121            for (JenrlConstraint constraint: ((TimetableModel)solution.getModel()).getJenrlConstraints()) {
    122                if (constraint.isInConflict(solution.getAssignment())) value += constraint.jenrl();
    123            }
    124            return value;
    125        }
    126
    127        double value = 0.0;
    128        for (StudentConflict criterion: criteria)
    129            value += criterion.getWeightedValue(solution.getAssignment());
    130        return value;
    131    }
    132
    133    /**
    134     * Student group weight of a solution
    135     */
    136    public static double group(TimetableModel model) {
    137        double ret = 0;
    138        for (StudentGroup group: model.getStudentGroups()) {
    139            Map<Long, Match> match = new HashMap<Long, Match>();
    140            Set<Long> offeringIds = new HashSet<Long>();
    141            for (Student student: group.getStudents())
    142                for (Lecture lecture: student.getLectures()) {
    143                    if (lecture.getConfiguration() == null) continue;
    144                    offeringIds.add(lecture.getConfiguration().getOfferingId());
    145                    Match m = match.get(lecture.getSchedulingSubpartId());
    146                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
    147                    m.inc(lecture);
    148                }
    149            double value = 0.0;
    150            for (Match m: match.values())
    151                value += m.value();
    152            ret += value / offeringIds.size();
    153        }
    154        return ret;
    155    }
    156
    157    /**
    158     * Student group percentage of a solution subset
    159     */
    160    public static double gp(TimetableModel model, Collection<Lecture> variables) {
    161        if (model.getStudentGroups().isEmpty()) return 0.0;
    162        double ret = 0; int count = 0;
    163        for (StudentGroup group: model.getStudentGroups()) {
    164            Map<Long, Match> match = new HashMap<Long, Match>();
    165            Set<Long> offeringIds = new HashSet<Long>();
    166            for (Student student: group.getStudents())
    167                for (Lecture lecture: student.getLectures()) {
    168                    if (lecture.getConfiguration() == null) continue;
    169                    if (variables != null && !variables.contains(lecture)) continue;
    170                    offeringIds.add(lecture.getConfiguration().getOfferingId());
    171                    Match m = match.get(lecture.getSchedulingSubpartId());
    172                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
    173                    m.inc(lecture);
    174                }
    175            if (match.isEmpty()) continue;
    176            double value = 0.0;
    177            for (Match m: match.values())
    178                value += m.value();
    179            ret += value / offeringIds.size();
    180            count ++;
    181        }
    182        return 100.0 * ret / count;
    183    }
    184
    185    /**
    186     * Student group percentage of a solution
    187     */
    188    public static double gp(TimetableModel model) {
    189        if (model.getStudentGroups().isEmpty()) return 0.0;
    190        return 100.0 * group(model) / model.getStudentGroups().size();
    191    }
    192
    193    /**
    194     * Student group percentage of a solution
    195     */
    196    public static double gp(Solution<Lecture, Placement> solution) {
    197        return gp((TimetableModel)solution.getModel());
    198    }
    199
    200    /**
    201     * Combined weight of a solution
    202     */
    203    protected double value(Solution<Lecture, Placement> solution) {
    204        return objective(solution) + iGroupWeight * (iModel.getStudentGroups().size() - group(iModel));
    205    }
    206
    207    @Override
    208    public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) {
    209        long it = 0, lastImp = 0;
    210        double t0 = JProf.currentTimeMillis();
    211        DataProperties cfg = ((TimetableModel)solution.getModel()).getProperties();
    212        long maxIdle = cfg.getPropertyInt("StudentSwaps.MaxIdle", 100000);
    213
    214        getProgress().setStatus("Student Sectioning...");
    215        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
    216        getProgress().setPhase("Swapping students [HC]...", 1000);
    217        StudentSwapGenerator g = new StudentSwapGenerator();
    218        while ((it - lastImp) < maxIdle && (termination == null || termination.canContinue(solution))) {
    219            it ++;
    220            if ((it % 1000) == 0) {
    221                long prg = Math.round(1000.0 * (it - lastImp) / maxIdle);
    222                if (getProgress().getProgress() < prg)
    223                    getProgress().setProgress(prg);
    224                if ((it % 10000) == 0)
    225                    getProgress().info("Iter=" + (it / 1000)+"k, Idle=" + sDF2.format((it - lastImp)/1000.0)+"k, Speed=" + sDF2.format(1000.0 * it / (JProf.currentTimeMillis() - t0))+" it/s" +
    226                            ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%");
    227            }
    228            Neighbour<Lecture, Placement> n = g.selectNeighbour(solution);
    229            if (n == null) continue;
    230            double v = value(n, solution.getAssignment());
    231            if (v < -sEps) { lastImp = it; }
    232            if (v <= 0) { n.assign(solution.getAssignment(), it); }
    233        }
    234        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
    235
    236        double f = cfg.getPropertyDouble("StudentSwaps.Deluge.Factor", 0.9999999);
    237        double ub = cfg.getPropertyDouble("StudentSwaps.Deluge.UpperBound", 1.10);
    238        double lb = cfg.getPropertyDouble("StudentSwaps.Deluge.LowerBound", 0.90);
    239        double total = value(solution);
    240        double bound = ub * total;
    241        double best = total;
    242
    243        it = 0; lastImp = 0; t0 = JProf.currentTimeMillis();
    244        getProgress().setPhase("Swapping students [GD]...", 1000);
    245        while (bound > lb * total && total > 0 && (termination == null || termination.canContinue(solution))) {
    246            Neighbour<Lecture, Placement> n = g.selectNeighbour(solution);
    247            if (n != null) {
    248                double value = value(n, solution.getAssignment());
    249                if (value < 0) { lastImp = it; }
    250                if (value <= 0.0 || total + value < bound) {
    251                    n.assign(solution.getAssignment(), it);
    252                    if (total + value < best) {
    253                        best = total + value;
    254                    }
    255                    total += value;
    256                }
    257            }
    258            bound *= f;
    259            it++;
    260            if ((it % 1000) == 0) {
    261                long prg = 1000 - Math.round(1000.0 * (bound - lb * best) / (ub * best - lb * best));
    262                if (getProgress().getProgress() < prg)
    263                    getProgress().setProgress(prg);
    264                if ((it % 10000) == 0) {
    265                    getProgress().info("Iter=" + (it / 1000)+"k, Idle=" + sDF2.format((it - lastImp)/1000.0)+"k, Speed=" + sDF2.format(1000.0 * it / (JProf.currentTimeMillis() - t0))+" it/s" +
    266                            ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%");
    267                    getProgress().info("Bound is " + sDF2.format(bound) + ", " + "best value is " + sDF2.format(best) + " (" + sDF2.format(100.0 * bound / best) + "%), " +
    268                            "current value is " + sDF2.format(total) + " (" + sDF2.format(100.0 * bound / total) + "%)");
    269                }
    270            }
    271        }
    272        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
    273    }
    274
    275    @Override
    276    public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) {
    277        if (lecture.students().isEmpty()) return;
    278        StudentSwapGenerator g = new StudentSwapGenerator();
    279        long nrIdle = 0, it = 0;
    280        while (nrIdle < iMaxIdleResection) {
    281            nrIdle ++; it ++;
    282            Neighbour<Lecture, Placement> n = g.selectNeighbour(assignment, lecture);
    283            if (n == null) continue;
    284            double v = value(n, assignment);
    285            if (v < -sEps) nrIdle = 0;
    286            if (v <= 0.0) n.assign(assignment, it);
    287        }
    288    }
    289
    290    /**
    291     * Matching students within a scheduling subpart (for student group weight computation)
    292     */
    293    private static class Match {
    294        private int iTotal = 0;
    295        private double iFraction = 1.0;
    296        private Map<Long, Integer> iMatch = new HashMap<Long, Integer>();
    297
    298        /**
    299         * Constructor
    300         * @param group student group
    301         * @param offeringId offering id
    302         */
    303        Match(StudentGroup group, Configuration config) {
    304            iTotal = group.countStudents(config.getOfferingId());
    305            iFraction = 1.0 / config.countSubparts();
    306        }
    307
    308        /**
    309         * Increment given lecture
    310         */
    311        void inc(Lecture lecture) {
    312            Integer val = iMatch.get(lecture.getClassId());
    313            iMatch.put(lecture.getClassId(), 1 + (val == null ? 0 : val.intValue()));
    314        }
    315
    316        /**
    317         * Value (an overall probability of two students being in the same lecture)
    318         */
    319        double value() {
    320            if (iTotal <= 1) return iFraction;
    321            double value = 0.0;
    322            for (Integer m: iMatch.values())
    323                if (m > 1)
    324                    value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0));
    325            return iFraction * value;
    326        }
    327
    328        @Override
    329        public String toString() {
    330            return iTotal + "/" + iMatch;
    331        }
    332    }
    333
    334    protected boolean hasStudentGroups(Collection<Student> students) {
    335        for (Student student: students)
    336            if (!student.getGroups().isEmpty()) return true;
    337        return false;
    338    }
    339
    340    @Override
    341    protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) {
    342        if (hasStudentGroups(students)) {
    343            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students);
    344            return sect.getGroups();
    345        } else {
    346            return super.studentsToConfigurations(offeringId, students, configurations);
    347        }
    348    }
    349
    350    @Override
    351    protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) {
    352        if (hasStudentGroups(students)) {
    353            Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() {
    354                @Override
    355                public int compare(Lecture l1, Lecture l2) {
    356                    return l1.getClassId().compareTo(l2.getClassId());
    357                }
    358            });
    359            sortedLectures.addAll(lectures);
    360            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students);
    361            return sect.getGroups();
    362        } else {
    363            return super.studentsToLectures(offeringId, students, lectures);
    364        }
    365    }
    366}