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