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