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