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