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