    001package org.cpsolver.exam.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.HashMap;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.TreeSet;
    011
    012import org.cpsolver.exam.model.Exam;
    013import org.cpsolver.exam.model.ExamInstructor;
    014import org.cpsolver.exam.model.ExamModel;
    015import org.cpsolver.exam.model.ExamPeriodPlacement;
    016import org.cpsolver.exam.model.ExamPlacement;
    017import org.cpsolver.exam.model.ExamRoomPlacement;
    018import org.cpsolver.exam.model.ExamStudent;
    019import org.cpsolver.ifs.assignment.Assignment;
    020import org.cpsolver.ifs.heuristics.NeighbourSelection;
    021import org.cpsolver.ifs.model.Neighbour;
    022import org.cpsolver.ifs.solution.Solution;
    023import org.cpsolver.ifs.solver.Solver;
    024import org.cpsolver.ifs.util.DataProperties;
    025import org.cpsolver.ifs.util.JProf;
    026import org.cpsolver.ifs.util.Progress;
    027
    028
    029/**
    030 * Examination timetabling construction heuristics based on graph vertex coloring.
    031 * This approach is trying to find a (direct) conflict-free examination schedule using
    032 * a depth-first search, assigning periods to exams in a way that there is not student or
    033 * instructor direct conflict.
    034 * <br>
    035 * <br>
    036 * This heuristics works in following modes (defined by Exam.ColoringConstructionMode).
    037 * <ul>
    038 * <li>Greedy .. all exams are greedily assigned with periods (and best available rooms);
    039 *   Exams with smallest number of available periods (or highest number of connected exams
    040 *   if multiple) are assigned first.
    041 * <li>ColorOnly .. all exams are assigned with periods using a depth-first search (ignoring
    042 *   all other constraints), this coloring is then extended to exam placements as much as possible
    043 * <li>Irredundant .. other constraints (distributions, rooms) are considered, however, to
    044 *   speedup the search redundant colorings are avoided -- this may not find a complete solution,
    045 *   especially when some periods are not swap-able
    046 * <li>Full .. all constraints are considered, a complete solution is guaranteed to be found, if
    047 *   it exists (and enough time is given)
    048 * </ul>
    049 * <br>
    050 * Time to run can  be limited using Exam.ColoringConstructionTimeLimit parameter (double precision,
    051 * limit is in seconds, defaults to 5 minutes)
    052 * <br>
    053 * <br>
    054 *
    055 * @version ExamTT 1.3 (Examination Timetabling)<br>
    056 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
    057 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    058 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    059 * <br>
    060 *          This library is free software; you can redistribute it and/or modify
    061 *          it under the terms of the GNU Lesser General Public License as
    062 *          published by the Free Software Foundation; either version 3 of the
    063 *          License, or (at your option) any later version. <br>
    064 * <br>
    065 *          This library is distributed in the hope that it will be useful, but
    066 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    067 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    068 *          Lesser General Public License for more details. <br>
    069 * <br>
    070 *          You should have received a copy of the GNU Lesser General Public
    071 *          License along with this library; if not see
    072 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    073 */
    074public class ExamColoringConstruction implements NeighbourSelection<Exam, ExamPlacement> {
    075    private Progress iProgress;
    076    private double iT0;
    077    private double iTimeLimit = 300.0;
    078    private boolean iTimeLimitReached = false;
    079    private Mode iMode = Mode.Full;
    080    private Solver<Exam, ExamPlacement> iSolver;
    081
    082    private static enum Mode {
    083        Greedy(true, false, true),
    084        ColorOnly(false, false, false),
    085        Irredundant(false, false, false),
    086        Full(false, true, true);
    087        boolean iGreedy, iRedundant, iConstraintCheck;
    088        private Mode(boolean gr, boolean r, boolean ch) { iGreedy = gr; iRedundant = r; iConstraintCheck = ch; }
    089        public boolean isGreedy() { return iGreedy; }
    090        public boolean isRedundant() { return iRedundant; }
    091        public boolean isConstraintCheck() { return iConstraintCheck; }
    092    }
    093
    094    public ExamColoringConstruction(DataProperties config) {
    095        iTimeLimit = config.getPropertyDouble("Exam.ColoringConstructionTimeLimit", iTimeLimit);
    096        iMode = Mode.valueOf(config.getProperty("Exam.ColoringConstructionMode", iMode.name()));
    097    }
    098
    099    private boolean backTrack(Solution<Exam, ExamPlacement> solution, int index, HashSet<Integer> colorsUsedSoFar, Collection<Vertex> vertices) {
    100        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
    101        if (iTimeLimitReached || iSolver.isStop()) return false;
    102        if (JProf.currentTimeSec() - iT0 > iTimeLimit) {
    103            iTimeLimitReached = true;
    104            return false;
    105        }
    106        if (index == vertices.size()) return true;
    107        if (iProgress.getProgress() < index) {
    108            iProgress.setProgress(index);
    109            if (iMode.isConstraintCheck())
    110                solution.saveBest();
    111        }
    112        Vertex vertex = null;
    113        for (Vertex v: vertices) {
    114            if (v.color() >= 0) continue;
    115            if (vertex == null || v.compareTo(vertex) < 0) {
    116                vertex = v;
    117            }
    118        }
    119        if (colorsUsedSoFar != null) {
    120            for (int color: new TreeSet<Integer>(colorsUsedSoFar))
    121                if (vertex.colorize(assignment, color) && backTrack(solution, 1 + index, colorsUsedSoFar, vertices)) return true;
    122            for (int color: vertex.domain()) {
    123                if (colorsUsedSoFar.contains(color)) continue;
    124                if (vertex.colorize(assignment, color)) {
    125                    colorsUsedSoFar.add(color);
    126                    if (backTrack(solution, 1 + index, colorsUsedSoFar, vertices)) return true;
    127                    colorsUsedSoFar.remove(color);
    128                }
    129                break;
    130            }
    131        } else {
    132            for (int color: vertex.domain())
    133                if (vertex.colorize(assignment, color) && backTrack(solution, 1 + index, colorsUsedSoFar, vertices)) return true;
    134        }
    135        vertex.colorize(assignment, -1);
    136        return false;
    137    }
    138
    139    @Override
    140    public void init(Solver<Exam, ExamPlacement> solver) {
    141        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    142        iSolver = solver;
    143    }
    144
    145    public Set<ExamRoomPlacement> findRooms(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period) {
    146        Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(assignment, period);
    147        if (rooms != null) return rooms;
    148
    149        rooms = new HashSet<ExamRoomPlacement>();
    150        int size = 0;
    151        while (size < exam.getSize()) {
    152            ExamRoomPlacement bestRoom = null; int bestSize = 0;
    153            for (ExamRoomPlacement r: exam.getRoomPlacements()) {
    154                if (!r.isAvailable(period.getPeriod())) continue;
    155                if (rooms.contains(r)) continue;
    156                if (!r.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) continue;
    157                int s = r.getSize(exam.hasAltSeating());
    158                if (bestRoom == null || s > bestSize) {
    159                    bestRoom = r;
    160                    bestSize = s;
    161                }
    162            }
    163            if (bestRoom == null) return rooms;
    164            rooms.add(bestRoom); size += bestSize;
    165        }
    166
    167        return rooms;
    168    }
    169
    170    @Override
    171    public Neighbour<Exam, ExamPlacement> selectNeighbour(final Solution<Exam, ExamPlacement> solution) {
    172        ExamModel model = (ExamModel)solution.getModel();
    173        // if (!model.assignedVariables().isEmpty()) return null;
    174        final HashMap<Exam, Vertex> vertices = new HashMap<Exam, Vertex>();
    175        for (Exam x: model.variables()) {
    176            vertices.put(x, new Vertex(x));
    177        }
    178        for (ExamStudent s: model.getStudents()) {
    179            for (Exam x: s.variables()) {
    180                for (Exam y: s.variables()) {
    181                    if (!x.equals(y)) {
    182                        vertices.get(x).neighbors().add(vertices.get(y));
    183                        vertices.get(y).neighbors().add(vertices.get(x));
    184                    }
    185                }
    186            }
    187        }
    188        for (ExamInstructor i: model.getInstructors()) {
    189            for (Exam x: i.variables()) {
    190                for (Exam y: i.variables()) {
    191                    if (!x.equals(y)) {
    192                        vertices.get(x).neighbors().add(vertices.get(y));
    193                        vertices.get(y).neighbors().add(vertices.get(x));
    194                    }
    195                }
    196            }
    197        }
    198        iProgress.setPhase("Graph coloring-based construction", vertices.size());
    199        iProgress.info("Looking for a conflict-free assignment using " + model.getPeriods().size() + " periods.");
    200        iT0 = JProf.currentTimeSec(); iTimeLimitReached = false;
    201        if (iMode.isGreedy()) {
    202            iProgress.info("Using greedy heuristics only (no backtracking)...");
    203        } else if (backTrack(solution, 0, (iMode.isRedundant() ? null : new HashSet<Integer>()), vertices.values())) {
    204            iProgress.info("Success!");
    205        } else if (iTimeLimitReached) {
    206            iProgress.info("There was no conflict-free schedule found during the given time.");
    207        } else if (iSolver.isStop()) {
    208            iProgress.info("Solver was stopped.");
    209        } else {
    210            if (iMode.isRedundant())
    211                iProgress.info("There is no conflict-free schedule!");
    212            else
    213                iProgress.info("Conflict-free schedule not found.");
    214        }
    215        if (iMode.isConstraintCheck())
    216            solution.restoreBest();
    217        HashSet<Vertex> remaning = new HashSet<Vertex>();
    218        for (Vertex v: vertices.values())
    219            if (v.color() < 0) remaning.add(v);
    220        remaining: while (!remaning.isEmpty()) {
    221            Vertex vertex = null;
    222            for (Vertex v: remaning)
    223                if (vertex == null || v.compareTo(vertex) < 0)
    224                    vertex = v;
    225            remaning.remove(vertex);
    226            for (int color: vertex.domain())
    227                if (vertex.colorize(solution.getAssignment(), color)) continue remaining;
    228        }
    229        if (!iMode.isConstraintCheck()) {
    230            return new Neighbour<Exam, ExamPlacement>() {
    231                @Override
    232                public void assign(Assignment<Exam, ExamPlacement> assignment, long iteration) {
    233                    iProgress.info("Using graph coloring solution ...");
    234                    for (Vertex vertex: new TreeSet<Vertex>(vertices.values())) {
    235                        ExamPeriodPlacement period = vertex.period();
    236                        if (period == null || !vertex.exam().checkDistributionConstraints(assignment, period)) continue;
    237                        Set<ExamRoomPlacement> rooms = findRooms(assignment, vertex.exam(), period);
    238                        if (rooms == null) continue;
    239                        assignment.assign(iteration, new ExamPlacement(vertex.exam(), period, rooms));
    240                    }
    241                    HashSet<Vertex> unassigned = new HashSet<Vertex>();
    242                    for (Vertex vertex: vertices.values()) {
    243                        if (assignment.getValue(vertex.exam()) == null) {
    244                            unassigned.add(vertex);
    245                            vertex.colorize(assignment, -1);
    246                        }
    247                    }
    248                    solution.saveBest();
    249                    iProgress.info("Extending ...");
    250                    unassigned: while (!unassigned.isEmpty()) {
    251                        Vertex vertex = null;
    252                        for (Vertex v: unassigned)
    253                            if (vertex == null || v.compareTo(vertex) < 0)
    254                                vertex = v;
    255                        unassigned.remove(vertex);
    256                        for (int color: vertex.domain()) {
    257                            if (!vertex.colorize(assignment, color)) continue;
    258                            ExamPeriodPlacement period = vertex.period(color);
    259                            if (period == null || !vertex.exam().checkDistributionConstraints(assignment, period)) continue;
    260                            Set<ExamRoomPlacement> rooms = findRooms(assignment, vertex.exam(), period);
    261                            if (rooms == null) continue;
    262                            assignment.assign(iteration, new ExamPlacement(vertex.exam(), period, rooms));
    263                            continue unassigned;
    264                        }
    265                        vertex.colorize(assignment, -1);
    266                    }
    267                    solution.saveBest();
    268                    iProgress.info("Construction done.");
    269                }
    270                @Override
    271                public double value(Assignment<Exam, ExamPlacement> assignment) {
    272                    return 0;
    273                }
    274                @Override
    275                public Map<Exam, ExamPlacement> assignments() {
    276                    throw new UnsupportedOperationException();
    277                }
    278            };
    279        }
    280        return null;
    281    }
    282
    283    /** Internal graph representation -- needed for domain caching */
    284    private class Vertex implements Comparable<Vertex> {
    285        private Exam iExam;
    286        private List<Vertex> iNeighbors = new ArrayList<Vertex>();
    287        private int iColor = -1;
    288        private HashMap<Integer, ExamPeriodPlacement> iDomain = new HashMap<Integer, ExamPeriodPlacement>();
    289        private HashMap<Integer, Vertex> iTaken = new HashMap<Integer, Vertex>();
    290
    291        public Vertex(Exam exam) {
    292            iExam = exam;
    293            for (ExamPeriodPlacement period: exam.getPeriodPlacements())
    294                iDomain.put(period.getIndex(), period);
    295        }
    296
    297        public List<Vertex> neighbors() { return iNeighbors; }
    298
    299        public Set<Integer> domain() { return iDomain.keySet(); }
    300
    301        public ExamPeriodPlacement period() { return (iColor < 0 ? null : iDomain.get(iColor)); }
    302
    303        public ExamPeriodPlacement period(int color) { return (color < 0 ? null : iDomain.get(color)); }
    304
    305        private boolean neighborColored(Vertex v, int color) {
    306            if (!iDomain.containsKey(color)) return true;
    307            if (iTaken.get(color) == null)
    308                iTaken.put(color, v);
    309            return iTaken.size() < iDomain.size();
    310        }
    311
    312        private void neighborUncolored(Vertex v, int color) {
    313            if (!iDomain.containsKey(color)) return;
    314            if (v.equals(iTaken.get(color))) {
    315                for (Vertex w: neighbors()) {
    316                    if (w.equals(v)) continue;
    317                    if (w.color() == color) {
    318                        iTaken.put(color, w);
    319                        return;
    320                    }
    321                }
    322                iTaken.remove(color);
    323            }
    324        }
    325
    326        public int color() { return iColor; }
    327
    328        public boolean colorize(Assignment<Exam, ExamPlacement> assignment, int color) {
    329            if (iColor == color) return true;
    330            ExamPlacement placement = null;
    331            if (color >= 0) {
    332                if (iTaken.get(color) != null || !iDomain.containsKey(color))
    333                    return false;
    334                if (iMode.isConstraintCheck()) {
    335                    ExamPeriodPlacement period = iDomain.get(color);
    336                    if (!iExam.checkDistributionConstraints(assignment, period)) return false;
    337                    Set<ExamRoomPlacement> rooms = findRooms(assignment, iExam, period);
    338                    if (rooms == null) return false;
    339                    placement = new ExamPlacement(iExam, period, rooms);
    340                }
    341            }
    342            if (iColor >= 0) {
    343                for (Vertex v: neighbors())
    344                    v.neighborUncolored(this, iColor);
    345            }
    346            boolean success = true;
    347            if (color >= 0) {
    348                for (Vertex v: neighbors()) {
    349                    if (!v.neighborColored(this, color)) {
    350                        success = false; break;
    351                    }
    352                }
    353            }
    354            if (success) {
    355                iColor = color;
    356                if (iMode.isConstraintCheck()) {
    357                    if (placement != null)
    358                        assignment.assign(0l, placement);
    359                    else
    360                        assignment.unassign(0l, iExam);
    361                }
    362            } else { // undo
    363                for (Vertex v: neighbors()) {
    364                    v.neighborUncolored(this, color);
    365                    if (iColor >= 0)
    366                        v.neighborColored(this, iColor);
    367                }
    368            }
    369            return success;
    370        }
    371
    372        public int degree() {
    373            return iNeighbors.size();
    374        }
    375
    376        public int available() {
    377            return iDomain.size() - iTaken.size();
    378        }
    379
    380        public int degreeNotColored() {
    381            int ret = 0;
    382            for (Vertex v: neighbors())
    383                if (v.color() < 0) ret ++;
    384            return ret;
    385        }
    386
    387        public Exam exam() { return iExam; }
    388
    389        @Override
    390        public int compareTo(Vertex v) {
    391            if (available() < v.available()) return -1;
    392            if (v.available() < available()) return 1;
    393            if (degree() > v.degree()) return -1;
    394            if (v.degree() > degree()) return 1;
    395            if (degreeNotColored() > v.degreeNotColored()) return -1;
    396            if (v.degreeNotColored() > degreeNotColored()) return 1;
    397            return Double.compare(exam().getId(), v.exam().getId());
    398        }
    399    }
    400}