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}