001package net.sf.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.Collections; 005import java.util.Comparator; 006import java.util.HashSet; 007import java.util.HashMap; 008import java.util.Iterator; 009import java.util.List; 010import java.util.Set; 011 012import net.sf.cpsolver.coursett.Constants; 013import net.sf.cpsolver.coursett.model.Lecture; 014import net.sf.cpsolver.coursett.model.Placement; 015import net.sf.cpsolver.coursett.model.RoomLocation; 016import net.sf.cpsolver.ifs.model.Constraint; 017import net.sf.cpsolver.ifs.model.WeakeningConstraint; 018import 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 Tomáš Müller<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 048public 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}