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