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