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