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