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.Iterator;
008import java.util.List;
009import java.util.Set;
010
011import net.sf.cpsolver.coursett.Constants;
012import net.sf.cpsolver.coursett.model.Lecture;
013import net.sf.cpsolver.coursett.model.Placement;
014import net.sf.cpsolver.coursett.model.TimeLocation;
015import net.sf.cpsolver.ifs.model.Constraint;
016import net.sf.cpsolver.ifs.model.WeakeningConstraint;
017import 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 Tomáš Müller<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
068public 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}