    001package net.sf.cpsolver.exam.split;
    002
    003import java.util.HashSet;
    004import java.util.List;
    005import java.util.Set;
    006
    007import net.sf.cpsolver.exam.criteria.RoomPenalty;
    008import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
    009import net.sf.cpsolver.exam.model.Exam;
    010import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
    011import net.sf.cpsolver.exam.model.ExamPlacement;
    012import net.sf.cpsolver.exam.model.ExamRoomPlacement;
    013import net.sf.cpsolver.exam.model.ExamStudent;
    014import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    015import net.sf.cpsolver.ifs.model.Neighbour;
    016import net.sf.cpsolver.ifs.solution.Solution;
    017import net.sf.cpsolver.ifs.solver.Solver;
    018import net.sf.cpsolver.ifs.util.DataProperties;
    019import net.sf.cpsolver.ifs.util.ToolBox;
    020
    021import org.apache.log4j.Logger;
    022
    023/**
    024 * Experimental neighbor selection that allows an exam to be split
    025 * into two if it decreases the number of student conflicts.
    026 * <br><br>
    027 * An examination split is improving (and is considered) if the weighted
    028 * number of student conflicts that will be removed by the split is bigger
    029 * than the weight of the splitter criterion {@link ExamSplitter#getWeight()}.
    030 *
    031 * <br>
    032 *
    033 * @version ExamTT 1.2 (Examination Timetabling)<br>
    034 *          Copyright (C) 2008 - 2013 Tomáš Müller<br>
    035 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    036 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    037 * <br>
    038 *          This library is free software; you can redistribute it and/or modify
    039 *          it under the terms of the GNU Lesser General Public License as
    040 *          published by the Free Software Foundation; either version 3 of the
    041 *          License, or (at your option) any later version. <br>
    042 * <br>
    043 *          This library is distributed in the hope that it will be useful, but
    044 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    045 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    046 *          Lesser General Public License for more details. <br>
    047 * <br>
    048 *          You should have received a copy of the GNU Lesser General Public
    049 *          License along with this library; if not see
    050 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    051 */
    052public class ExamSplitMoves implements NeighbourSelection<Exam, ExamPlacement> {
    053    private static Logger sLog = Logger.getLogger(ExamSplitMoves.class);
    054    private ExamSplitter iSplitter = null;
    055
    056    /** Constructor */
    057    public ExamSplitMoves(DataProperties properties) {}
    058
    059    /** Initialization */
    060    @Override
    061    public void init(Solver<Exam, ExamPlacement> solver) {
    062        iSplitter = (ExamSplitter)solver.currentSolution().getModel().getCriterion(ExamSplitter.class);
    063        if (iSplitter == null) throw new RuntimeException("ExamSplitter criterion needs to be used as well.");
    064    }
    065
    066    /**
    067     * Find best available rooms for a new exam (that is to be split from the given one),
    068     * if is is assigned into the given examination period.
    069     *
    070     * @param exam an exam to be split
    071     * @param period a period to be assigned to the new exam
    072     * @param examSize size of the new exam (i.e., the number of students that will be moved from the given exam to the new one)
    073     * @return best room placement for the given exam and period
    074     */
    075    public Set<ExamRoomPlacement> findBestAvailableRooms(Exam exam, ExamPeriodPlacement period, int examSize) {
    076        if (exam.getMaxRooms() == 0) return new HashSet<ExamRoomPlacement>();
    077        double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
    078        double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
    079        loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
    080            HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
    081            int size = 0;
    082            while (rooms.size() < nrRooms && size < examSize) {
    083                int minSize = (examSize - size) / (nrRooms - rooms.size());
    084                ExamRoomPlacement best = null;
    085                double bestWeight = 0;
    086                int bestSize = 0;
    087                for (ExamRoomPlacement room : exam.getRoomPlacements()) {
    088                    if (!room.isAvailable(period.getPeriod()))
    089                        continue;
    090                    if (!room.getRoom().getPlacements(period.getPeriod()).isEmpty())
    091                        continue;
    092                    if (rooms.contains(room))
    093                        continue;
    094                    int s = room.getSize(exam.hasAltSeating());
    095                    if (s < minSize)
    096                        break;
    097                    int p = room.getPenalty(period.getPeriod());
    098                    double w = pw * p + sw * (s - minSize);
    099                    double d = 0;
    100                    if (!rooms.isEmpty()) {
    101                        for (ExamRoomPlacement r : rooms) {
    102                            d += r.getDistanceInMeters(room);
    103                        }
    104                        w += d / rooms.size();
    105                    }
    106                    if (best == null || bestWeight > w) {
    107                        best = room;
    108                        bestSize = s;
    109                        bestWeight = w;
    110                    }
    111                }
    112                if (best == null)
    113                    continue loop;
    114                rooms.add(best);
    115                size += bestSize;
    116            }
    117            if (size >= examSize)
    118                return rooms;
    119        }
    120        return null;
    121    }
    122
    123    /**
    124     * Find a best split for the given exam. Only improving neighbors are considered.
    125     * @param exam an exam to be split
    126     * @return best neighbor that will do the split
    127     */
    128    public ExamSplitNeighbour bestSplit(Exam exam) {
    129        ExamSplitNeighbour split = null;
    130        ExamPlacement placement = exam.getAssignment();
    131        int px = ToolBox.random(exam.getPeriodPlacements().size());
    132        for (int p = 0; p < exam.getPeriodPlacements().size(); p++) { // Iterate over possible periods
    133            ExamPeriodPlacement period = exam.getPeriodPlacements().get((p + px) % exam.getPeriodPlacements().size());
    134            if (placement != null && placement.getPeriod().equals(period)) continue;
    135            // Try to create a neighbor
    136            ExamSplitNeighbour s = new ExamSplitNeighbour(exam, new ExamPlacement(exam, period, null));
    137            if (split == null || s.value() < split.value()) {
    138                // If improving, try to find available rooms
    139                Set<ExamRoomPlacement> rooms = findBestAvailableRooms(exam, period, s.nrStudents());
    140                if (rooms != null) {
    141                    // Remember as best split
    142                    s.placement().getRoomPlacements().addAll(rooms);
    143                    split = s;
    144                }
    145            }
    146        }
    147        return split;
    148    }
    149
    150    /**
    151     * Select a split (split an exam into two), a merge (merge two split exams back together) or
    152     * shuffle operation (move students between two exams that has been split before).
    153     */
    154    @Override
    155    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
    156        // Randomly select an exam
    157        Exam exam = ToolBox.random(solution.getModel().assignedVariables());
    158
    159        // Parent exam (its either the exam itself, or its parent if it has been already split)
    160        Exam parent = iSplitter.parent(exam);
    161        // Its children (if already split)
    162        List<Exam> children = iSplitter.children(parent);
    163
    164        // Already split -> try shuffle
    165        if (children != null && !children.isEmpty()) {
    166            ExamShuffleNeighbour shuffle = new ExamShuffleNeighbour(exam);
    167            if (shuffle.value() < 0.0) return shuffle;
    168        }
    169
    170        // Can split -> try a split
    171        if (iSplitter.canSplit(exam)) {
    172            ExamSplitNeighbour split = bestSplit(exam);
    173            if (split != null && split.value() < 0.0) return split;
    174        }
    175
    176        // Can merge -> try to merge
    177        if (iSplitter.canMerge(exam)) {
    178            ExamMergeNeighbour merge = new ExamMergeNeighbour(exam);
    179            if (merge.value() < 0.0) return merge;
    180        }
    181
    182        return null;
    183    }
    184
    185    /**
    186     * Split an exam into two
    187     */
    188    protected class ExamSplitNeighbour extends Neighbour<Exam, ExamPlacement> {
    189        private Exam iExam;
    190        private ExamPlacement iPlacement;
    191        private double iValue = 0.0;
    192        private int iNrStudents = 0;
    193
    194        /**
    195         * Split an exam into two, assign the new exam into the given placement.
    196         * @param exam an exam to be split
    197         * @param placement a placement to be assigned to the new exam
    198         */
    199        public ExamSplitNeighbour(Exam exam, ExamPlacement placement) {
    200            iExam = exam;
    201            iPlacement = placement;
    202
    203            // Parent exam (its either the exam itself, or its parent if it has been already split)
    204            Exam parent = iSplitter.parent(exam);
    205            // Its children (if already split)
    206            List<Exam> children = iSplitter.children(parent);
    207
    208            // Compute improvement
    209            // Consider moving all students of the parent exam to the new placement
    210            for (ExamStudent student: parent.getStudents()) {
    211                double delta = iSplitter.delta(student, parent.getAssignment(), placement);
    212                if (delta < 0.0) {
    213                    iValue += delta;
    214                    iNrStudents ++;
    215                }
    216            }
    217            // If there already are other children, consider moving students of these children to the
    218            // new placement as well
    219            if (children != null)
    220                for (Exam child: children)
    221                    for (ExamStudent student: child.getStudents()) {
    222                        double delta = iSplitter.delta(student, child.getAssignment(), placement);
    223                        if (delta < 0.0) {
    224                            iValue += delta;
    225                            iNrStudents ++;
    226                        }
    227                    }
    228
    229            // Increase the weight by the splitter criterion weight
    230            iValue += iSplitter.getWeight();
    231        }
    232
    233        /**
    234         * Perform the split.
    235         */
    236        @Override
    237        public void assign(long iteration) {
    238            sLog.info("Splitting " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", " + iPlacement.getName() + ", value: " + iValue + ")");
    239            iSplitter.split(iExam, iteration, iPlacement);
    240        }
    241
    242        /**
    243         * Value of the split. This is the weight of the splitter criterion minus the weighted sum of
    244         * all student conflicts that will be removed by the split.
    245         */
    246        @Override
    247        public double value() {
    248            return iValue;
    249        }
    250
    251        /**
    252         * Number of students that will be moved into the new exam.
    253         */
    254        public int nrStudents() {
    255            return iNrStudents;
    256        }
    257
    258        /**
    259         * Exam to be split.
    260         */
    261        public Exam exam() {
    262            return iExam;
    263        }
    264
    265        /**
    266         * Placement of the new exam.
    267         */
    268        public ExamPlacement placement() {
    269            return iPlacement;
    270        }
    271    }
    272
    273    /**
    274     * Merge two exams that have been split before back into one. This moves
    275     * the students from the child exam back to its parent and removes the
    276     * child exam from the problem.
    277     */
    278    protected class ExamMergeNeighbour extends Neighbour<Exam, ExamPlacement> {
    279        private Exam iExam;
    280        private double iValue = 0.0;
    281
    282        /**
    283         * Child exam to be removed.
    284         */
    285        public ExamMergeNeighbour(Exam exam) {
    286            iExam = exam;
    287
    288            // Parent exam (its either the exam itself, or its parent if it has been already split)
    289            Exam parent = iSplitter.parent(exam);
    290            // Its children (if already split)
    291            List<Exam> children = iSplitter.children(parent);
    292
    293            // Compute improvement
    294            for (ExamStudent student: exam.getStudents()) {
    295                // Try to move each student either back to the parent exam or to any of the other
    296                // children exams, if there are any
    297                double delta = iSplitter.delta(student, exam.getAssignment(), parent.getAssignment());
    298                for (Exam child: children) {
    299                    if (child.equals(exam)) continue;
    300                    double d = iSplitter.delta(student, exam.getAssignment(), child.getAssignment());
    301                    if (d < delta) delta = d;
    302                }
    303                iValue += delta;
    304            }
    305            // Decrease the weight by the splitter criterion weight
    306            iValue -= iSplitter.getWeight();
    307        }
    308
    309        /**
    310         * Perform the merge.
    311         */
    312        @Override
    313        public void assign(long iteration) {
    314            sLog.info("Mergning " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", value: " + iValue + ")");
    315            iSplitter.merge(iExam, iteration);
    316        }
    317
    318        /**
    319         * Value of the merge. This is the weighted sum of all student conflicts that will be added by the merge,
    320         * minus the weight of the splitter criterion.
    321         */
    322        @Override
    323        public double value() {
    324            return iValue;
    325        }
    326
    327        /**
    328         * Number of students that will be moved back to the parent exam or to some other child (if there are any).
    329         */
    330        public int nrStudents() {
    331            return iExam.getStudents().size();
    332        }
    333
    334        /**
    335         * Exam to be merged.
    336         */
    337        public Exam exam() {
    338            return iExam;
    339        }
    340    }
    341
    342    /**
    343     * Shuffle students between the parent exam and all of its children. Only swaps
    344     * that are decreasing the weighted sum of student conflicts are considered.
    345     */
    346    protected class ExamShuffleNeighbour extends Neighbour<Exam, ExamPlacement> {
    347        private Exam iExam;
    348        private double iValue = 0.0;
    349
    350        /**
    351         * Exam to be shuffled.
    352         */
    353        public ExamShuffleNeighbour(Exam exam) {
    354            iExam = exam;
    355
    356            // Parent exam (its either the exam itself, or its parent if it has been already split)
    357            Exam parent = iSplitter.parent(exam);
    358            // Its children (if already split)
    359            List<Exam> children = iSplitter.children(parent);
    360
    361            // Compute improvement
    362            // Try moving students away from parent
    363            for (ExamStudent student: parent.getStudents()) {
    364                Double delta = null;
    365                for (Exam x: children) {
    366                    double d = iSplitter.delta(student, parent.getAssignment(), x.getAssignment());
    367                    if (delta == null || d < delta) delta = d;
    368                }
    369                if (delta != null && delta < 0) iValue += delta;
    370            }
    371
    372            // Try moving students away from any child
    373            for (Exam child: children) {
    374                for (ExamStudent student: child.getStudents()) {
    375                    double delta = iSplitter.delta(student, child.getAssignment(), parent.getAssignment());
    376                    for (Exam x: children) {
    377                        if (x.equals(child)) continue;
    378                        double d = iSplitter.delta(student, child.getAssignment(), x.getAssignment());
    379                        if (d < delta) delta = d;
    380                    }
    381                    if (delta < 0) iValue += delta;
    382                }
    383            }
    384        }
    385
    386        /**
    387         * Perform the shuffle.
    388         */
    389        @Override
    390        public void assign(long iteration) {
    391            sLog.info("Shuffling " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", value: " + iValue + ")");
    392            iSplitter.shuffle(iExam, iteration);
    393        }
    394
    395        /**
    396         * Value of the shuffle. This is the weighted sum of all student conflicts that will be removed by the shuffle.
    397         */
    398        @Override
    399        public double value() {
    400            return iValue;
    401        }
    402
    403        /**
    404         * Exam to be shuffled.
    405         */
    406        public Exam exam() {
    407            return iExam;
    408        }
    409    }
    410}