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