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