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