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