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