    001package org.cpsolver.exam.neighbours;
    002
    003import java.util.HashMap;
    004import java.util.HashSet;
    005import java.util.Map;
    006import java.util.Set;
    007
    008import org.cpsolver.exam.criteria.DistributionPenalty;
    009import org.cpsolver.exam.criteria.RoomPenalty;
    010import org.cpsolver.exam.criteria.RoomSizePenalty;
    011import org.cpsolver.exam.model.Exam;
    012import org.cpsolver.exam.model.ExamDistributionConstraint;
    013import org.cpsolver.exam.model.ExamModel;
    014import org.cpsolver.exam.model.ExamPeriodPlacement;
    015import org.cpsolver.exam.model.ExamPlacement;
    016import org.cpsolver.exam.model.ExamRoom;
    017import org.cpsolver.exam.model.ExamRoomPlacement;
    018import org.cpsolver.ifs.assignment.Assignment;
    019import org.cpsolver.ifs.heuristics.NeighbourSelection;
    020import org.cpsolver.ifs.model.LazySwap;
    021import org.cpsolver.ifs.model.Neighbour;
    022import org.cpsolver.ifs.solution.Solution;
    023import org.cpsolver.ifs.solver.Solver;
    024import org.cpsolver.ifs.util.DataProperties;
    025import org.cpsolver.ifs.util.ToolBox;
    026
    027
    028/**
    029 * Try to swap a period between two exams.
    030 * Two examinations are randomly selected. A new placement is generated by swapping periods of the two exams.
    031 * For each exam, the best possible room placement is found. If the two exams are in the same period, it just tries
    032 * to change the room assignments by looking for the best available room placement ignoring the existing room assignments
    033 * of the two exams. If no conflict results from the swap the assignment is returned.
    034 * The following exams of the second exam in the pair are tried for an exam swap otherwise.
    035 * <br><br>
    036 *
    037 * @author  Tomáš Müller
    038 * @version ExamTT 1.3 (Examination Timetabling)<br>
    039 *          Copyright (C) 2013 - 2014 Tomáš Müller<br>
    040 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    041 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    042 * <br>
    043 *          This library is free software; you can redistribute it and/or modify
    044 *          it under the terms of the GNU Lesser General Public License as
    045 *          published by the Free Software Foundation; either version 3 of the
    046 *          License, or (at your option) any later version. <br>
    047 * <br>
    048 *          This library is distributed in the hope that it will be useful, but
    049 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    050 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    051 *          Lesser General Public License for more details. <br>
    052 * <br>
    053 *          You should have received a copy of the GNU Lesser General Public
    054 *          License along with this library; if not see
    055 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    056 */
    057public class ExamPeriodSwapMove implements NeighbourSelection<Exam,ExamPlacement> {
    058    private boolean iCheckStudentConflicts = false;
    059    private boolean iCheckDistributionConstraints = true;
    060
    061    /**
    062     * Constructor
    063     * @param properties problem properties
    064     */
    065    public ExamPeriodSwapMove(DataProperties properties) {
    066        iCheckStudentConflicts = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckStudentConflicts", iCheckStudentConflicts);
    067        iCheckDistributionConstraints = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckDistributionConstraints", iCheckDistributionConstraints);
    068    }
    069
    070    /**
    071     * Initialization
    072     */
    073    @Override
    074    public void init(Solver<Exam,ExamPlacement> solver) {}
    075
    076    /**
    077     * Select an exam randomly,
    078     * select an available period randomly (if it is not assigned),
    079     * use rooms if possible, select rooms using {@link Exam#findBestAvailableRooms(Assignment, ExamPeriodPlacement)} if not (exam is unassigned, a room is not available or used).
    080     */
    081    @Override
    082    public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution) {
    083        ExamModel model = (ExamModel)solution.getModel();
    084        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
    085        Exam x1 = ToolBox.random(model.variables());
    086        ExamPlacement v1 = assignment.getValue(x1);
    087        if (v1 == null) return null;
    088        int x = ToolBox.random(model.variables().size());
    089        for (int v = 0; v < model.variables().size(); v++) {
    090            Exam x2 = model.variables().get((v + x) % (model.variables().size()));
    091            ExamPlacement v2 = assignment.getValue(x2);
    092            if (x1.equals(x2) || v2 == null) continue;
    093            ExamPeriodPlacement p1 = x1.getPeriodPlacement(v2.getPeriod());
    094            ExamPeriodPlacement p2 = x2.getPeriodPlacement(v1.getPeriod());
    095            if (p1 == null || p2 == null || p1.equals(p2)) continue;
    096            if (iCheckStudentConflicts && (x1.countStudentConflicts(assignment, p1) > 0 || x2.countStudentConflicts(assignment, p2) > 0)) continue;
    097            if (iCheckDistributionConstraints) {
    098                Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
    099                placements.put(x1, new ExamPlacement(x1, p1, new HashSet<ExamRoomPlacement>()));
    100                placements.put(x2, new ExamPlacement(x2, p2, new HashSet<ExamRoomPlacement>()));
    101                if (!checkDistributionConstraints(assignment, x1, p1, placements) || !checkDistributionConstraints(assignment, x2, p2, placements)) continue;
    102            }
    103            Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>();
    104            conflicts.add(v1); conflicts.add(v2);
    105            Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
    106            Set<ExamRoomPlacement> r1 = findBestAvailableRooms(assignment, x1, p1, conflicts, placements);
    107            if (r1 == null) continue;
    108            placements.put(x1, new ExamPlacement(x1, p1, r1));
    109            Set<ExamRoomPlacement> r2 = findBestAvailableRooms(assignment, x2, p2, conflicts, placements);
    110            if (r2 == null) continue;
    111            return new LazySwap<Exam, ExamPlacement>(new ExamPlacement(x1, p1, r1), new ExamPlacement(x2, p2, r2));
    112        }
    113        return null;
    114    }
    115
    116    public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Map<Exam, ExamPlacement> placements) {
    117        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
    118            if (!dc.isHard())
    119                continue;
    120            boolean before = true;
    121            for (Exam other : dc.variables()) {
    122                if (other.equals(this)) {
    123                    before = false;
    124                    continue;
    125                }
    126                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
    127                if (placement == null) continue;
    128                if (before) {
    129                    if (!dc.getDistributionType().isSatisfied(placement.getPeriod(), period.getPeriod()))
    130                        return false;
    131                } else {
    132                    if (!dc.getDistributionType().isSatisfied(period.getPeriod(), placement.getPeriod()))
    133                        return false;
    134                }
    135            }
    136        }
    137        return true;
    138    }
    139
    140    public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
    141        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
    142            if (!dc.isHard())
    143                continue;
    144            for (Exam other : dc.variables()) {
    145                if (other.equals(exam)) continue;
    146                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
    147                if (placement == null || conflictsToIgnore.contains(placement)) continue;
    148                if (!dc.getDistributionType().isSatisfied(placement, room))
    149                    return false;
    150            }
    151        }
    152        return true;
    153    }
    154
    155    public int getDistributionConstraintPenalty(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room,  Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
    156        int penalty = 0;
    157        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
    158            if (dc.isHard()) continue;
    159            for (Exam other : dc.variables()) {
    160                if (other.equals(this)) continue;
    161                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
    162                if (placement == null || conflictsToIgnore.contains(placement)) continue;
    163                if (!dc.getDistributionType().isSatisfied(placement, room))
    164                    penalty += dc.getWeight();
    165            }
    166        }
    167        return penalty;
    168    }
    169
    170    public Set<ExamRoomPlacement> findBestAvailableRooms(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
    171        if (exam.getMaxRooms() == 0)
    172            return new HashSet<ExamRoomPlacement>();
    173        double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
    174        double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
    175        double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight();
    176        loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
    177            HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
    178            int size = 0;
    179            while (rooms.size() < nrRooms && size < exam.getSize()) {
    180                int minSize = (exam.getSize() - size) / (nrRooms - rooms.size());
    181                ExamRoomPlacement best = null;
    182                double bestWeight = 0;
    183                int bestSize = 0;
    184                for (ExamRoomPlacement room : exam.getRoomPlacements()) {
    185                    if (!room.isAvailable(period.getPeriod())) continue;
    186                    if (rooms.contains(room)) continue;
    187                    if (!ExamRoom.checkParents(rooms, room)) continue;
    188
    189                    Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>(conflictsToIgnore);
    190                    room.getRoom().computeConflicts(assignment, exam, period.getPeriod(), conflicts);
    191                    if (conflicts.size() > conflictsToIgnore.size()) continue;
    192
    193                    if (iCheckDistributionConstraints && !checkDistributionConstraints(assignment, exam, room, conflictsToIgnore, placements)) continue;
    194                    int s = room.getSize(exam.hasAltSeating());
    195                    if (s < minSize) break;
    196                    int p = room.getPenalty(period.getPeriod());
    197                    double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(assignment, exam, room, conflictsToIgnore, placements);
    198                    double d = 0;
    199                    if (!rooms.isEmpty()) {
    200                        for (ExamRoomPlacement r : rooms) {
    201                            d += r.getDistanceInMeters(room);
    202                        }
    203                        w += d / rooms.size();
    204                    }
    205                    if (best == null || bestWeight > w) {
    206                        best = room;
    207                        bestSize = s;
    208                        bestWeight = w;
    209                    }
    210                }
    211                if (best == null)
    212                    continue loop;
    213                rooms.add(best);
    214                size += bestSize;
    215            }
    216            if (size >= exam.getSize())
    217                return rooms;
    218        }
    219        return null;
    220    }
    221}