001 package net.sf.cpsolver.coursett.constraint;
002
003 import java.util.ArrayList;
004 import java.util.Collections;
005 import java.util.Comparator;
006 import java.util.HashSet;
007 import java.util.HashMap;
008 import java.util.Iterator;
009 import java.util.List;
010 import java.util.Set;
011
012 import net.sf.cpsolver.coursett.Constants;
013 import net.sf.cpsolver.coursett.model.Lecture;
014 import net.sf.cpsolver.coursett.model.Placement;
015 import net.sf.cpsolver.coursett.model.RoomLocation;
016 import net.sf.cpsolver.ifs.model.Constraint;
017 import net.sf.cpsolver.ifs.model.WeakeningConstraint;
018 import net.sf.cpsolver.ifs.util.DataProperties;
019
020 /**
021 * Minimize number of used rooms within the set of classes. <br>
022 * <br>
023 * This constraint implements the following distribution/group constraint: <br>
024 * <br>
025 * MIN_ROOM_USE (Minimize Number Of Rooms Used)<br>
026 * Minimize number of rooms used by the given set of classes.
027 *
028 * @version CourseTT 1.2 (University Course Timetabling)<br>
029 * Copyright (C) 2006 - 2010 Tomas Muller<br>
030 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
031 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
032 * <br>
033 * This library is free software; you can redistribute it and/or modify
034 * it under the terms of the GNU Lesser General Public License as
035 * published by the Free Software Foundation; either version 3 of the
036 * License, or (at your option) any later version. <br>
037 * <br>
038 * This library is distributed in the hope that it will be useful, but
039 * WITHOUT ANY WARRANTY; without even the implied warranty of
040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
041 * Lesser General Public License for more details. <br>
042 * <br>
043 * You should have received a copy of the GNU Lesser General Public
044 * License along with this library; if not see
045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
046 */
047
048 public class MinimizeNumberOfUsedRoomsConstraint extends Constraint<Lecture, Placement> implements WeakeningConstraint<Lecture, Placement> {
049 private int iUnassignmentsToWeaken = 250;
050 private long iUnassignment = 0;
051 private int iLimit = 1;
052 private HashMap<RoomLocation, Set<Lecture>> iUsedRooms = new HashMap<RoomLocation, Set<Lecture>>();
053 boolean iEnabled = false;
054
055 public MinimizeNumberOfUsedRoomsConstraint(DataProperties config) {
056 iUnassignmentsToWeaken = config.getPropertyInt("MinimizeNumberOfUsedRooms.Unassignments2Weaken",
057 iUnassignmentsToWeaken);
058 }
059
060 public boolean isOverLimit(Placement placement) {
061 return getOverLimit(placement) > 0;
062 }
063
064 public int getOverLimit(Placement placement) {
065 if (!iEnabled)
066 return 0; // not enabled
067 if (iUnassignmentsToWeaken == 0)
068 return 0; // not working
069
070 Lecture lecture = placement.variable();
071
072 if (lecture.getNrRooms() <= 0)
073 return 0; // no room
074 if (lecture.roomLocations().size() == lecture.getNrRooms())
075 return 0; // required room
076 if (lecture.isCommitted())
077 return 0; // commited class
078
079 int usage = iUsedRooms.size();
080 if (usage + lecture.getNrRooms() <= iLimit)
081 return 0; // under the limit, quick check
082
083 if (placement.isMultiRoom()) {
084 HashSet<RoomLocation> assignedRooms = new HashSet<RoomLocation>();
085 if (lecture.getAssignment() != null)
086 assignedRooms.addAll(lecture.getAssignment().getRoomLocations());
087 for (RoomLocation r : placement.getRoomLocations()) {
088 if (assignedRooms.remove(r))
089 continue;
090 if (!iUsedRooms.containsKey(r))
091 usage++;
092 }
093 for (RoomLocation r : assignedRooms) {
094 Set<Lecture> lects = iUsedRooms.get(r);
095 if (lects != null && lects.size() == 1)
096 usage--;
097 }
098 } else {
099 RoomLocation assignedRoom = (lecture.getAssignment() != null && !lecture.getAssignment().equals(placement) ? lecture
100 .getAssignment().getRoomLocation()
101 : null);
102 RoomLocation room = placement.getRoomLocation();
103 if (!room.equals(assignedRoom)) {
104 if (!iUsedRooms.containsKey(room))
105 usage++;
106 if (assignedRoom != null) {
107 Set<Lecture> lects = iUsedRooms.get(assignedRoom);
108 if (lects != null && lects.size() == 1)
109 usage--;
110 }
111 }
112 }
113 if (usage <= iUsedRooms.size())
114 return 0; // number of used rooms not changed
115 if (usage <= iLimit)
116 return 0; // under the limit
117 return usage - iLimit;
118 }
119
120 @Override
121 public void computeConflicts(Placement placement, Set<Placement> conflicts) {
122 int overLimit = getOverLimit(placement);
123 if (overLimit > 0) {
124 List<List<Placement>> adepts = new ArrayList<List<Placement>>();
125 for (Set<Lecture> lects: iUsedRooms.values()) {
126 List<Placement> placementsToUnassign = new ArrayList<Placement>();
127 boolean canUnassign = true;
128 for (Lecture l : lects) {
129 if (l.isCommitted()) {
130 canUnassign = false;
131 break;
132 }
133 if (!conflicts.contains(l.getAssignment()))
134 placementsToUnassign.add(l.getAssignment());
135 }
136 if (!canUnassign)
137 continue;
138 adepts.add(placementsToUnassign);
139 }
140 if (adepts.size() < overLimit) {
141 conflicts.add(placement);
142 } else {
143 Collections.sort(adepts, new Comparator<List<Placement>>() {
144 @Override
145 public int compare(List<Placement> c1, List<Placement> c2) {
146 return Double.compare(c1.size(), c2.size());
147 }
148 });
149 for (int i = 0; i < overLimit; i++) {
150 conflicts.addAll(adepts.get(i));
151 }
152 }
153 }
154 }
155
156 @Override
157 public boolean inConflict(Placement placeement) {
158 return isOverLimit(placeement);
159 }
160
161 @Override
162 public boolean isConsistent(Placement value1, Placement value2) {
163 return (isOverLimit(value1) || isOverLimit(value2));
164 }
165
166 @Override
167 public void assigned(long iteration, Placement placement) {
168 super.assigned(iteration, placement);
169 Lecture lecture = placement.variable();
170 if (lecture.getNrRooms() <= 0)
171 return;
172 if (placement.isMultiRoom()) {
173 for (RoomLocation r : placement.getRoomLocations()) {
174 Set<Lecture> lects = iUsedRooms.get(r);
175 if (lects == null) {
176 lects = new HashSet<Lecture>();
177 iUsedRooms.put(r, lects);
178 }
179 lects.add(lecture);
180 }
181 } else {
182 RoomLocation r = placement.getRoomLocation();
183 Set<Lecture> lects = iUsedRooms.get(r);
184 if (lects == null) {
185 lects = new HashSet<Lecture>();
186 iUsedRooms.put(r, lects);
187 }
188 lects.add(lecture);
189 }
190 }
191
192 @Override
193 public void unassigned(long iteration, Placement placement) {
194 super.unassigned(iteration, placement);
195 Lecture lecture = placement.variable();
196 if (lecture.getNrRooms() <= 0)
197 return;
198 if (placement.isMultiRoom()) {
199 for (RoomLocation r : placement.getRoomLocations()) {
200 Set<Lecture> lects = iUsedRooms.get(r);
201 if (lects != null) {
202 lects.remove(lecture);
203 if (lects.isEmpty())
204 iUsedRooms.remove(r);
205 }
206 }
207 } else {
208 RoomLocation r = placement.getRoomLocation();
209 Set<Lecture> lects = iUsedRooms.get(r);
210 if (lects != null) {
211 lects.remove(lecture);
212 if (lects.isEmpty())
213 iUsedRooms.remove(r);
214 }
215 }
216 }
217
218 @Override
219 public void weaken() {
220 iUnassignment++;
221 if (iUnassignmentsToWeaken > 0 && iUnassignment % iUnassignmentsToWeaken == 0)
222 iLimit++;
223 }
224
225 @Override
226 public String getName() {
227 return "Minimize number of used rooms";
228 }
229
230 public int estimateLimit() {
231 HashSet<RoomLocation> mandatoryRooms = new HashSet<RoomLocation>();
232 for (Lecture lecture : variables()) {
233 if (lecture.getNrRooms() == 0)
234 continue;
235 if (lecture.isCommitted() || lecture.roomLocations().size() == 1)
236 mandatoryRooms.addAll(lecture.roomLocations());
237 }
238 double histogram[][] = new double[Constants.SLOTS_PER_DAY][Constants.NR_DAYS_WEEK];
239 for (int i = 0; i < Constants.SLOTS_PER_DAY_NO_EVENINGS; i++)
240 for (int j = 0; j < Constants.NR_DAYS_WEEK; j++)
241 histogram[i][j] = 0.0;
242 for (Lecture lecture : variables()) {
243 if (lecture.getNrRooms() == 0)
244 continue;
245 List<Placement> values = lecture.values();
246 for (Placement p : lecture.values()) {
247 int firstSlot = p.getTimeLocation().getStartSlot();
248 if (firstSlot > Constants.DAY_SLOTS_LAST)
249 continue;
250 int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1;
251 if (endSlot < Constants.DAY_SLOTS_FIRST)
252 continue;
253 for (int i = firstSlot; i <= endSlot; i++) {
254 int dayCode = p.getTimeLocation().getDayCode();
255 for (int j = 0; j < Constants.NR_DAYS_WEEK; j++) {
256 if ((dayCode & Constants.DAY_CODES[j]) != 0) {
257 histogram[i][j] += ((double) lecture.getNrRooms()) / values.size();
258 }
259 }
260 }
261 }
262 }
263 int maxAverageRooms = 0;
264 for (int i = 0; i < Constants.SLOTS_PER_DAY_NO_EVENINGS; i++)
265 for (int j = 0; j < Constants.NR_DAYS_WEEK; j++)
266 maxAverageRooms = Math.max(maxAverageRooms, (int) Math.ceil(histogram[i][j]));
267 return Math.max(1, Math.max(mandatoryRooms.size(), maxAverageRooms));
268 }
269
270 public void setEnabled(boolean enabled) {
271 iEnabled = enabled;
272 iLimit = Math.max(iUsedRooms.size(), estimateLimit());
273 }
274
275 public boolean isEnabled() {
276 return iEnabled;
277 }
278
279 @Override
280 public String toString() {
281 StringBuffer sb = new StringBuffer();
282 sb.append("Minimize Number Of Rooms Used between ");
283 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
284 Lecture v = e.next();
285 sb.append(v.getName());
286 if (e.hasNext())
287 sb.append(", ");
288 }
289 return sb.toString();
290 }
291
292 @Override
293 public void weaken(Placement value) {
294 if (isOverLimit(value))
295 iLimit += getOverLimit(value);
296 }
297 }