    001package net.sf.cpsolver.exam.split;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashMap;
    006import java.util.Hashtable;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.TreeSet;
    011
    012import net.sf.cpsolver.exam.criteria.ExamCriterion;
    013import net.sf.cpsolver.exam.criteria.StudentBackToBackConflicts;
    014import net.sf.cpsolver.exam.criteria.StudentDirectConflicts;
    015import net.sf.cpsolver.exam.criteria.StudentMoreThan2ADayConflicts;
    016import net.sf.cpsolver.exam.model.Exam;
    017import net.sf.cpsolver.exam.model.ExamPeriod;
    018import net.sf.cpsolver.exam.model.ExamPlacement;
    019import net.sf.cpsolver.exam.model.ExamRoomPlacement;
    020import net.sf.cpsolver.exam.model.ExamStudent;
    021import net.sf.cpsolver.ifs.criteria.Criterion;
    022import net.sf.cpsolver.ifs.solver.Solver;
    023import 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 Tomáš Müller<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 */
    066public 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}