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 * @version ExamTT 1.3 (Examination Timetabling)<br>
038 *          Copyright (C) 2013 - 2014 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(Assignment, 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        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
084        Exam x1 = ToolBox.random(model.variables());
085        ExamPlacement v1 = assignment.getValue(x1);
086        if (v1 == null) return null;
087        int x = ToolBox.random(model.variables().size());
088        for (int v = 0; v < model.variables().size(); v++) {
089            Exam x2 = model.variables().get((v + x) % (model.variables().size()));
090            ExamPlacement v2 = assignment.getValue(x2);
091            if (x1.equals(x2) || v2 == null) continue;
092            ExamPeriodPlacement p1 = x1.getPeriodPlacement(v2.getPeriod());
093            ExamPeriodPlacement p2 = x2.getPeriodPlacement(v1.getPeriod());
094            if (p1 == null || p2 == null || p1.equals(p2)) continue;
095            if (iCheckStudentConflicts && (x1.countStudentConflicts(assignment, p1) > 0 || x2.countStudentConflicts(assignment, p2) > 0)) continue;
096            if (iCheckDistributionConstraints) {
097                Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
098                placements.put(x1, new ExamPlacement(x1, p1, new HashSet<ExamRoomPlacement>()));
099                placements.put(x2, new ExamPlacement(x2, p2, new HashSet<ExamRoomPlacement>()));
100                if (!checkDistributionConstraints(assignment, x1, p1, placements) || !checkDistributionConstraints(assignment, x2, p2, placements)) continue;
101            }
102            Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>();
103            conflicts.add(v1); conflicts.add(v2);
104            Map<Exam, ExamPlacement> placements = new HashMap<Exam, ExamPlacement>();
105            Set<ExamRoomPlacement> r1 = findBestAvailableRooms(assignment, x1, p1, conflicts, placements);
106            if (r1 == null) continue;
107            placements.put(x1, new ExamPlacement(x1, p1, r1));
108            Set<ExamRoomPlacement> r2 = findBestAvailableRooms(assignment, x2, p2, conflicts, placements);
109            if (r2 == null) continue;
110            return new LazySwap<Exam, ExamPlacement>(new ExamPlacement(x1, p1, r1), new ExamPlacement(x2, p2, r2));
111        }
112        return null;
113    }
114    
115    public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Map<Exam, ExamPlacement> placements) {
116        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
117            if (!dc.isHard())
118                continue;
119            boolean before = true;
120            for (Exam other : dc.variables()) {
121                if (other.equals(this)) {
122                    before = false;
123                    continue;
124                }
125                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
126                if (placement == null) continue;
127                if (before) {
128                    if (!dc.getDistributionType().isSatisfied(placement.getPeriod(), period.getPeriod()))
129                        return false;
130                } else {
131                    if (!dc.getDistributionType().isSatisfied(period.getPeriod(), placement.getPeriod()))
132                        return false;
133                }
134            }
135        }
136        return true;
137    }
138    
139    public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
140        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
141            if (!dc.isHard())
142                continue;
143            for (Exam other : dc.variables()) {
144                if (other.equals(exam)) continue;
145                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
146                if (placement == null || conflictsToIgnore.contains(placement)) continue;
147                if (!dc.getDistributionType().isSatisfied(placement, room))
148                    return false;
149            }
150        }
151        return true;
152    }
153    
154    public int getDistributionConstraintPenalty(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room,  Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
155        int penalty = 0;
156        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
157            if (dc.isHard()) continue;
158            for (Exam other : dc.variables()) {
159                if (other.equals(this)) continue;
160                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
161                if (placement == null || conflictsToIgnore.contains(placement)) continue;
162                if (!dc.getDistributionType().isSatisfied(placement, room))
163                    penalty += dc.getWeight();
164            }
165        }
166        return penalty;
167    }
168    
169    public Set<ExamRoomPlacement> findBestAvailableRooms(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
170        if (exam.getMaxRooms() == 0)
171            return new HashSet<ExamRoomPlacement>();
172        double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
173        double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
174        double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight();
175        loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
176            HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
177            int size = 0;
178            while (rooms.size() < nrRooms && size < exam.getSize()) {
179                int minSize = (exam.getSize() - size) / (nrRooms - rooms.size());
180                ExamRoomPlacement best = null;
181                double bestWeight = 0;
182                int bestSize = 0;
183                for (ExamRoomPlacement room : exam.getRoomPlacements()) {
184                    if (!room.isAvailable(period.getPeriod())) continue;
185                    if (rooms.contains(room)) continue;
186                    if (!ExamRoom.checkParents(rooms, room)) continue;
187                    
188                    Set<ExamPlacement> conflicts = new HashSet<ExamPlacement>(conflictsToIgnore);
189                    room.getRoom().computeConflicts(assignment, exam, period.getPeriod(), conflicts);
190                    if (conflicts.size() > conflictsToIgnore.size()) continue;
191
192                    if (iCheckDistributionConstraints && !checkDistributionConstraints(assignment, exam, room, conflictsToIgnore, placements)) continue;
193                    int s = room.getSize(exam.hasAltSeating());
194                    if (s < minSize) break;
195                    int p = room.getPenalty(period.getPeriod());
196                    double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(assignment, exam, room, conflictsToIgnore, placements);
197                    double d = 0;
198                    if (!rooms.isEmpty()) {
199                        for (ExamRoomPlacement r : rooms) {
200                            d += r.getDistanceInMeters(room);
201                        }
202                        w += d / rooms.size();
203                    }
204                    if (best == null || bestWeight > w) {
205                        best = room;
206                        bestSize = s;
207                        bestWeight = w;
208                    }
209                }
210                if (best == null)
211                    continue loop;
212                rooms.add(best);
213                size += bestSize;
214            }
215            if (size >= exam.getSize())
216                return rooms;
217        }
218        return null;
219    }
220}