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    }