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.Iterator;
008    import java.util.List;
009    import java.util.Set;
010    
011    import net.sf.cpsolver.coursett.Constants;
012    import net.sf.cpsolver.coursett.model.Lecture;
013    import net.sf.cpsolver.coursett.model.Placement;
014    import net.sf.cpsolver.coursett.model.TimeLocation;
015    import net.sf.cpsolver.ifs.model.Constraint;
016    import net.sf.cpsolver.ifs.util.DataProperties;
017    
018    /**
019     * Minimize number of used groups of time within a set of classes. <br>
020     * <br>
021     * 
022     * This constraint implements the following distribution/group constraints: <br>
023     * <br>
024     * 
025     * MIN_GRUSE(10x1h) (Minimize Use Of 1h Groups)<br>
026     * Minimize number of groups of time that are used by the given classes. The
027     * time is spread into the following 10 groups of one hour: 7:30a-8:30a,
028     * 8:30a-9:30a, 9:30a-10:30a, ... 4:30p-5:30p. <br>
029     * <br>
030     * 
031     * MIN_GRUSE(5x2h) (Minimize Use Of 2h Groups)<br>
032     * Minimize number of groups of time that are used by the given classes. The
033     * time is spread into the following 5 groups of two hours: 7:30a-9:30a,
034     * 9:30a-11:30a, 11:30a-1:30p, 1:30p-3:30p, 3:30p-5:30p. <br>
035     * <br>
036     * 
037     * MIN_GRUSE(3x3h) (Minimize Use Of 3h Groups)<br>
038     * Minimize number of groups of time that are used by the given classes. The
039     * time is spread into the following 3 groups: 7:30a-10:30a, 10:30a-2:30p,
040     * 2:30p-5:30p. <br>
041     * <br>
042     * 
043     * MIN_GRUSE(2x5h) (Minimize Use Of 5h Groups)<br>
044     * Minimize number of groups of time that are used by the given classes. The
045     * time is spread into the following 2 groups: 7:30a-12:30a, 12:30a-5:30p.
046     * 
047     * @version CourseTT 1.2 (University Course Timetabling)<br>
048     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
049     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
050     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
051     * <br>
052     *          This library is free software; you can redistribute it and/or modify
053     *          it under the terms of the GNU Lesser General Public License as
054     *          published by the Free Software Foundation; either version 3 of the
055     *          License, or (at your option) any later version. <br>
056     * <br>
057     *          This library is distributed in the hope that it will be useful, but
058     *          WITHOUT ANY WARRANTY; without even the implied warranty of
059     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
060     *          Lesser General Public License for more details. <br>
061     * <br>
062     *          You should have received a copy of the GNU Lesser General Public
063     *          License along with this library; if not see
064     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
065     */
066    
067    public class MinimizeNumberOfUsedGroupsOfTime extends Constraint<Lecture, Placement> implements WeakeningConstraint {
068        private int iUnassignmentsToWeaken = 250;
069        private long iUnassignment = 0;
070        private int iLimit = 1;
071        private GroupOfTime iGroupsOfTime[];
072        private HashSet<Placement> iUsage[];
073        private boolean iEnabled = false;
074    
075        private String iName = null;
076    
077        public static GroupOfTime[] sGroups2of5h = new GroupOfTime[] {
078                new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(12, 30), Constants.DAY_CODE_ALL),
079                new GroupOfTime(Constants.time2slot(12, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL), };
080        public static GroupOfTime[] sGroups3of3h = new GroupOfTime[] {
081                new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(10, 30), Constants.DAY_CODE_ALL),
082                new GroupOfTime(Constants.time2slot(10, 30), Constants.time2slot(14, 30), Constants.DAY_CODE_ALL),
083                new GroupOfTime(Constants.time2slot(14, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) };
084        public static GroupOfTime[] sGroups5of2h = new GroupOfTime[] {
085                new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(9, 30), Constants.DAY_CODE_ALL),
086                new GroupOfTime(Constants.time2slot(9, 30), Constants.time2slot(11, 30), Constants.DAY_CODE_ALL),
087                new GroupOfTime(Constants.time2slot(11, 30), Constants.time2slot(13, 30), Constants.DAY_CODE_ALL),
088                new GroupOfTime(Constants.time2slot(13, 30), Constants.time2slot(15, 30), Constants.DAY_CODE_ALL),
089                new GroupOfTime(Constants.time2slot(15, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) };
090        public static GroupOfTime[] sGroups10of1h = new GroupOfTime[] {
091                new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(8, 30), Constants.DAY_CODE_ALL),
092                new GroupOfTime(Constants.time2slot(8, 30), Constants.time2slot(9, 30), Constants.DAY_CODE_ALL),
093                new GroupOfTime(Constants.time2slot(9, 30), Constants.time2slot(10, 30), Constants.DAY_CODE_ALL),
094                new GroupOfTime(Constants.time2slot(10, 30), Constants.time2slot(11, 30), Constants.DAY_CODE_ALL),
095                new GroupOfTime(Constants.time2slot(11, 30), Constants.time2slot(12, 30), Constants.DAY_CODE_ALL),
096                new GroupOfTime(Constants.time2slot(12, 30), Constants.time2slot(13, 30), Constants.DAY_CODE_ALL),
097                new GroupOfTime(Constants.time2slot(13, 30), Constants.time2slot(14, 30), Constants.DAY_CODE_ALL),
098                new GroupOfTime(Constants.time2slot(14, 30), Constants.time2slot(15, 30), Constants.DAY_CODE_ALL),
099                new GroupOfTime(Constants.time2slot(15, 30), Constants.time2slot(16, 30), Constants.DAY_CODE_ALL),
100                new GroupOfTime(Constants.time2slot(16, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) };
101    
102        @SuppressWarnings("unchecked")
103        public MinimizeNumberOfUsedGroupsOfTime(DataProperties config, String name, GroupOfTime[] groupsOfTime) {
104            iGroupsOfTime = groupsOfTime;
105            iUnassignmentsToWeaken = config.getPropertyInt("MinimizeNumberOfUsedGroupsOfTime.Unassignments2Weaken",
106                    iUnassignmentsToWeaken);
107            iName = name;
108            iUsage = new HashSet[iGroupsOfTime.length];
109            for (int i = 0; i < iUsage.length; i++)
110                iUsage[i] = new HashSet<Placement>();
111        }
112    
113        public int currentUsage() {
114            int ret = 0;
115            for (int i = 0; i < iUsage.length; i++)
116                if (!iUsage[i].isEmpty())
117                    ret++;
118            return ret;
119        }
120    
121        @Override
122        public void weaken() {
123            iUnassignment++;
124            if (iUnassignmentsToWeaken > 0 && iUnassignment % iUnassignmentsToWeaken == 0)
125                iLimit++;
126        }
127    
128        public boolean isOverLimit(Placement placement) {
129            return getOverLimit(placement) > 0;
130        }
131    
132        public int getOverLimit(Placement placement) {
133            if (!iEnabled)
134                return 0; // not enabled
135            if (iUnassignmentsToWeaken == 0)
136                return 0; // not working
137    
138            Lecture lecture = placement.variable();
139            TimeLocation time = placement.getTimeLocation();
140    
141            if (lecture.isCommitted())
142                return 0; // commited class
143    
144            int usage = 0;
145            for (int i = 0; i < iGroupsOfTime.length; i++) {
146                GroupOfTime groupOfTime = iGroupsOfTime[i];
147                if (!iUsage[i].isEmpty() || groupOfTime.overlap(time))
148                    usage++;
149            }
150    
151            return usage - iLimit;
152        }
153    
154        public int estimateLimit() {
155            int nrSlotsUsed = 0;
156            int minSlotsUsed = 0;
157            boolean firstLecture = true;
158            for (Lecture lecture : variables()) {
159                boolean first = true;
160                int minSlotsUsedThisLecture = 0;
161                for (TimeLocation time : lecture.timeLocations()) {
162                    int min = 0;
163                    for (int i = 0; i < iGroupsOfTime.length; i++) {
164                        if (iGroupsOfTime[i].overlap(time))
165                            min++;
166                    }
167                    if (first) {
168                        nrSlotsUsed += time.getLength() * time.getNrMeetings();
169                        minSlotsUsedThisLecture = min;
170                        first = false;
171                    } else {
172                        minSlotsUsedThisLecture = Math.min(minSlotsUsedThisLecture, min);
173                    }
174                }
175                if (firstLecture) {
176                    minSlotsUsed = minSlotsUsedThisLecture;
177                    firstLecture = false;
178                } else {
179                    minSlotsUsed = Math.min(minSlotsUsed, minSlotsUsedThisLecture);
180                }
181            }
182            return Math.max(Math.max(1, (int) Math.ceil(((double) nrSlotsUsed) / iGroupsOfTime[0].size())), minSlotsUsed);
183        }
184    
185        @Override
186        public void computeConflicts(Placement placement, Set<Placement> conflicts) {
187            int overLimit = getOverLimit(placement);
188            if (overLimit > 0) {
189                TimeLocation time = placement.getTimeLocation();
190    
191                List<List<Placement>> adepts = new ArrayList<List<Placement>>();
192                for (int i = 0; i < iGroupsOfTime.length; i++) {
193                    GroupOfTime groupOfTime = iGroupsOfTime[i];
194                    HashSet<Placement> usage = iUsage[i];
195                    if (groupOfTime.overlap(time) || usage.isEmpty())
196                        continue;
197                    boolean canUnassign = true;
198                    List<Placement> placementsToUnassign = new ArrayList<Placement>(usage.size());
199                    for (Placement p : usage) {
200                        Lecture l = p.variable();
201                        if (l.isCommitted()) {
202                            canUnassign = false;
203                            break;
204                        }
205                        if (!conflicts.contains(p))
206                            placementsToUnassign.add(p);
207                    }
208                    if (!canUnassign)
209                        continue;
210                    adepts.add(placementsToUnassign);
211                }
212                if (adepts.size() < overLimit) {
213                    conflicts.add(placement);
214                } else {
215                    Collections.sort(adepts, new Comparator<List<Placement>>() {
216                        @Override
217                        public int compare(List<Placement> c1, List<Placement> c2) {
218                            return Double.compare(c1.size(), c2.size());
219                        }
220                    });
221                    for (int i = 0; i < overLimit; i++) {
222                        conflicts.addAll(adepts.get(i));
223                    }
224                }
225            }
226        }
227    
228        @Override
229        public boolean inConflict(Placement placement) {
230            return isOverLimit(placement);
231        }
232    
233        @Override
234        public boolean isConsistent(Placement value1, Placement value2) {
235            return (isOverLimit(value1) || isOverLimit(value2));
236        }
237    
238        @Override
239        public void assigned(long iteration, Placement placement) {
240            super.assigned(iteration, placement);
241            TimeLocation time = placement.getTimeLocation();
242            for (int i = 0; i < iGroupsOfTime.length; i++) {
243                GroupOfTime groupOfTime = iGroupsOfTime[i];
244                HashSet<Placement> usage = iUsage[i];
245                if (groupOfTime.overlap(time))
246                    usage.add(placement);
247            }
248        }
249    
250        @Override
251        public void unassigned(long iteration, Placement placement) {
252            super.unassigned(iteration, placement);
253            TimeLocation time = placement.getTimeLocation();
254            for (int i = 0; i < iGroupsOfTime.length; i++) {
255                GroupOfTime groupOfTime = iGroupsOfTime[i];
256                HashSet<Placement> usage = iUsage[i];
257                if (groupOfTime.overlap(time))
258                    usage.remove(placement);
259            }
260        }
261    
262        public String getConstraintName() {
263            return "MIN_GRUSE(" + iName + ")";
264        }
265    
266        @Override
267        public String getName() {
268            return "Minimize number of used groups of time (" + iName + ")";
269        }
270    
271        public void setEnabled(boolean enabled) {
272            iEnabled = enabled;
273            iLimit = Math.max(currentUsage(), estimateLimit());
274        }
275    
276        public boolean isEnabled() {
277            return iEnabled;
278        }
279    
280        private static class GroupOfTime {
281            private int iStartSlot = 0;
282            private int iEndSlot = 0;
283            private int iDays = 0;
284    
285            public GroupOfTime(int startSlot, int endSlot, int days) {
286                iStartSlot = startSlot;
287                iEndSlot = endSlot;
288                iDays = days;
289            }
290    
291            public int getStartSlot() {
292                return iStartSlot;
293            }
294    
295            public int getEndSlot() {
296                return iEndSlot;
297            }
298    
299            public int getDays() {
300                return iDays;
301            }
302    
303            public int nrDays() {
304                int ret = 0;
305                for (int i = 0; i < Constants.DAY_CODES.length; i++) {
306                    if ((getDays() & Constants.DAY_CODES[i]) != 0)
307                        ret++;
308                }
309                return ret;
310            }
311    
312            public int size() {
313                return (getEndSlot() - getStartSlot()) * nrDays();
314            }
315    
316            public boolean overlap(TimeLocation timeLocation) {
317                if ((timeLocation.getDayCode() & iDays) == 0)
318                    return false;
319                int end = Math.min(iEndSlot, timeLocation.getStartSlot() + timeLocation.getLength());
320                int start = Math.max(iStartSlot, timeLocation.getStartSlot());
321                int nrSharedSlots = (end < start ? 0 : end - start);
322                return (nrSharedSlots > 0);
323            }
324        }
325    
326        @Override
327        public String toString() {
328            StringBuffer sb = new StringBuffer();
329            sb.append("Minimize Use Of "
330                    + (Constants.SLOT_LENGTH_MIN * (iGroupsOfTime[0].getEndSlot() - iGroupsOfTime[0].getStartSlot()))
331                    + "min Groups between ");
332            for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
333                Lecture v = e.next();
334                sb.append(v.getName());
335                if (e.hasNext())
336                    sb.append(", ");
337            }
338            return sb.toString();
339        }
340    
341        @Override
342        public void weaken(Placement value) {
343            if (isOverLimit(value))
344                iLimit += getOverLimit(value);
345        }
346    
347    }