001    package net.sf.cpsolver.exam.neighbours;
002    
003    import java.util.ArrayList;
004    import java.util.HashMap;
005    import java.util.HashSet;
006    import java.util.List;
007    import java.util.Map;
008    import java.util.Set;
009    
010    import net.sf.cpsolver.exam.criteria.DistributionPenalty;
011    import net.sf.cpsolver.exam.criteria.RoomPenalty;
012    import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
013    import net.sf.cpsolver.exam.model.Exam;
014    import net.sf.cpsolver.exam.model.ExamDistributionConstraint;
015    import net.sf.cpsolver.exam.model.ExamModel;
016    import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
017    import net.sf.cpsolver.exam.model.ExamPlacement;
018    import net.sf.cpsolver.exam.model.ExamRoomPlacement;
019    import net.sf.cpsolver.exam.model.ExamRoomSharing;
020    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
021    import net.sf.cpsolver.ifs.model.LazySwap;
022    import net.sf.cpsolver.ifs.model.Neighbour;
023    import net.sf.cpsolver.ifs.solution.Solution;
024    import net.sf.cpsolver.ifs.solver.Solver;
025    import net.sf.cpsolver.ifs.util.DataProperties;
026    import 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 Tomas Muller<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     */
056    public 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    }