    001package net.sf.cpsolver.exam.heuristics;
    002
    003import java.util.HashSet;
    004import java.util.Set;
    005
    006import net.sf.cpsolver.exam.model.Exam;
    007import net.sf.cpsolver.exam.model.ExamModel;
    008import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
    009import net.sf.cpsolver.exam.model.ExamPlacement;
    010import net.sf.cpsolver.exam.model.ExamRoomPlacement;
    011import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
    012import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    013import net.sf.cpsolver.ifs.model.Neighbour;
    014import net.sf.cpsolver.ifs.solution.Solution;
    015import net.sf.cpsolver.ifs.solver.Solver;
    016import net.sf.cpsolver.ifs.util.DataProperties;
    017import net.sf.cpsolver.ifs.util.Progress;
    018
    019/**
    020 * Initial solution construction heuristics. <br>
    021 * <br>
    022 * While there are exams that are still not assigned:
    023 * <ul>
    024 * <li>The worst unassigned exam is selected (using {@link Exam#compareTo(Exam)})
    025 * <li>The best period that does not break any hard constraint and for which
    026 * there is a room assignment available is selected together with the set the
    027 * best available rooms for the exam in the best period (computed using
    028 * {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)}).
    029 * </ul>
    030 * <br>
    031 * <br>
    032 * If problem property ExamConstruction.CheckLocalOptimality is true, local
    033 * (time) optimality is enforced at the end of this phase. During this
    034 * procedure, for each exam, it tries to change the period of the exam so that
    035 * the time cost is lower (see {@link ExamPlacement#getTimeCost()}), but no hard
    036 * constraint is violated. The problem is considered locally optimal if there is
    037 * no such move. <br>
    038 * <br>
    039 *
    040 * @version ExamTT 1.2 (Examination Timetabling)<br>
    041 *          Copyright (C) 2008 - 2010 Tomáš Müller<br>
    042 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    043 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    044 * <br>
    045 *          This library is free software; you can redistribute it and/or modify
    046 *          it under the terms of the GNU Lesser General Public License as
    047 *          published by the Free Software Foundation; either version 3 of the
    048 *          License, or (at your option) any later version. <br>
    049 * <br>
    050 *          This library is distributed in the hope that it will be useful, but
    051 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    052 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    053 *          Lesser General Public License for more details. <br>
    054 * <br>
    055 *          You should have received a copy of the GNU Lesser General Public
    056 *          License along with this library; if not see
    057 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    058 */
    059public class ExamConstruction implements NeighbourSelection<Exam, ExamPlacement> {
    060    private HashSet<String> iAssignments = new HashSet<String>();
    061    private boolean iCheckLocalOptimality = false;
    062    private HashSet<Exam> iSkip = new HashSet<Exam>();
    063    private Progress iProgress = null;
    064    private boolean iActive;
    065
    066    /**
    067     * Constructor
    068     *
    069     * @param properties
    070     *            problem properties
    071     */
    072    public ExamConstruction(DataProperties properties) {
    073        iCheckLocalOptimality = properties.getPropertyBoolean("ExamConstruction.CheckLocalOptimality",
    074                iCheckLocalOptimality);
    075    }
    076
    077    /**
    078     * Initialization
    079     */
    080    @Override
    081    public void init(Solver<Exam, ExamPlacement> solver) {
    082        iSkip.clear();
    083        solver.setUpdateProgress(false);
    084        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    085        iActive = false;
    086    }
    087
    088    /**
    089     * Find a new assignment of one of the assigned exams that improves the time
    090     * cost {@link ExamPlacement#getTimeCost()} and for which there is a set of
    091     * available rooms {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)}.
    092     * Return null, if there is no such assignment (the problem is considered
    093     * locally optimal).
    094     */
    095    public Neighbour<Exam, ExamPlacement> checkLocalOptimality(ExamModel model) {
    096        if (iCheckLocalOptimality) {
    097            for (Exam exam : model.assignedVariables()) {
    098                ExamPlacement current = exam.getAssignment();
    099                if (current.getTimeCost() <= 0)
    100                    continue;
    101                ExamPlacement best = null;
    102                for (ExamPeriodPlacement period : exam.getPeriodPlacements()) {
    103                    if (exam.countStudentConflicts(period) > 0) {
    104                        if (iAssignments.contains(exam.getId() + ":" + period.getIndex()))
    105                            continue;
    106                    }
    107                    if (!exam.checkDistributionConstraints(period))
    108                        continue;
    109                    ExamPlacement placement = new ExamPlacement(exam, period, null);
    110                    if (best == null || best.getTimeCost() > placement.getTimeCost()) {
    111                        Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period);
    112                        if (rooms != null)
    113                            best = new ExamPlacement(exam, period, rooms);
    114                    }
    115                }
    116                if (best != null && best.getTimeCost() < current.getTimeCost())
    117                    return new ExamSimpleNeighbour(best);
    118            }
    119        }
    120        iActive = false;
    121        return null;
    122    }
    123
    124    /**
    125     * Select a neighbour. While there are exams that are still not assigned:
    126     * <ul>
    127     * <li>The worst unassigned exam is selected (using
    128     * {@link Exam#compareTo(Exam)})
    129     * <li>The best period that does not break any hard constraint and for which
    130     * there is a room assignment available is selected together with the set
    131     * the best available rooms for the exam in the best period (computed using
    132     * {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)}).
    133     * </ul>
    134     * Return null when done (all variables are assigned and the problem is
    135     * locally optimal).
    136     */
    137    @Override
    138    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
    139        ExamModel model = (ExamModel) solution.getModel();
    140        if (!iActive) {
    141            iActive = true;
    142            iProgress.setPhase("Construction ...", model.variables().size());
    143        }
    144        iProgress.setProgress(model.nrAssignedVariables());
    145        if (model.nrUnassignedVariables() <= iSkip.size())
    146            return checkLocalOptimality(model);
    147        Exam bestExam = null;
    148        for (Exam exam : model.unassignedVariables()) {
    149            if (iSkip.contains(exam))
    150                continue;
    151            if (bestExam == null || exam.compareTo(bestExam) < 0)
    152                bestExam = exam;
    153        }
    154        ExamPlacement best = null;
    155        for (ExamPeriodPlacement period : bestExam.getPeriodPlacements()) {
    156            if (bestExam.countStudentConflicts(period) > 0) {
    157                if (iAssignments.contains(bestExam.getId() + ":" + period.getIndex()))
    158                    continue;
    159            }
    160            if (!bestExam.checkDistributionConstraints(period))
    161                continue;
    162            ExamPlacement placement = new ExamPlacement(bestExam, period, null);
    163            if (best == null || best.getTimeCost() > placement.getTimeCost()) {
    164                Set<ExamRoomPlacement> rooms = bestExam.findBestAvailableRooms(period);
    165                if (rooms != null)
    166                    best = new ExamPlacement(bestExam, period, rooms);
    167            }
    168        }
    169        if (best != null) {
    170            iAssignments.add(bestExam.getId() + ":" + best.getPeriod().getIndex());
    171            return new ExamSimpleNeighbour(best);
    172        } /*
    173           * else { for (Enumeration
    174           * e=bestExam.getPeriodPlacements().elements();e.hasMoreElements();) {
    175           * ExamPeriodPlacement period = (ExamPeriodPlacement)e.nextElement();
    176           * ExamPlacement placement = new ExamPlacement(bestExam, period,
    177           * null); if (best==null ||
    178           * best.getTimeCost()>placement.getTimeCost()) { Set rooms =
    179           * bestExam.findBestAvailableRooms(period); if (rooms!=null) best =
    180           * new ExamPlacement(bestExam, period, rooms); } } if (best!=null) {
    181           * bestExam.allowAllStudentConflicts(best.getPeriod());
    182           * iAssignments.add(bestExam.getId()+":"+best.getPeriod().getIndex());
    183           * return new ExamSimpleNeighbour(best); } }
    184           */
    185        if (!iSkip.contains(bestExam)) {
    186            iSkip.add(bestExam);
    187            return selectNeighbour(solution);
    188        }
    189        return checkLocalOptimality(model);
    190    }
    191
    192}