    001package net.sf.cpsolver.exam.neighbours;
    002
    003import java.util.ArrayList;
    004import java.util.HashMap;
    005import java.util.HashSet;
    006import java.util.List;
    007import java.util.Map;
    008import java.util.Set;
    009
    010import net.sf.cpsolver.exam.criteria.DistributionPenalty;
    011import net.sf.cpsolver.exam.criteria.RoomPenalty;
    012import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
    013import net.sf.cpsolver.exam.model.Exam;
    014import net.sf.cpsolver.exam.model.ExamDistributionConstraint;
    015import net.sf.cpsolver.exam.model.ExamModel;
    016import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
    017import net.sf.cpsolver.exam.model.ExamPlacement;
    018import net.sf.cpsolver.exam.model.ExamRoomPlacement;
    019import net.sf.cpsolver.exam.model.ExamRoomSharing;
    020import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    021import net.sf.cpsolver.ifs.model.LazySwap;
    022import net.sf.cpsolver.ifs.model.Neighbour;
    023import net.sf.cpsolver.ifs.solution.Solution;
    024import net.sf.cpsolver.ifs.solver.Solver;
    025import net.sf.cpsolver.ifs.util.DataProperties;
    026import net.sf.cpsolver.ifs.util.ToolBox;
    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 * @version ExamTT 1.2 (Examination Timetabling)<br>
    038 *          Copyright (C) 2013 Tomáš Müller<br>
    039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    041 * <br>
    042 *          This library is free software; you can redistribute it and/or modify
    043 *          it under the terms of the GNU Lesser General Public License as
    044 *          published by the Free Software Foundation; either version 3 of the
    045 *          License, or (at your option) any later version. <br>
    046 * <br>
    047 *          This library is distributed in the hope that it will be useful, but
    048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    050 *          Lesser General Public License for more details. <br>
    051 * <br>
    052 *          You should have received a copy of the GNU Lesser General Public
    053 *          License along with this library; if not see
    054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    055 */
    056public class ExamPeriodSwapMove implements NeighbourSelection<Exam,ExamPlacement> {
    057    private boolean iCheckStudentConflicts = false;
    058    private boolean iCheckDistributionConstraints = true;
    059
    060    /**
    061     * Constructor
    062     * @param properties problem properties
    063     */
    064    public ExamPeriodSwapMove(DataProperties properties) {
    065        iCheckStudentConflicts = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckStudentConflicts", iCheckStudentConflicts);
    066        iCheckDistributionConstraints = properties.getPropertyBoolean("ExamPeriodSwapMove.CheckDistributionConstraints", iCheckDistributionConstraints);
    067    }
    068
    069    /**
    070     * Initialization
    071     */
    072    @Override
    073    public void init(Solver<Exam,ExamPlacement> solver) {}
    074
    075    /**
    076     * Select an exam randomly,
    077     * select an available period randomly (if it is not assigned),
    078     * use rooms if possible, select rooms using {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)} if not (exam is unassigned, a room is not available or used).
    079     */
    080    @Override
    081    public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution) {
    082        ExamModel model = (ExamModel)solution.getModel();
    083        Exam x1 = ToolBox.random(model.variables());
    084        if (x1.getAssignment() == null) return null;
    085        int x = ToolBox.random(model.variables().size());
    086        for (int v = 0; v < model.variables().size(); v++) {
    087            Exam x2 = model.variables().get((v + x) % (model.variables().size()));
    088            if (x1.equals(x2) || x2.getAssignment() == null) continue;
    089            ExamPeriodPlacement p1 = x1.getPeriodPlacement(x2.getAssignment().getPeriod());
    090            ExamPeriodPlacement p2 = x2.getPeriodPlacement(x1.getAssignment().getPeriod());
    091            if (p1 == null || p2 == null) continue;
    092            if (iCheckStudentConflicts && (x1.countStudentConflicts(p1) > 0 || x2.countStudentConflicts(p2) > 0)) continue;
    093            if (iCheckDistributionConstraints) {
    094                Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
    095                placements.put(x1, new ExamPlacement(x1, p1, new HashSet<ExamRoomPlacement>()));
    096                placements.put(x2, new ExamPlacement(x2, p2, new HashSet<ExamRoomPlacement>()));
    097                if (!checkDistributionConstraints(x1, p1, placements) || !checkDistributionConstraints(x2, p2, placements)) continue;
    098            }
    099            Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>();
    100            conflicts.add(x1.getAssignment()); conflicts.add(x2.getAssignment());
    101            Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
    102            Set<ExamRoomPlacement> r1 = findBestAvailableRooms(x1, p1, conflicts, placements);
    103            if (r1 == null) continue;
    104            placements.put(x1, new ExamPlacement(x1, p1, r1));
    105            Set<ExamRoomPlacement> r2 = findBestAvailableRooms(x2, p2, conflicts, placements);
    106            if (r2 == null) continue;
    107            return new LazySwap<Exam, ExamPlacement>(new ExamPlacement(x1, p1, r1), new ExamPlacement(x2, p2, r2));
    108        }
    109        return null;
    110    }
    111
    112    public boolean checkDistributionConstraints(Exam exam, ExamPeriodPlacement period, Map<Exam, ExamPlacement> placements) {
    113        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
    114            if (!dc.isHard())
    115                continue;
    116            boolean before = true;
    117            for (Exam other : dc.variables()) {
    118                if (other.equals(this)) {
    119                    before = false;
    120                    continue;
    121                }
    122                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment());
    123                if (placement == null) continue;
    124                switch (dc.getType()) {
    125                    case ExamDistributionConstraint.sDistSamePeriod:
    126                        if (period.getIndex() != placement.getPeriod().getIndex())
    127                            return false;
    128                        break;
    129                    case ExamDistributionConstraint.sDistDifferentPeriod:
    130                        if (period.getIndex() == placement.getPeriod().getIndex())
    131                            return false;
    132                        break;
    133                    case ExamDistributionConstraint.sDistPrecedence:
    134                        if (before) {
    135                            if (period.getIndex() <= placement.getPeriod().getIndex())
    136                                return false;
    137                        } else {
    138                            if (period.getIndex() >= placement.getPeriod().getIndex())
    139                                return false;
    140                        }
    141                        break;
    142                    case ExamDistributionConstraint.sDistPrecedenceRev:
    143                        if (before) {
    144                            if (period.getIndex() >= placement.getPeriod().getIndex())
    145                                return false;
    146                        } else {
    147                            if (period.getIndex() <= placement.getPeriod().getIndex())
    148                                return false;
    149                        }
    150                        break;
    151                }
    152            }
    153        }
    154        return true;
    155    }
    156
    157    public boolean checkDistributionConstraints(Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
    158        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
    159            if (!dc.isHard())
    160                continue;
    161            for (Exam other : dc.variables()) {
    162                if (other.equals(exam)) continue;
    163                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment());
    164                if (placement == null || conflictsToIgnore.contains(placement)) continue;
    165                switch (dc.getType()) {
    166                    case ExamDistributionConstraint.sDistSameRoom:
    167                        if (!placement.getRoomPlacements().contains(room))
    168                            return false;
    169                        break;
    170                    case ExamDistributionConstraint.sDistDifferentRoom:
    171                        if (placement.getRoomPlacements().contains(room))
    172                            return false;
    173                        break;
    174                }
    175            }
    176        }
    177        return true;
    178    }
    179
    180    public int getDistributionConstraintPenalty(Exam exam, ExamRoomPlacement room,  Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
    181        int penalty = 0;
    182        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
    183            if (dc.isHard()) continue;
    184            for (Exam other : dc.variables()) {
    185                if (other.equals(this)) continue;
    186                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : other.getAssignment());
    187                if (placement == null || conflictsToIgnore.contains(placement)) continue;
    188                switch (dc.getType()) {
    189                    case ExamDistributionConstraint.sDistSameRoom:
    190                        if (!placement.getRoomPlacements().contains(room))
    191                            penalty += dc.getWeight();
    192                        break;
    193                    case ExamDistributionConstraint.sDistDifferentRoom:
    194                        if (placement.getRoomPlacements().contains(room))
    195                            penalty += dc.getWeight();
    196                        break;
    197                }
    198            }
    199        }
    200        return penalty;
    201    }
    202
    203    public Set<ExamRoomPlacement> findBestAvailableRooms(Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
    204        if (exam.getMaxRooms() == 0)
    205            return new HashSet<ExamRoomPlacement>();
    206        double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
    207        double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
    208        double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight();
    209        ExamRoomSharing sharing = ((ExamModel)exam.getModel()).getRoomSharing();
    210        loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
    211            HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
    212            int size = 0;
    213            while (rooms.size() < nrRooms && size < exam.getSize()) {
    214                int minSize = (exam.getSize() - size) / (nrRooms - rooms.size());
    215                ExamRoomPlacement best = null;
    216                double bestWeight = 0;
    217                int bestSize = 0;
    218                for (ExamRoomPlacement room : exam.getRoomPlacements()) {
    219                    if (!room.isAvailable(period.getPeriod())) continue;
    220                    if (rooms.contains(room)) continue;
    221
    222                    List<ExamPlacement> overlaps = new ArrayList<ExamPlacement>();
    223                    for (ExamPlacement overlap: room.getRoom().getPlacements(period.getPeriod()))
    224                        if (!conflictsToIgnore.contains(overlap)) overlaps.add(overlap);
    225                    for (ExamPlacement other: placements.values())
    226                        if (other.getPeriod().equals(period.getPeriod()))
    227                            for (ExamRoomPlacement r: other.getRoomPlacements())
    228                                if (r.getRoom().equals(room.getRoom())) {
    229                                    overlaps.add(other);
    230                                    continue;
    231                                }
    232
    233                    if (nrRooms == 1 && sharing != null) {
    234                        if (sharing.inConflict(exam, overlaps, room.getRoom()))
    235                            continue;
    236                    } else {
    237                        if (!overlaps.isEmpty())
    238                            continue;
    239                    }
    240                    if (iCheckDistributionConstraints && !checkDistributionConstraints(exam, room, conflictsToIgnore, placements)) continue;
    241                    int s = room.getSize(exam.hasAltSeating());
    242                    if (s < minSize) break;
    243                    int p = room.getPenalty(period.getPeriod());
    244                    double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(exam, room, conflictsToIgnore, placements);
    245                    double d = 0;
    246                    if (!rooms.isEmpty()) {
    247                        for (ExamRoomPlacement r : rooms) {
    248                            d += r.getDistanceInMeters(room);
    249                        }
    250                        w += d / rooms.size();
    251                    }
    252                    if (best == null || bestWeight > w) {
    253                        best = room;
    254                        bestSize = s;
    255                        bestWeight = w;
    256                    }
    257                }
    258                if (best == null)
    259                    continue loop;
    260                rooms.add(best);
    261                size += bestSize;
    262            }
    263            if (size >= exam.getSize())
    264                return rooms;
    265        }
    266        return null;
    267    }
    268}