001    package net.sf.cpsolver.exam.split;
002    
003    import java.util.HashSet;
004    import java.util.List;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.exam.criteria.RoomPenalty;
008    import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
009    import net.sf.cpsolver.exam.model.Exam;
010    import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
011    import net.sf.cpsolver.exam.model.ExamPlacement;
012    import net.sf.cpsolver.exam.model.ExamRoomPlacement;
013    import net.sf.cpsolver.exam.model.ExamStudent;
014    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
015    import net.sf.cpsolver.ifs.model.Neighbour;
016    import net.sf.cpsolver.ifs.solution.Solution;
017    import net.sf.cpsolver.ifs.solver.Solver;
018    import net.sf.cpsolver.ifs.util.DataProperties;
019    import net.sf.cpsolver.ifs.util.ToolBox;
020    
021    import org.apache.log4j.Logger;
022    
023    /**
024     * Experimental neighbor selection that allows an exam to be split
025     * into two if it decreases the number of student conflicts.
026     * <br><br>
027     * An examination split is improving (and is considered) if the weighted
028     * number of student conflicts that will be removed by the split is bigger 
029     * than the weight of the splitter criterion {@link ExamSplitter#getWeight()}.
030     * 
031     * <br>
032     * 
033     * @version ExamTT 1.2 (Examination Timetabling)<br>
034     *          Copyright (C) 2008 - 2013 Tomas Muller<br>
035     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
036     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
037     * <br>
038     *          This library is free software; you can redistribute it and/or modify
039     *          it under the terms of the GNU Lesser General Public License as
040     *          published by the Free Software Foundation; either version 3 of the
041     *          License, or (at your option) any later version. <br>
042     * <br>
043     *          This library is distributed in the hope that it will be useful, but
044     *          WITHOUT ANY WARRANTY; without even the implied warranty of
045     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
046     *          Lesser General Public License for more details. <br>
047     * <br>
048     *          You should have received a copy of the GNU Lesser General Public
049     *          License along with this library; if not see
050     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
051     */
052    public class ExamSplitMoves implements NeighbourSelection<Exam, ExamPlacement> {
053        private static Logger sLog = Logger.getLogger(ExamSplitMoves.class);
054        private ExamSplitter iSplitter = null;
055    
056        /** Constructor */
057        public ExamSplitMoves(DataProperties properties) {}
058    
059        /** Initialization */
060        @Override
061        public void init(Solver<Exam, ExamPlacement> solver) {
062            iSplitter = (ExamSplitter)solver.currentSolution().getModel().getCriterion(ExamSplitter.class);
063            if (iSplitter == null) throw new RuntimeException("ExamSplitter criterion needs to be used as well.");
064        }
065        
066        /**
067         * Find best available rooms for a new exam (that is to be split from the given one),
068         * if is is assigned into the given examination period.
069         * 
070         * @param exam an exam to be split
071         * @param period a period to be assigned to the new exam
072         * @param examSize size of the new exam (i.e., the number of students that will be moved from the given exam to the new one)
073         * @return best room placement for the given exam and period 
074         */
075        public Set<ExamRoomPlacement> findBestAvailableRooms(Exam exam, ExamPeriodPlacement period, int examSize) {
076            if (exam.getMaxRooms() == 0) return new HashSet<ExamRoomPlacement>();
077            double sw = exam.getModel().getCriterion(RoomSizePenalty.class).getWeight();
078            double pw = exam.getModel().getCriterion(RoomPenalty.class).getWeight();
079            loop: for (int nrRooms = 1; nrRooms <= exam.getMaxRooms(); nrRooms++) {
080                HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
081                int size = 0;
082                while (rooms.size() < nrRooms && size < examSize) {
083                    int minSize = (examSize - size) / (nrRooms - rooms.size());
084                    ExamRoomPlacement best = null;
085                    double bestWeight = 0;
086                    int bestSize = 0;
087                    for (ExamRoomPlacement room : exam.getRoomPlacements()) {
088                        if (!room.isAvailable(period.getPeriod()))
089                            continue;
090                        if (!room.getRoom().getPlacements(period.getPeriod()).isEmpty())
091                            continue;
092                        if (rooms.contains(room))
093                            continue;
094                        int s = room.getSize(exam.hasAltSeating());
095                        if (s < minSize)
096                            break;
097                        int p = room.getPenalty(period.getPeriod());
098                        double w = pw * p + sw * (s - minSize);
099                        double d = 0;
100                        if (!rooms.isEmpty()) {
101                            for (ExamRoomPlacement r : rooms) {
102                                d += r.getDistanceInMeters(room);
103                            }
104                            w += d / rooms.size();
105                        }
106                        if (best == null || bestWeight > w) {
107                            best = room;
108                            bestSize = s;
109                            bestWeight = w;
110                        }
111                    }
112                    if (best == null)
113                        continue loop;
114                    rooms.add(best);
115                    size += bestSize;
116                }
117                if (size >= examSize)
118                    return rooms;
119            }
120            return null;
121        }
122        
123        /**
124         * Find a best split for the given exam. Only improving neighbors are considered. 
125         * @param exam an exam to be split
126         * @return best neighbor that will do the split
127         */
128        public ExamSplitNeighbour bestSplit(Exam exam) {
129            ExamSplitNeighbour split = null;
130            ExamPlacement placement = exam.getAssignment();
131            int px = ToolBox.random(exam.getPeriodPlacements().size());
132            for (int p = 0; p < exam.getPeriodPlacements().size(); p++) { // Iterate over possible periods
133                ExamPeriodPlacement period = exam.getPeriodPlacements().get((p + px) % exam.getPeriodPlacements().size());
134                if (placement != null && placement.getPeriod().equals(period)) continue;
135                // Try to create a neighbor
136                ExamSplitNeighbour s = new ExamSplitNeighbour(exam, new ExamPlacement(exam, period, null));
137                if (split == null || s.value() < split.value()) {
138                    // If improving, try to find available rooms
139                    Set<ExamRoomPlacement> rooms = findBestAvailableRooms(exam, period, s.nrStudents());
140                    if (rooms != null) {
141                        // Remember as best split
142                        s.placement().getRoomPlacements().addAll(rooms);
143                        split = s;
144                    }
145                }
146            }
147            return split;
148        }
149    
150        /**
151         * Select a split (split an exam into two), a merge (merge two split exams back together) or 
152         * shuffle operation (move students between two exams that has been split before).
153         */
154        @Override
155        public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
156            // Randomly select an exam
157            Exam exam = ToolBox.random(solution.getModel().assignedVariables());
158            
159            // Parent exam (its either the exam itself, or its parent if it has been already split)
160            Exam parent = iSplitter.parent(exam);
161            // Its children (if already split)
162            List<Exam> children = iSplitter.children(parent);
163            
164            // Already split -> try shuffle
165            if (children != null && !children.isEmpty()) {
166                ExamShuffleNeighbour shuffle = new ExamShuffleNeighbour(exam);
167                if (shuffle.value() < 0.0) return shuffle;
168            }
169            
170            // Can split -> try a split
171            if (iSplitter.canSplit(exam)) {
172                ExamSplitNeighbour split = bestSplit(exam);
173                if (split != null && split.value() < 0.0) return split;
174            }
175            
176            // Can merge -> try to merge
177            if (iSplitter.canMerge(exam)) {
178                ExamMergeNeighbour merge = new ExamMergeNeighbour(exam);
179                if (merge.value() < 0.0) return merge;
180            }
181    
182            return null;
183        }
184        
185        /**
186         * Split an exam into two
187         */
188        protected class ExamSplitNeighbour extends Neighbour<Exam, ExamPlacement> {
189            private Exam iExam;
190            private ExamPlacement iPlacement;
191            private double iValue = 0.0;
192            private int iNrStudents = 0;
193            
194            /**
195             * Split an exam into two, assign the new exam into the given placement.
196             * @param exam an exam to be split
197             * @param placement a placement to be assigned to the new exam
198             */
199            public ExamSplitNeighbour(Exam exam, ExamPlacement placement) {
200                iExam = exam;
201                iPlacement = placement;
202                
203                // Parent exam (its either the exam itself, or its parent if it has been already split)
204                Exam parent = iSplitter.parent(exam);
205                // Its children (if already split)
206                List<Exam> children = iSplitter.children(parent);
207                
208                // Compute improvement
209                // Consider moving all students of the parent exam to the new placement
210                for (ExamStudent student: parent.getStudents()) {
211                    double delta = iSplitter.delta(student, parent.getAssignment(), placement);
212                    if (delta < 0.0) {
213                        iValue += delta;
214                        iNrStudents ++;
215                    }
216                }
217                // If there already are other children, consider moving students of these children to the
218                // new placement as well
219                if (children != null)
220                    for (Exam child: children)
221                        for (ExamStudent student: child.getStudents()) {
222                            double delta = iSplitter.delta(student, child.getAssignment(), placement);
223                            if (delta < 0.0) {
224                                iValue += delta;
225                                iNrStudents ++;
226                            }
227                        }
228                
229                // Increase the weight by the splitter criterion weight
230                iValue += iSplitter.getWeight();
231            }
232    
233            /**
234             * Perform the split.
235             */
236            @Override
237            public void assign(long iteration) {
238                sLog.info("Splitting " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", " + iPlacement.getName() + ", value: " + iValue + ")");
239                iSplitter.split(iExam, iteration, iPlacement);
240            }
241    
242            /**
243             * Value of the split. This is the weight of the splitter criterion minus the weighted sum of
244             * all student conflicts that will be removed by the split.
245             */
246            @Override
247            public double value() {
248                return iValue;
249            }
250    
251            /**
252             * Number of students that will be moved into the new exam.
253             */
254            public int nrStudents() {
255                return iNrStudents;
256            }
257    
258            /**
259             * Exam to be split.
260             */
261            public Exam exam() {
262                return iExam;
263            }
264    
265            /**
266             * Placement of the new exam.
267             */
268            public ExamPlacement placement() {
269                return iPlacement;
270            }
271        }
272        
273        /**
274         * Merge two exams that have been split before back into one. This moves
275         * the students from the child exam back to its parent and removes the
276         * child exam from the problem.
277         */
278        protected class ExamMergeNeighbour extends Neighbour<Exam, ExamPlacement> {
279            private Exam iExam;
280            private double iValue = 0.0;
281            
282            /**
283             * Child exam to be removed. 
284             */
285            public ExamMergeNeighbour(Exam exam) {
286                iExam = exam;
287                
288                // Parent exam (its either the exam itself, or its parent if it has been already split)
289                Exam parent = iSplitter.parent(exam);
290                // Its children (if already split)
291                List<Exam> children = iSplitter.children(parent);
292    
293                // Compute improvement
294                for (ExamStudent student: exam.getStudents()) {
295                    // Try to move each student either back to the parent exam or to any of the other
296                    // children exams, if there are any
297                    double delta = iSplitter.delta(student, exam.getAssignment(), parent.getAssignment());
298                    for (Exam child: children) {
299                        if (child.equals(exam)) continue;
300                        double d = iSplitter.delta(student, exam.getAssignment(), child.getAssignment());
301                        if (d < delta) delta = d;
302                    }
303                    iValue += delta;
304                }
305                // Decrease the weight by the splitter criterion weight
306                iValue -= iSplitter.getWeight();
307            }
308    
309            /**
310             * Perform the merge.
311             */        
312            @Override
313            public void assign(long iteration) {
314                sLog.info("Mergning " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", value: " + iValue + ")");
315                iSplitter.merge(iExam, iteration);
316            }
317    
318            /**
319             * Value of the merge. This is the weighted sum of all student conflicts that will be added by the merge,
320             * minus the weight of the splitter criterion.
321             */
322            @Override
323            public double value() {
324                return iValue;
325            }
326            
327            /**
328             * Number of students that will be moved back to the parent exam or to some other child (if there are any).
329             */
330            public int nrStudents() {
331                return iExam.getStudents().size();
332            }
333    
334            /**
335             * Exam to be merged.
336             */
337            public Exam exam() {
338                return iExam;
339            }
340        }
341        
342        /**
343         * Shuffle students between the parent exam and all of its children. Only swaps
344         * that are decreasing the weighted sum of student conflicts are considered.
345         */
346        protected class ExamShuffleNeighbour extends Neighbour<Exam, ExamPlacement> {
347            private Exam iExam;
348            private double iValue = 0.0;
349            
350            /**
351             * Exam to be shuffled.
352             */
353            public ExamShuffleNeighbour(Exam exam) {
354                iExam = exam;
355    
356                // Parent exam (its either the exam itself, or its parent if it has been already split)
357                Exam parent = iSplitter.parent(exam);
358                // Its children (if already split)
359                List<Exam> children = iSplitter.children(parent);
360    
361                // Compute improvement
362                // Try moving students away from parent
363                for (ExamStudent student: parent.getStudents()) {
364                    Double delta = null;
365                    for (Exam x: children) {
366                        double d = iSplitter.delta(student, parent.getAssignment(), x.getAssignment());
367                        if (delta == null || d < delta) delta = d;
368                    }
369                    if (delta != null && delta < 0) iValue += delta;
370                }
371                
372                // Try moving students away from any child
373                for (Exam child: children) {
374                    for (ExamStudent student: child.getStudents()) {
375                        double delta = iSplitter.delta(student, child.getAssignment(), parent.getAssignment());
376                        for (Exam x: children) {
377                            if (x.equals(child)) continue;
378                            double d = iSplitter.delta(student, child.getAssignment(), x.getAssignment());
379                            if (d < delta) delta = d;
380                        }
381                        if (delta < 0) iValue += delta;
382                    }
383                }
384            }
385    
386            /**
387             * Perform the shuffle.
388             */        
389            @Override
390            public void assign(long iteration) {
391                sLog.info("Shuffling " + iExam.getName() + " (" + iExam.getAssignment().getName() + ", value: " + iValue + ")");
392                iSplitter.shuffle(iExam, iteration);
393            }
394    
395            /**
396             * Value of the shuffle. This is the weighted sum of all student conflicts that will be removed by the shuffle.
397             */
398            @Override
399            public double value() {
400                return iValue;
401            }
402            
403            /**
404             * Exam to be shuffled.
405             */
406            public Exam exam() {
407                return iExam;
408            }
409        }
410    }