001 package net.sf.cpsolver.exam.model;
002
003 import java.util.HashSet;
004 import java.util.Iterator;
005 import java.util.Set;
006
007 import net.sf.cpsolver.exam.criteria.DistributionPenalty;
008 import net.sf.cpsolver.ifs.model.Constraint;
009
010 /**
011 * Distribution binary constraint. <br>
012 * <br>
013 * The following binary distribution constraints are implemented
014 * <ul>
015 * <li>Same room
016 * <li>Different room
017 * <li>Same period
018 * <li>Different period
019 * <li>Precedence
020 * </ul>
021 * <br>
022 * <br>
023 *
024 * @version ExamTT 1.2 (Examination Timetabling)<br>
025 * Copyright (C) 2008 - 2010 Tomas Muller<br>
026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028 * <br>
029 * This library is free software; you can redistribute it and/or modify
030 * it under the terms of the GNU Lesser General Public License as
031 * published by the Free Software Foundation; either version 3 of the
032 * License, or (at your option) any later version. <br>
033 * <br>
034 * This library is distributed in the hope that it will be useful, but
035 * WITHOUT ANY WARRANTY; without even the implied warranty of
036 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 * Lesser General Public License for more details. <br>
038 * <br>
039 * You should have received a copy of the GNU Lesser General Public
040 * License along with this library; if not see
041 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042 */
043 public class ExamDistributionConstraint extends Constraint<Exam, ExamPlacement> {
044 /** Same room constraint type */
045 public static final int sDistSameRoom = 0;
046 /** Different room constraint type */
047 public static final int sDistDifferentRoom = 1;
048 /** Same period constraint type */
049 public static final int sDistSamePeriod = 2;
050 /** Different period constraint type */
051 public static final int sDistDifferentPeriod = 3;
052 /** Precedence constraint type */
053 public static final int sDistPrecedence = 4;
054 /** Precedence constraint type (reverse order) */
055 public static final int sDistPrecedenceRev = 5;
056 /** Distribution type name */
057 public static final String[] sDistType = new String[] { "same-room", "different-room", "same-period",
058 "different-period", "precedence", "precedence-rev" };
059
060 private int iType = -1;
061 private boolean iHard = true;
062 private int iWeight = 0;
063
064 /**
065 * Constructor
066 *
067 * @param id
068 * constraint unique id
069 * @param type
070 * constraint type
071 * @param hard
072 * true if the constraint is hard (cannot be violated)
073 * @param weight
074 * if not hard, penalty for violation
075 */
076 public ExamDistributionConstraint(long id, int type, boolean hard, int weight) {
077 iId = id;
078 iType = type;
079 iHard = hard;
080 iWeight = weight;
081 }
082
083 /**
084 * Constructor
085 *
086 * @param id
087 * constraint unique id
088 * @param type
089 * constraint type (EX_SAME_PREF, EX_SAME_ROOM, or EX_PRECEDENCE)
090 * @param pref
091 * preference (R/P for required/prohibited, or -2, -1, 0, 1, 2
092 * for preference (from preferred to discouraged))
093 */
094 public ExamDistributionConstraint(long id, String type, String pref) {
095 iId = id;
096 boolean neg = "P".equals(pref) || "2".equals(pref) || "1".equals(pref);
097 if ("EX_SAME_PER".equals(type)) {
098 iType = (neg ? sDistDifferentPeriod : sDistSamePeriod);
099 } else if ("EX_SAME_ROOM".equals(type)) {
100 iType = (neg ? sDistDifferentRoom : sDistSameRoom);
101 } else if ("EX_PRECEDENCE".equals(type)) {
102 iType = (neg ? sDistPrecedenceRev : sDistPrecedence);
103 } else
104 throw new RuntimeException("Unkown type " + type);
105 if ("P".equals(pref) || "R".equals(pref))
106 iHard = true;
107 else {
108 iHard = false;
109 iWeight = Integer.parseInt(pref) * Integer.parseInt(pref);
110 }
111 }
112
113 /**
114 * Constructor
115 *
116 * @param id
117 * constraint unique id
118 * @param type
119 * constraint type name
120 */
121 public ExamDistributionConstraint(long id, String type, boolean hard, int weight) {
122 iId = id;
123 for (int i = 0; i < sDistType.length; i++)
124 if (sDistType[i].equals(type))
125 iType = i;
126 if (iType < 0)
127 throw new RuntimeException("Unknown type '" + type + "'.");
128 iHard = hard;
129 iWeight = weight;
130 }
131
132 /**
133 * True if hard (must be satisfied), false for soft (should be satisfied)
134 */
135 @Override
136 public boolean isHard() {
137 return iHard;
138 }
139
140 /**
141 * If not hard, penalty for violation
142 */
143 public int getWeight() {
144 return iWeight;
145 }
146
147 /**
148 * Constraint type
149 */
150 public int getType() {
151 return iType;
152 }
153
154 /**
155 * Constraint type name
156 */
157 public String getTypeString() {
158 return sDistType[iType];
159 }
160
161 /**
162 * String representation -- constraint type name (exam 1, exam 2)
163 */
164 @Override
165 public String toString() {
166 return getTypeString() + " (" + variables() + ")";
167 }
168
169 /**
170 * Compute conflicts -- there is a conflict if the other variable is
171 * assigned and
172 * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
173 * false
174 */
175 @Override
176 public void computeConflicts(ExamPlacement givenPlacement, Set<ExamPlacement> conflicts) {
177 boolean before = true;
178 for (Exam exam : variables()) {
179 if (exam.equals(givenPlacement.variable())) {
180 before = false;
181 continue;
182 }
183 ExamPlacement placement = exam.getAssignment();
184 if (placement == null)
185 continue;
186 if (!check(before ? placement : givenPlacement, before ? givenPlacement : placement))
187 conflicts.add(placement);
188 }
189 }
190
191 /**
192 * Check for conflict -- there is a conflict if the other variable is
193 * assigned and
194 * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
195 * false
196 */
197 @Override
198 public boolean inConflict(ExamPlacement givenPlacement) {
199 boolean before = true;
200 for (Exam exam : variables()) {
201 if (exam.equals(givenPlacement.variable())) {
202 before = false;
203 continue;
204 }
205 ExamPlacement placement = exam.getAssignment();
206 if (placement == null)
207 continue;
208 if (!check(before ? placement : givenPlacement, before ? givenPlacement : placement))
209 return true;
210 }
211 return false;
212 }
213
214 /**
215 * Consistency check --
216 * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
217 * called
218 */
219 @Override
220 public boolean isConsistent(ExamPlacement first, ExamPlacement second) {
221 boolean before = (variables().indexOf(first.variable()) < variables().indexOf(second.variable()));
222 return check(before ? first : second, before ? second : first);
223 }
224
225 /**
226 * Check assignments of the given exams
227 *
228 * @param first
229 * assignment of the first exam
230 * @param second
231 * assignment of the second exam
232 * @return true, if the constraint is satisfied
233 */
234 public boolean check(ExamPlacement first, ExamPlacement second) {
235 switch (getType()) {
236 case sDistPrecedence:
237 return first.getPeriod().getIndex() < second.getPeriod().getIndex();
238 case sDistPrecedenceRev:
239 return first.getPeriod().getIndex() > second.getPeriod().getIndex();
240 case sDistSamePeriod:
241 return first.getPeriod().getIndex() == second.getPeriod().getIndex();
242 case sDistDifferentPeriod:
243 return first.getPeriod().getIndex() != second.getPeriod().getIndex();
244 case sDistSameRoom:
245 return first.getRoomPlacements().containsAll(second.getRoomPlacements())
246 || second.getRoomPlacements().containsAll(first.getRoomPlacements());
247 case sDistDifferentRoom:
248 for (Iterator<ExamRoomPlacement> i = first.getRoomPlacements().iterator(); i.hasNext();)
249 if (second.getRoomPlacements().contains(i.next()))
250 return false;
251 return true;
252 default:
253 return false;
254 }
255 }
256
257 /**
258 * Compare with other constraint for equality
259 */
260 @Override
261 public boolean equals(Object o) {
262 if (o == null || !(o instanceof ExamDistributionConstraint))
263 return false;
264 ExamDistributionConstraint c = (ExamDistributionConstraint) o;
265 return getType() == c.getType() && getId() == c.getId();
266 }
267
268 /**
269 * Return true if this is hard constraint or this is a soft constraint
270 * without any violation
271 */
272 public boolean isSatisfied() {
273 return isSatisfied(null);
274 }
275
276 /**
277 * Return true if this is hard constraint or this is a soft constraint
278 * without any violation
279 *
280 * @param p
281 * exam assignment to be made
282 */
283 public boolean isSatisfied(ExamPlacement p) {
284 if (isHard())
285 return true;
286 switch (getType()) {
287 case sDistPrecedence:
288 ExamPeriod last = null;
289 for (Exam exam : variables()) {
290 ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
291 if (placement == null)
292 continue;
293 if (last == null || last.getIndex() < placement.getPeriod().getIndex())
294 last = placement.getPeriod();
295 else
296 return false;
297 }
298 return true;
299 case sDistPrecedenceRev:
300 last = null;
301 for (Exam exam : variables()) {
302 ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
303 if (placement == null)
304 continue;
305 if (last == null || last.getIndex() > placement.getPeriod().getIndex())
306 last = placement.getPeriod();
307 else
308 return false;
309 }
310 return true;
311 case sDistSamePeriod:
312 ExamPeriod period = null;
313 for (Exam exam : variables()) {
314 ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
315 if (placement == null)
316 continue;
317 if (period == null)
318 period = placement.getPeriod();
319 else if (period.getIndex() != placement.getPeriod().getIndex())
320 return false;
321 }
322 return true;
323 case sDistDifferentPeriod:
324 HashSet<ExamPeriod> periods = new HashSet<ExamPeriod>();
325 for (Exam exam : variables()) {
326 ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
327 if (placement == null)
328 continue;
329 if (!periods.add(placement.getPeriod()))
330 return false;
331 }
332 return true;
333 case sDistSameRoom:
334 Set<ExamRoomPlacement> rooms = null;
335 for (Exam exam : variables()) {
336 ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
337 if (placement == null)
338 continue;
339 if (rooms == null)
340 rooms = placement.getRoomPlacements();
341 else if (!rooms.containsAll(placement.getRoomPlacements())
342 || !placement.getRoomPlacements().containsAll(rooms))
343 return false;
344 }
345 return true;
346 case sDistDifferentRoom:
347 HashSet<ExamRoomPlacement> allRooms = new HashSet<ExamRoomPlacement>();
348 for (Exam exam : variables()) {
349 ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
350 if (placement == null)
351 continue;
352 for (ExamRoomPlacement room : placement.getRoomPlacements()) {
353 if (!allRooms.add(room))
354 return false;
355 }
356 }
357 return true;
358 default:
359 return false;
360 }
361 }
362
363 boolean iIsSatisfied = true;
364
365 @Override
366 public void assigned(long iteration, ExamPlacement value) {
367 super.assigned(iteration, value);
368 if (!isHard() && iIsSatisfied != isSatisfied()) {
369 iIsSatisfied = !iIsSatisfied;
370 ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(iIsSatisfied ? -getWeight() : getWeight());
371 }
372 }
373
374 @Override
375 public void unassigned(long iteration, ExamPlacement value) {
376 super.unassigned(iteration, value);
377 if (!isHard() && iIsSatisfied != isSatisfied()) {
378 iIsSatisfied = !iIsSatisfied;
379 ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(iIsSatisfied ? -getWeight() : getWeight());
380 }
381 }
382
383 /** True if the constraint is related to rooms */
384 public boolean isRoomRelated() {
385 return iType == sDistSameRoom || iType == sDistDifferentRoom;
386 }
387
388 /** True if the constraint is related to periods */
389 public boolean isPeriodRelated() {
390 return !isRoomRelated();
391 }
392 }