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