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 Tomas Muller<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                }
157            }
158        }
159        return true;
160    }
161    
162    public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
163        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
164            if (!dc.isHard())
165                continue;
166            for (Exam other : dc.variables()) {
167                if (other.equals(exam)) continue;
168                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
169                if (placement == null || conflictsToIgnore.contains(placement)) continue;
170                switch (dc.getType()) {
171                    case ExamDistributionConstraint.sDistSameRoom:
172                        if (!placement.getRoomPlacements().contains(room))
173                            return false;
174                        break;
175                    case ExamDistributionConstraint.sDistDifferentRoom:
176                        if (placement.getRoomPlacements().contains(room))
177                            return false;
178                        break;
179                }
180            }
181        }
182        return true;
183    }
184    
185    public int getDistributionConstraintPenalty(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamRoomPlacement room,  Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
186        int penalty = 0;
187        for (ExamDistributionConstraint dc : exam.getDistributionConstraints()) {
188            if (dc.isHard()) continue;
189            for (Exam other : dc.variables()) {
190                if (other.equals(this)) continue;
191                ExamPlacement placement = (placements.containsKey(other) ? placements.get(other) : assignment.getValue(other));
192                if (placement == null || conflictsToIgnore.contains(placement)) continue;
193                switch (dc.getType()) {
194                    case ExamDistributionConstraint.sDistSameRoom:
195                        if (!placement.getRoomPlacements().contains(room))
196                            penalty += dc.getWeight();
197                        break;
198                    case ExamDistributionConstraint.sDistDifferentRoom:
199                        if (placement.getRoomPlacements().contains(room))
200                            penalty += dc.getWeight();
201                        break;
202                }
203            }
204        }
205        return penalty;
206    }
207    
208    public Set<ExamRoomPlacement> findBestAvailableRooms(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period, Set<ExamPlacement> conflictsToIgnore, Map<Exam, ExamPlacement> placements) {
209        if (exam.getMaxRooms() == 0)
210            return new HashSet<ExamRoomPlacement>();
211        double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
212        double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
213        double cw = exam.getModel().getCriterion(DistributionPenalty.class).getWeight();
214        ExamRoomSharing sharing = ((ExamModel)exam.getModel()).getRoomSharing();
215        loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
216            HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
217            int size = 0;
218            while (rooms.size() < nrRooms && size < exam.getSize()) {
219                int minSize = (exam.getSize() - size) / (nrRooms - rooms.size());
220                ExamRoomPlacement best = null;
221                double bestWeight = 0;
222                int bestSize = 0;
223                for (ExamRoomPlacement room : exam.getRoomPlacements()) {
224                    if (!room.isAvailable(period.getPeriod())) continue;
225                    if (rooms.contains(room)) continue;
226                    
227                    List<ExamPlacement> overlaps = new ArrayList<ExamPlacement>();
228                    for (ExamPlacement overlap: room.getRoom().getPlacements(assignment, period.getPeriod()))
229                        if (!conflictsToIgnore.contains(overlap)) overlaps.add(overlap);
230                    for (ExamPlacement other: placements.values())
231                        if (other.getPeriod().equals(period.getPeriod()))
232                            for (ExamRoomPlacement r: other.getRoomPlacements())
233                                if (r.getRoom().equals(room.getRoom())) {
234                                    overlaps.add(other);
235                                    continue;
236                                }
237                    
238                    if (nrRooms == 1 && sharing != null) {
239                        if (sharing.inConflict(exam, overlaps, room.getRoom()))
240                            continue;
241                    } else {
242                        if (!overlaps.isEmpty())
243                            continue;
244                    }
245                    if (iCheckDistributionConstraints && !checkDistributionConstraints(assignment, exam, room, conflictsToIgnore, placements)) continue;
246                    int s = room.getSize(exam.hasAltSeating());
247                    if (s < minSize) break;
248                    int p = room.getPenalty(period.getPeriod());
249                    double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(assignment, exam, room, conflictsToIgnore, placements);
250                    double d = 0;
251                    if (!rooms.isEmpty()) {
252                        for (ExamRoomPlacement r : rooms) {
253                            d += r.getDistanceInMeters(room);
254                        }
255                        w += d / rooms.size();
256                    }
257                    if (best == null || bestWeight > w) {
258                        best = room;
259                        bestSize = s;
260                        bestWeight = w;
261                    }
262                }
263                if (best == null)
264                    continue loop;
265                rooms.add(best);
266                size += bestSize;
267            }
268            if (size >= exam.getSize())
269                return rooms;
270        }
271        return null;
272    }
273}