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