001    package net.sf.cpsolver.exam.split;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashMap;
006    import java.util.Hashtable;
007    import java.util.List;
008    import java.util.Map;
009    import java.util.Set;
010    import java.util.TreeSet;
011    
012    import net.sf.cpsolver.exam.criteria.ExamCriterion;
013    import net.sf.cpsolver.exam.criteria.StudentBackToBackConflicts;
014    import net.sf.cpsolver.exam.criteria.StudentDirectConflicts;
015    import net.sf.cpsolver.exam.criteria.StudentMoreThan2ADayConflicts;
016    import net.sf.cpsolver.exam.model.Exam;
017    import net.sf.cpsolver.exam.model.ExamPeriod;
018    import net.sf.cpsolver.exam.model.ExamPlacement;
019    import net.sf.cpsolver.exam.model.ExamRoomPlacement;
020    import net.sf.cpsolver.exam.model.ExamStudent;
021    import net.sf.cpsolver.ifs.criteria.Criterion;
022    import net.sf.cpsolver.ifs.solver.Solver;
023    import net.sf.cpsolver.ifs.util.DataProperties;
024    
025    /**
026     * Experimental criterion that allows an exam to be split
027     * into two if it decreases the number of student conflicts.
028     * <br><br>
029     * An examination split is improving (and is considered) if the weighted
030     * number of student conflicts that will be removed by the split is bigger 
031     * than the weight of the splitter criterion {@link ExamSplitter#getWeight()}.
032     * <br><br>
033     * To enable examination splitting, following parameters needs to be set:
034     * <ul>
035     *      <li>HillClimber.AdditionalNeighbours=net.sf.cpsolver.exam.split.ExamSplitMoves
036     *      <li>GreatDeluge.AdditionalNeighbours=net.sf.cpsolver.exam.split.ExamSplitMoves
037     *      <li>Exams.AdditionalCriteria=net.sf.cpsolver.exam.split.ExamSplitter
038     *      <li>Exams.ExamSplitWeight=500
039     * </ul>
040     * The Exams.ExamSplitWeight represents the weight of a split. For instance, to
041     * allow only splits that decrease the number of student direct conflicts,
042     * half of the weight of a direct student conflict is a good value for this
043     * weight. 
044     * 
045     * <br>
046     * 
047     * @version ExamTT 1.2 (Examination Timetabling)<br>
048     *          Copyright (C) 2008 - 2013 Tomas Muller<br>
049     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
050     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
051     * <br>
052     *          This library is free software; you can redistribute it and/or modify
053     *          it under the terms of the GNU Lesser General Public License as
054     *          published by the Free Software Foundation; either version 3 of the
055     *          License, or (at your option) any later version. <br>
056     * <br>
057     *          This library is distributed in the hope that it will be useful, but
058     *          WITHOUT ANY WARRANTY; without even the implied warranty of
059     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
060     *          Lesser General Public License for more details. <br>
061     * <br>
062     *          You should have received a copy of the GNU Lesser General Public
063     *          License along with this library; if not see
064     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
065     */
066    public class ExamSplitter extends ExamCriterion {
067        private long iLastSplitId = 0;
068        private Map<Exam, List<Exam>> iChildren = new HashMap<Exam, List<Exam>>();
069        private Map<Exam, Exam> iParent = new HashMap<Exam, Exam>();
070        private Criterion<Exam, ExamPlacement> iStudentDirectConflicts, iStudentMoreThan2ADayConflicts, iStudentBackToBackConflicts;
071        
072        private Map<Exam, List<ExamPlacement>> iBestSplit = null;
073        
074        /** Examination splitter criterion. */
075        public ExamSplitter() {
076            iValueUpdateType = ValueUpdateType.NoUpdate;
077        }
078        
079        /** Initialization */
080        @Override
081        public boolean init(Solver<Exam, ExamPlacement> solver) {
082            boolean ret = super.init(solver);
083            iStudentDirectConflicts = solver.currentSolution().getModel().getCriterion(StudentDirectConflicts.class);
084            iStudentMoreThan2ADayConflicts = solver.currentSolution().getModel().getCriterion(StudentMoreThan2ADayConflicts.class);
085            iStudentBackToBackConflicts = solver.currentSolution().getModel().getCriterion(StudentBackToBackConflicts.class);
086            return ret;
087        }
088        
089        /** Returns Exams.ExamSplitWeight */
090        @Override
091        public String getWeightName() {
092            return "Exams.ExamSplitWeight";
093        }
094        
095        /** Returns examSplitWeight */
096        @Override
097        public String getXmlWeightName() {
098            return "examSplitWeight";
099        }
100        
101        /** Returns half of a student direct conflict weight */
102        @Override
103        public double getWeightDefault(DataProperties config) {
104            return (iStudentDirectConflicts != null ? iStudentDirectConflicts.getWeight() / 2 : 500.0);
105        }
106        
107        private boolean isDayBreakBackToBack() {
108            return ((StudentBackToBackConflicts)iStudentBackToBackConflicts).isDayBreakBackToBack();
109        }
110        
111        /** True, if an exam can be split */
112        public boolean canSplit(Exam exam) {
113            if (iParent.containsKey(exam)) return false; // already split
114            return true;
115        }
116        
117        /**
118         * Parent of an exam that has been split.
119         * @param exam an exam in question
120         * @return parent exam if the exam has been split, or the exam itself otherwise (each non-split exam is its own parent)
121         */
122        public Exam parent(Exam exam) {
123            return (iParent.containsKey(exam) ? iParent.get(exam) : exam);
124        }
125        
126        /**
127         * Children exams of an exam that has been split. These are all the exams that the parent exam has been split into.
128         * @param parent an exam in question
129         * @return all children exams, or null of the exam has not been split yet
130         */
131        public List<Exam> children(Exam parent) {
132            return iChildren.get(parent);
133        }
134        
135        /**
136         * Split an exam
137         * @param parent an exam to be split
138         * @param iteration solver iteration
139         * @param placement placement of the new exam
140         * @return new exam assigned to the given placement with students moved into it; null if the given exam cannot be split
141         */
142        public Exam split(Exam parent, long iteration, ExamPlacement placement) {
143            if (!canSplit(parent)) return null;
144    
145            // Create the child exam
146            Exam child = new Exam(--iLastSplitId, parent.getName(), parent.getLength(), parent.hasAltSeating(), parent.getMaxRooms(), parent.getMinSize(), parent.getPeriodPlacements(), parent.getRoomPlacements());
147            child.setSizeOverride(parent.getSizeOverride());
148            child.setPrintOffset(parent.getPrintOffset());
149            child.setAveragePeriod(parent.getAveragePeriod());
150            child.getOwners().addAll(parent.getOwners());
151            
152            // Update the parent and children structures
153            iParent.put(child, parent);
154            List<Exam> children = iChildren.get(parent);
155            if (children == null) {
156                children = new ArrayList<Exam>();
157                iChildren.put(parent, children);
158            }
159            children.add(child);
160            iValue += 1.0;
161            
162            // Add into model
163            parent.getModel().addVariable(child);
164            for (ExamRoomPlacement room : child.getRoomPlacements()) 
165                room.getRoom().addVariable(child);
166            if (placement != null) child.assign(iteration, new ExamPlacement(child, placement.getPeriodPlacement(), placement.getRoomPlacements()));
167            
168            
169            // Shuffle students between parent exam and its children
170            shuffle(parent, iteration);
171    
172            // Return the new exam
173            return child;
174        }
175        
176        /** True, if the given exam can be merged (it has been split) */
177        public boolean canMerge(Exam exam) {
178            if (!iParent.containsKey(exam)) return false; // not split
179            return true;
180        }
181        
182        /**
183         * Merge an exam
184         * @param child an exam to be merged
185         * @param iteration solver iteration
186         * @return parent exam of the exam that has been deleted; null if the given exam cannot be merged
187         */
188        public Exam merge(Exam child, long iteration) {
189            if (!canMerge(child)) return null;
190            
191            // Update the parent and children structures
192            Exam parent = iParent.get(child);
193            iParent.remove(child);
194            List<Exam> children = iChildren.get(parent);
195            children.remove(child);
196            iValue -= 1.0;
197            
198            // Unassign parent and the given exam
199            ExamPlacement parentPlacement = parent.getAssignment();
200            if (parentPlacement != null) parent.unassign(iteration);
201            if (child.getAssignment() != null) child.unassign(iteration);
202    
203            // Move students back from the given exam
204            for (ExamStudent student: new ArrayList<ExamStudent>(child.getStudents())) {
205                student.removeVariable(child);
206                student.addVariable(parent);
207            }
208            
209            // Remove the given exam from the model
210            for (ExamRoomPlacement room : child.getRoomPlacements()) 
211                room.getRoom().removeVariable(child);
212            parent.getModel().removeVariable(child);
213            
214            // Assign parent exam back
215            if (parentPlacement != null) parent.assign(iteration, parentPlacement);
216            
217            
218            // Shuffle students between parent exam and its remaining children
219            shuffle(parent, iteration);
220            
221            // Return parent exam
222            return parent;
223        }
224        
225        /**
226         * Difference in the total weighted student conflicts (including {@link StudentDirectConflicts},
227         * {@link StudentMoreThan2ADayConflicts}, and {@link StudentBackToBackConflicts}) if a student
228         * is moved from an exam with one placement into an exam with another placement.
229         * @param student a student in question
230         * @param oldPlacement placement of the exam in which the student is now
231         * @param newPlacement placement of the exam into which the student would be moved
232         * @return difference in the student conflict weight
233         */
234        public double delta(ExamStudent student, ExamPlacement oldPlacement, ExamPlacement newPlacement) {
235            double delta = 0;
236            
237            // Weights of removing student form the old placement 
238            if (oldPlacement != null) {
239                Exam exam = oldPlacement.variable();
240                ExamPeriod period = oldPlacement.getPeriod();
241                Set<Exam> examsThisPeriod = student.getExams(period);
242                if (examsThisPeriod.size() > (examsThisPeriod.contains(exam) ? 1 : 0))
243                    delta -= iStudentDirectConflicts.getWeight(); // will remove a direct conflict
244                ExamPeriod prev = period.prev();
245                if (prev != null && (prev.getDay() == period.getDay() || isDayBreakBackToBack())) {
246                    Set<Exam> examsPrevPeriod = student.getExams(prev);
247                    if (examsPrevPeriod.size() > (examsPrevPeriod.contains(exam) ? 1 : 0))
248                        delta -= iStudentBackToBackConflicts.getWeight(); // will remove a back-to-back conflict
249                }
250                ExamPeriod next = period.next();
251                if (next != null && (next.getDay() == period.getDay() || isDayBreakBackToBack())) {
252                    Set<Exam> examsNextPeriod = student.getExams(next);
253                    if (examsNextPeriod.size() > (examsNextPeriod.contains(exam) ? 1 : 0))
254                        delta -= iStudentBackToBackConflicts.getWeight(); // will remove a back-to-back conflict
255                }
256                Set<Exam> examsInADay = student.getExamsADay(period);
257                if (examsInADay.size() > (examsInADay.contains(exam) ? 3 : 2))
258                    delta -= iStudentMoreThan2ADayConflicts.getWeight(); // will remove a more than 2 on a day conflict
259            }
260            
261            // Weights of moving student into the new placement
262            if (newPlacement != null) {
263                Exam exam = newPlacement.variable();
264                ExamPeriod period = newPlacement.getPeriod();
265                Set<Exam> examsThisPeriod = student.getExams(period);
266                if (examsThisPeriod.size() > (examsThisPeriod.contains(exam) ? 1 : 0))
267                    delta += iStudentDirectConflicts.getWeight(); // will add a direct conflict
268                ExamPeriod prev = period.prev();
269                if (prev != null && (prev.getDay() == period.getDay() || isDayBreakBackToBack())) {
270                    Set<Exam> examsPrevPeriod = student.getExams(prev);
271                    if (examsPrevPeriod.size() > (examsPrevPeriod.contains(exam) ? 1 : 0))
272                        delta += iStudentBackToBackConflicts.getWeight(); // will add a back-to-back conflict
273                }
274                ExamPeriod next = period.next();
275                if (next != null && (next.getDay() == period.getDay() || isDayBreakBackToBack())) {
276                    Set<Exam> examsNextPeriod = student.getExams(next);
277                    if (examsNextPeriod.size() > (examsNextPeriod.contains(exam) ? 1 : 0))
278                        delta += iStudentBackToBackConflicts.getWeight(); // will add a back-to-back conflict
279                }
280                Set<Exam> examsInADay = student.getExamsADay(period);
281                if (examsInADay.size() > (examsInADay.contains(exam) ? 3 : 2))
282                    delta += iStudentMoreThan2ADayConflicts.getWeight(); // will add a more than 2 on a day conflict
283            }
284            
285            return delta;
286        }
287        
288        /**
289         * Shuffle students between the given exam and all the other exams in the split (if there are any).
290         * Only moves between exams that improve {@link ExamSplitter#delta(ExamStudent, ExamPlacement, ExamPlacement)} are
291         * considered.
292         * @param exam an exam in question
293         * @param iteration solver iteration
294         */
295        public void shuffle(Exam exam, long iteration) {
296            // Parent exam (its either the exam itself, or its parent if it has been already split)
297            Exam parent = (iParent.containsKey(exam) ? iParent.get(exam) : exam);
298            // Its children (if already split)
299            List<Exam> children = iChildren.get(parent);
300            
301            if (children != null && !children.isEmpty()) {
302                // Unassign all involved exams
303                Map<Exam, ExamPlacement> assignments = new HashMap<Exam, ExamPlacement>();
304                if (parent.getAssignment() != null) {
305                    assignments.put(parent, parent.getAssignment());
306                    parent.unassign(iteration);
307                }
308                for (Exam child: children) {
309                    if (child.getAssignment() != null) {
310                        assignments.put(child, child.getAssignment());
311                        child.unassign(iteration);
312                    }
313                }
314                
315                // Move away from parent
316                for (ExamStudent student: new ArrayList<ExamStudent>(parent.getStudents())) {
317                    Exam child = null; double delta = 0;
318                    for (Exam x: children) {
319                        double d = delta(student, assignments.get(parent), assignments.get(x));
320                        if (child == null || d < delta) {
321                            delta = d; child = x;
322                        }
323                    }
324                    if (child != null && delta < 0) {
325                        student.removeVariable(parent);
326                        student.addVariable(child);
327                    }
328                }
329                
330                // Move students away from a child
331                for (Exam child: children) {
332                    for (ExamStudent student: new ArrayList<ExamStudent>(child.getStudents())) {
333                        Exam other = parent; double delta = delta(student, assignments.get(child), assignments.get(parent));
334                        for (Exam x: children) {
335                            if (x.equals(child)) continue;
336                            double d = delta(student, assignments.get(child), assignments.get(x));
337                            if (d < delta) {
338                                delta = d; other = x;
339                            }
340                        }
341                        if (other != null && delta < 0) {
342                            student.removeVariable(child);
343                            student.addVariable(other);
344                        }
345                    }
346                }
347                
348                // Assign everything back
349                ExamPlacement parentPlacement = assignments.get(parent);
350                if (parentPlacement != null) parent.assign(iteration, parentPlacement);
351                for (Exam child: children) {
352                    ExamPlacement placement = assignments.get(child);
353                    if (placement != null) child.assign(iteration, placement);
354                }
355            }
356        }
357    
358        /** Not used */
359        @Override
360        public double getValue(ExamPlacement value, Set<ExamPlacement> conflicts) {
361            return 0.0;
362        }
363        
364        /** Not used */
365        @Override
366        public double[] getBounds(Collection<Exam> exams) {
367            return new double[] { 0.0, 0.0 };
368        }
369        
370        @Override
371        public String toString() {
372            return "XX:" + sDoubleFormat.format(getValue());
373        }
374        
375        /** Lists the split */
376        @Override
377        public void getInfo(Map<String, String> info) {
378            if (!iChildren.isEmpty()) {
379                int parents = 0;
380                String split = "";
381                for (Exam parent: new TreeSet<Exam>(iChildren.keySet())) {
382                    List<Exam> children = iChildren.get(parent);
383                    if (children.isEmpty()) continue;
384                    split += "\n  ";
385                    parents ++;
386                    split += parent.getName() + ": " + parent.getStudents().size() + " (" + (parent.getAssignment() == null ? "N/A" : parent.getAssignment().getPeriod()) + ")";
387                    for (Exam child: children)
388                        split += " + " + child.getStudents().size() + " (" + (child.getAssignment() == null ? "N/A" : child.getAssignment().getPeriod()) + ")";
389                }
390                if (parents > 0)
391                    info.put("Examination Splits", parents + split);
392            }
393        }
394    
395        /** Best solution was saved, remember the current splits */
396        @Override
397        public void bestSaved() {
398            super.bestSaved();
399            
400            if (iBestSplit == null)
401                iBestSplit = new Hashtable<Exam, List<ExamPlacement>>();
402            else
403                iBestSplit.clear();
404            
405            for (Map.Entry<Exam, List<Exam>> entry: iChildren.entrySet()) {
406                Exam parent = entry.getKey();
407                List<ExamPlacement> placements = new ArrayList<ExamPlacement>();
408                for (Exam child: entry.getValue()) {
409                    if (child.getAssignment() != null)
410                        placements.add(child.getAssignment());
411                }
412                if (!placements.isEmpty())
413                    iBestSplit.put(parent, placements);
414            }
415        }
416    
417        /** Best solution was restored, change the splits back to what it was in the best solution */
418        @Override
419        public void bestRestored() {
420            super.bestRestored();
421            
422            // Merge those that are not split
423            for (Exam parent: new ArrayList<Exam>(iChildren.keySet())) {
424                List<Exam> children = new ArrayList<Exam>(iChildren.get(parent));
425                List<ExamPlacement> placements = iBestSplit.get(parent);
426                for (int i = (placements == null ? 0 : placements.size()); i < children.size(); i++)
427                    merge(children.get(i), 0);
428            }
429            
430            // Assign best placements to all children, create children if needed
431            iValue = 0;
432            for (Exam parent: iBestSplit.keySet()) {
433                List<ExamPlacement> placements = iBestSplit.get(parent);
434                for (int i = 0; i < placements.size(); i++) {
435                    List<Exam> children = iChildren.get(parent);
436                    if (children == null || children.size() <= i) { // create a child if needed
437                        split(parent, 0, placements.get(i));
438                    } else { // otherwise, just assign the placement
439                        children.get(i).assign(0, new ExamPlacement(children.get(i), placements.get(i).getPeriodPlacement(), placements.get(i).getRoomPlacements()));
440                    }
441                }
442                iValue += placements.size();
443            }
444        }
445    }