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 Tomáš Müller<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 if (iLastWorkDay < iFirstWorkDay) iLastWorkDay += 7; 063 } 064 065 @Override 066 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) { 067 MinimizeNumberOfUsedRoomsConstraintContext context = getContext(assignment); 068 int overLimit = context.getOverLimit(assignment, placement); 069 if (overLimit > 0) { 070 List<List<Placement>> adepts = new ArrayList<List<Placement>>(); 071 for (Set<Lecture> lects: context.getUsedRooms().values()) { 072 List<Placement> placementsToUnassign = new ArrayList<Placement>(); 073 boolean canUnassign = true; 074 for (Lecture l : lects) { 075 if (l.isCommitted()) { 076 canUnassign = false; 077 break; 078 } 079 Placement p = assignment.getValue(l); 080 if (!conflicts.contains(p)) 081 placementsToUnassign.add(p); 082 } 083 if (!canUnassign) 084 continue; 085 adepts.add(placementsToUnassign); 086 } 087 if (adepts.size() < overLimit) { 088 conflicts.add(placement); 089 } else { 090 Collections.sort(adepts, new Comparator<List<Placement>>() { 091 @Override 092 public int compare(List<Placement> c1, List<Placement> c2) { 093 return Double.compare(c1.size(), c2.size()); 094 } 095 }); 096 for (int i = 0; i < overLimit; i++) { 097 conflicts.addAll(adepts.get(i)); 098 } 099 } 100 } 101 } 102 103 @Override 104 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) { 105 return getContext(assignment).isOverLimit(assignment, placement); 106 } 107 108 @Override 109 public String getName() { 110 return "Minimize number of used rooms"; 111 } 112 113 public int estimateLimit() { 114 HashSet<RoomLocation> mandatoryRooms = new HashSet<RoomLocation>(); 115 for (Lecture lecture : variables()) { 116 if (lecture.getNrRooms() == 0) 117 continue; 118 if (lecture.isCommitted() || lecture.roomLocations().size() == 1) 119 mandatoryRooms.addAll(lecture.roomLocations()); 120 } 121 double histogram[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 122 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 123 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 124 histogram[i][j] = 0.0; 125 for (Lecture lecture : variables()) { 126 if (lecture.getNrRooms() == 0) 127 continue; 128 List<Placement> values = lecture.values(null); 129 for (Placement p : lecture.values(null)) { 130 int firstSlot = p.getTimeLocation().getStartSlot(); 131 if (firstSlot > iLastDaySlot) 132 continue; 133 int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1; 134 if (endSlot < iFirstDaySlot) 135 continue; 136 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 137 int dayCode = p.getTimeLocation().getDayCode(); 138 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 139 if ((dayCode & Constants.DAY_CODES[j%7]) != 0) { 140 histogram[i - iFirstDaySlot][j - iFirstWorkDay] += ((double) lecture.getNrRooms()) / values.size(); 141 } 142 } 143 } 144 } 145 } 146 int maxAverageRooms = 0; 147 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 148 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 149 maxAverageRooms = Math.max(maxAverageRooms, (int) Math.ceil(histogram[i][j])); 150 return Math.max(1, Math.max(mandatoryRooms.size(), maxAverageRooms)); 151 } 152 153 @Override 154 public String toString() { 155 StringBuffer sb = new StringBuffer(); 156 sb.append("Minimize Number Of Rooms Used between "); 157 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 158 Lecture v = e.next(); 159 sb.append(v.getName()); 160 if (e.hasNext()) 161 sb.append(", "); 162 } 163 return sb.toString(); 164 } 165 166 @Override 167 public void weaken(Assignment<Lecture, Placement> assignment) { 168 if (iUnassignmentsToWeaken > 0) 169 getContext(assignment).weaken(); 170 } 171 172 @Override 173 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 174 getContext(assignment).weaken(assignment, value); 175 } 176 177 @Override 178 public MinimizeNumberOfUsedRoomsConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 179 return new MinimizeNumberOfUsedRoomsConstraintContext(assignment); 180 } 181 182 public class MinimizeNumberOfUsedRoomsConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 183 private long iUnassignment = 0; 184 private int iLimit = 1; 185 private Map<RoomLocation, Set<Lecture>> iUsedRooms = new HashMap<RoomLocation, Set<Lecture>>(); 186 187 public MinimizeNumberOfUsedRoomsConstraintContext(Assignment<Lecture, Placement> assignment) { 188 for (Lecture lecture: variables()) { 189 Placement placement = assignment.getValue(lecture); 190 if (placement != null) 191 assigned(assignment, placement); 192 } 193 iLimit = Math.max(iUsedRooms.size(), estimateLimit()); 194 } 195 196 @Override 197 public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) { 198 Lecture lecture = placement.variable(); 199 if (lecture.getNrRooms() <= 0) 200 return; 201 if (placement.isMultiRoom()) { 202 for (RoomLocation r : placement.getRoomLocations()) { 203 Set<Lecture> lects = iUsedRooms.get(r); 204 if (lects == null) { 205 lects = new HashSet<Lecture>(); 206 iUsedRooms.put(r, lects); 207 } 208 lects.add(lecture); 209 } 210 } else { 211 RoomLocation r = placement.getRoomLocation(); 212 Set<Lecture> lects = iUsedRooms.get(r); 213 if (lects == null) { 214 lects = new HashSet<Lecture>(); 215 iUsedRooms.put(r, lects); 216 } 217 lects.add(lecture); 218 } 219 } 220 221 @Override 222 public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) { 223 Lecture lecture = placement.variable(); 224 if (lecture.getNrRooms() <= 0) 225 return; 226 if (placement.isMultiRoom()) { 227 for (RoomLocation r : placement.getRoomLocations()) { 228 Set<Lecture> lects = iUsedRooms.get(r); 229 if (lects != null) { 230 lects.remove(lecture); 231 if (lects.isEmpty()) 232 iUsedRooms.remove(r); 233 } 234 } 235 } else { 236 RoomLocation r = placement.getRoomLocation(); 237 Set<Lecture> lects = iUsedRooms.get(r); 238 if (lects != null) { 239 lects.remove(lecture); 240 if (lects.isEmpty()) 241 iUsedRooms.remove(r); 242 } 243 } 244 } 245 246 public boolean isOverLimit(Assignment<Lecture, Placement> assignment, Placement placement) { 247 return getOverLimit(assignment, placement) > 0; 248 } 249 250 public int getOverLimit(Assignment<Lecture, Placement> assignment, Placement placement) { 251 if (iUnassignmentsToWeaken == 0) 252 return 0; // not working 253 254 Lecture lecture = placement.variable(); 255 256 if (lecture.getNrRooms() <= 0) 257 return 0; // no room 258 if (lecture.roomLocations().size() == lecture.getNrRooms()) 259 return 0; // required room 260 if (lecture.isCommitted()) 261 return 0; // commited class 262 263 Placement current = assignment.getValue(lecture); 264 265 int usage = iUsedRooms.size(); 266 if (usage + lecture.getNrRooms() <= iLimit) 267 return 0; // under the limit, quick check 268 269 if (placement.isMultiRoom()) { 270 HashSet<RoomLocation> assignedRooms = new HashSet<RoomLocation>(); 271 if (current != null) 272 assignedRooms.addAll(current.getRoomLocations()); 273 for (RoomLocation r : placement.getRoomLocations()) { 274 if (assignedRooms.remove(r)) 275 continue; 276 if (!iUsedRooms.containsKey(r)) 277 usage++; 278 } 279 for (RoomLocation r : assignedRooms) { 280 Set<Lecture> lects = iUsedRooms.get(r); 281 if (lects != null && lects.size() == 1) 282 usage--; 283 } 284 } else { 285 RoomLocation assignedRoom = (current != null && !current.equals(placement) ? current.getRoomLocation() : null); 286 RoomLocation room = placement.getRoomLocation(); 287 if (!room.equals(assignedRoom)) { 288 if (!iUsedRooms.containsKey(room)) 289 usage++; 290 if (assignedRoom != null) { 291 Set<Lecture> lects = iUsedRooms.get(assignedRoom); 292 if (lects != null && lects.size() == 1) 293 usage--; 294 } 295 } 296 } 297 if (usage <= iUsedRooms.size()) 298 return 0; // number of used rooms not changed 299 if (usage <= iLimit) 300 return 0; // under the limit 301 return usage - iLimit; 302 } 303 304 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 305 if (isOverLimit(assignment, value)) 306 iLimit += getOverLimit(assignment, value); 307 } 308 309 public void weaken() { 310 iUnassignment++; 311 if (iUnassignmentsToWeaken > 0 && iUnassignment % iUnassignmentsToWeaken == 0) 312 iLimit++; 313 } 314 315 public Map<RoomLocation, Set<Lecture>> getUsedRooms() { 316 return iUsedRooms; 317 } 318 } 319 320}