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