001package net.sf.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.Set;
011
012import net.sf.cpsolver.coursett.Constants;
013import net.sf.cpsolver.coursett.model.Lecture;
014import net.sf.cpsolver.coursett.model.Placement;
015import net.sf.cpsolver.coursett.model.RoomLocation;
016import net.sf.cpsolver.ifs.model.Constraint;
017import net.sf.cpsolver.ifs.model.WeakeningConstraint;
018import 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 Tomáš Müller<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
048public 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}