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}