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