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