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