001    package net.sf.cpsolver.exam.heuristics;
002    
003    import java.util.HashSet;
004    import java.util.Set;
005    
006    import net.sf.cpsolver.exam.model.Exam;
007    import net.sf.cpsolver.exam.model.ExamModel;
008    import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
009    import net.sf.cpsolver.exam.model.ExamPlacement;
010    import net.sf.cpsolver.exam.model.ExamRoomPlacement;
011    import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
012    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
013    import net.sf.cpsolver.ifs.model.Neighbour;
014    import net.sf.cpsolver.ifs.solution.Solution;
015    import net.sf.cpsolver.ifs.solver.Solver;
016    import net.sf.cpsolver.ifs.util.DataProperties;
017    import 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 Tomas Muller<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     */
059    public 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    }