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 }