001 package net.sf.cpsolver.studentsct.extension;
002
003 import java.text.DecimalFormat;
004 import java.util.Enumeration;
005 import java.util.HashSet;
006 import java.util.Iterator;
007
008 import org.apache.log4j.Logger;
009
010 import net.sf.cpsolver.coursett.model.Placement;
011 import net.sf.cpsolver.coursett.model.TimeLocation;
012 import net.sf.cpsolver.ifs.extension.Extension;
013 import net.sf.cpsolver.ifs.model.ModelListener;
014 import net.sf.cpsolver.ifs.model.Value;
015 import net.sf.cpsolver.ifs.model.Variable;
016 import net.sf.cpsolver.ifs.solver.Solver;
017 import net.sf.cpsolver.ifs.util.DataProperties;
018 import net.sf.cpsolver.studentsct.StudentSectioningModel;
019 import net.sf.cpsolver.studentsct.model.CourseRequest;
020 import net.sf.cpsolver.studentsct.model.Enrollment;
021 import net.sf.cpsolver.studentsct.model.Request;
022 import net.sf.cpsolver.studentsct.model.Section;
023 import net.sf.cpsolver.studentsct.model.Student;
024
025 /**
026 * This extension computes student distant conflicts.
027 * Two sections that are attended by the same student are considered in a
028 * distance conflict if they are back-to-back taught in locations
029 * that are two far away. The allowed distance is provided by method
030 * {@link DistanceConflict#getAllowedDistance(TimeLocation)}.
031 *
032 * @see TimeLocation
033 * @see Placement
034 *
035 * <br><br>
036 *
037 * @version
038 * StudentSct 1.1 (Student Sectioning)<br>
039 * Copyright (C) 2007 Tomáš Müller<br>
040 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
041 * Lazenska 391, 76314 Zlin, Czech Republic<br>
042 * <br>
043 * This library is free software; you can redistribute it and/or
044 * modify it under the terms of the GNU Lesser General Public
045 * License as published by the Free Software Foundation; either
046 * version 2.1 of the License, or (at your option) any later version.
047 * <br><br>
048 * This library is distributed in the hope that it will be useful,
049 * but WITHOUT ANY WARRANTY; without even the implied warranty of
050 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
051 * Lesser General Public License for more details.
052 * <br><br>
053 * You should have received a copy of the GNU Lesser General Public
054 * License along with this library; if not, write to the Free Software
055 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
056 */
057
058 public class DistanceConflict extends Extension implements ModelListener {
059 private static Logger sLog = Logger.getLogger(DistanceConflict.class);
060 private static DecimalFormat sDF = new DecimalFormat("0.000");
061 private double iTotalNrConflicts = 0;
062 private HashSet iAllConflicts = new HashSet();
063 /** Debug flag */
064 public static boolean sDebug = false;
065 private Variable iOldVariable = null;
066
067 /**
068 * Constructor.
069 * Beside of other thigs, this constructor also uses
070 * {@link StudentSectioningModel#setDistanceConflict(DistanceConflict)} to
071 * set the this instance to the model.
072 * @param solver constraint solver
073 * @param properties configuration
074 */
075 public DistanceConflict(Solver solver, DataProperties properties) {
076 super(solver, properties);
077 if (solver!=null)
078 ((StudentSectioningModel)solver.currentSolution().getModel()).setDistanceConflict(this);
079 }
080
081 /**
082 * Initialize extension
083 */
084 public boolean init(Solver solver) {
085 iTotalNrConflicts = countTotalNrConflicts();
086 return true;
087 }
088
089 public String toString() {
090 return "DistanceConstraint";
091 }
092
093 /**
094 * Return true if the given two sections are in distance conflict.
095 * This means that the sections are back-to-back and that they are
096 * placed in locations that are two far.
097 * @param s1 a section
098 * @param s2 a section
099 * @return true, if the given sections are in a distance conflict
100 */
101 public boolean inConflict(Section s1, Section s2) {
102 if (s1.getPlacement()==null || s2.getPlacement()==null) return false;
103 TimeLocation t1 = s1.getTime();
104 TimeLocation t2 = s2.getTime();
105 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
106 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
107 if (a1+t1.getNrSlotsPerMeeting()==a2) {
108 double dist = Placement.getDistance(s1.getPlacement(), s2.getPlacement());
109 if (dist>getAllowedDistance(t1)) return true;
110 } else if (a2+t2.getNrSlotsPerMeeting()==a1) {
111 double dist = Placement.getDistance(s1.getPlacement(), s2.getPlacement());
112 if (dist>getAllowedDistance(t2)) return true;
113 }
114 return false;
115 }
116
117 /**
118 * Return number of distance conflict of a (course) enrollment.
119 * It is the number of pairs of assignments of the enrollment
120 * that are in a distance conflict, weighted by the
121 * request's weight (see {@link Request#getWeight()}).
122 * @param e1 an enrollment
123 * @return number of distance conflicts
124 */
125 public double nrConflicts(Enrollment e1) {
126 if (!e1.isCourseRequest()) return 0;
127 double cnt = 0;
128 for (Iterator i1=e1.getAssignments().iterator();i1.hasNext();) {
129 Section s1 = (Section)i1.next();
130 for (Iterator i2=e1.getAssignments().iterator();i2.hasNext();) {
131 Section s2 = (Section)i2.next();
132 if (s1.getId()<s2.getId() && inConflict(s1,s2)) cnt+=e1.getRequest().getWeight();
133 }
134 }
135 return cnt;
136 }
137
138 /**
139 * Return number of distance conflicts that are between two enrollments.
140 * It is the number of pairs of assignments of these enrollments
141 * that are in a distance conflict, weighted by the average
142 * (see {@link DistanceConflict#avg(double, double)}) of the requests'
143 * weight (see {@link Request#getWeight()}).
144 * @param e1 an enrollment
145 * @param e2 an enrollment
146 * @return number of distance conflict between given enrollments
147 */
148 public double nrConflicts(Enrollment e1, Enrollment e2) {
149 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent())) return 0;
150 double cnt = 0;
151 for (Iterator i1=e1.getAssignments().iterator();i1.hasNext();) {
152 Section s1 = (Section)i1.next();
153 for (Iterator i2=e2.getAssignments().iterator();i2.hasNext();) {
154 Section s2 = (Section)i2.next();
155 if (inConflict(s1,s2)) cnt+=avg(e1.getRequest().getWeight(),e2.getRequest().getWeight());
156 }
157 }
158 return cnt;
159 }
160
161 /**
162 * Return a set of distance conflicts ({@link Conflict} objects) of a (course) enrollment.
163 * @param e1 an enrollment
164 * @return list of distance conflicts that are between assignment of the given enrollment
165 */
166 public HashSet conflicts(Enrollment e1) {
167 HashSet ret = new HashSet();
168 if (!e1.isCourseRequest()) return ret;
169 int cnt = 0;
170 for (Iterator i1=e1.getAssignments().iterator();i1.hasNext();) {
171 Section s1 = (Section)i1.next();
172 for (Iterator i2=e1.getAssignments().iterator();i2.hasNext();) {
173 Section s2 = (Section)i2.next();
174 if (s1.getId()<s2.getId() && inConflict(s1,s2))
175 ret.add(new Conflict(e1.getRequest().getWeight(),e1.getStudent(),s1,s2));
176 }
177 }
178 return ret;
179 }
180
181 /**
182 * Return a set of distance conflicts ({@link Conflict} objects) between given (course) enrollments.
183 * @param e1 an enrollment
184 * @param e2 an enrollment
185 * @return list of distance conflicts that are between assignment of the given enrollments
186 */
187 public HashSet conflicts(Enrollment e1, Enrollment e2) {
188 HashSet ret = new HashSet();
189 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent())) return ret;
190 int cnt = 0;
191 for (Iterator i1=e1.getAssignments().iterator();i1.hasNext();) {
192 Section s1 = (Section)i1.next();
193 for (Iterator i2=e2.getAssignments().iterator();i2.hasNext();) {
194 Section s2 = (Section)i2.next();
195 if (inConflict(s1,s2))
196 ret.add(new Conflict(avg(e1.getRequest().getWeight(),e2.getRequest().getWeight()),e1.getStudent(),s1,s2));
197 }
198 }
199 return ret;
200 }
201
202 /**
203 * Allowed distance for the course that follows the given time assignment.
204 * @param time a time assignment of the first of two sections that are back-to-back
205 * @return the maximal allowed distance
206 */
207 public double getAllowedDistance(TimeLocation time) {
208 if (time.getBreakTime()>=15) return 100.0;
209 return 67.0;
210 }
211
212 /**
213 * Total sum of all conflict of the given enrollment and other enrollments that are assignmed to the same student.
214 */
215 public double nrAllConflicts(Enrollment enrollment) {
216 if (!enrollment.isCourseRequest()) return 0;
217 double cnt = nrConflicts(enrollment);
218 for (Enumeration e=enrollment.getStudent().getRequests().elements(); e.hasMoreElements();) {
219 Request request = (Request)e.nextElement();
220 if (request.equals(enrollment.getRequest()) || request.getAssignment()==null || request.equals(iOldVariable)) continue;
221 cnt += nrConflicts(enrollment, (Enrollment)request.getAssignment());
222 }
223 return cnt;
224 }
225
226 /**
227 * The set of all conflicts ({@link Conflict} objects) of the given enrollment and
228 * other enrollments that are assignmed to the same student.
229 */
230 public HashSet allConflicts(Enrollment enrollment) {
231 HashSet ret = new HashSet();
232 if (!enrollment.isCourseRequest()) return ret;
233 for (Enumeration e=enrollment.getStudent().getRequests().elements(); e.hasMoreElements();) {
234 Request request = (Request)e.nextElement();
235 if (request.equals(enrollment.getRequest()) || request.getAssignment()==null) continue;
236 ret.addAll(conflicts(enrollment, (Enrollment)request.getAssignment()));
237 }
238 return ret;
239 }
240
241 /**
242 * Called when a value is assigned to a variable.
243 * Internal number of distance conflicts is updated, see {@link DistanceConflict#getTotalNrConflicts()}.
244 */
245 public void assigned(long iteration, Value value) {
246 double inc = nrAllConflicts((Enrollment)value);
247 iTotalNrConflicts += inc;
248 if (sDebug) {
249 sLog.debug("A:"+value);
250 HashSet allConfs = computeAllConflicts();
251 double allConfWeight = 0.0;
252 for (Iterator i=allConfs.iterator();i.hasNext();)
253 allConfWeight += ((Conflict)i.next()).getWeight();
254 if (Math.abs(iTotalNrConflicts-allConfWeight)>0.0001) {
255 sLog.error("Different number of conflicts "+sDF.format(iTotalNrConflicts)+"!="+sDF.format(allConfWeight));
256 for (Iterator i=allConfs.iterator();i.hasNext();) {
257 Conflict c = (Conflict)i.next();
258 if (!iAllConflicts.contains(c))
259 sLog.debug(" +add+ "+c);
260 }
261 for (Iterator i=iAllConflicts.iterator();i.hasNext();) {
262 Conflict c = (Conflict)i.next();
263 if (!allConfs.contains(c))
264 sLog.debug(" -rem- "+c);
265 }
266 iTotalNrConflicts = allConfWeight;
267 }
268 iAllConflicts = allConfs;
269 if (inc!=0) {
270 sLog.debug("-- DC+"+sDF.format(inc)+" A: "+value);
271 HashSet confs = allConflicts((Enrollment)value);
272 for (Iterator i=confs.iterator();i.hasNext();)
273 sLog.debug(" -- "+i.next());
274 }
275 }
276 }
277
278 /**
279 * Called when a value is unassigned from a variable.
280 * Internal number of distance conflicts is updated, see {@link DistanceConflict#getTotalNrConflicts()}.
281 */
282 public void unassigned(long iteration, Value value) {
283 if (value.variable().equals(iOldVariable)) return;
284 double dec = nrAllConflicts((Enrollment)value);
285 iTotalNrConflicts -= dec;
286 if (sDebug) {
287 sLog.debug("U:"+value);
288 if (dec!=0) {
289 sLog.debug("-- DC-"+sDF.format(dec)+" U: "+value);
290 HashSet confs = allConflicts((Enrollment)value);
291 for (Iterator i=confs.iterator();i.hasNext();)
292 sLog.debug(" -- "+i.next());
293 }
294 }
295 }
296
297 /** Actual number of all distance conflicts */
298 public double getTotalNrConflicts() {
299 return iTotalNrConflicts;
300 }
301
302 /**
303 * Compute the actual number of all distance conflicts.
304 * Should be equal to {@link DistanceConflict#getTotalNrConflicts()}.
305 */
306 public double countTotalNrConflicts() {
307 double total = 0;
308 for (Enumeration e=getModel().variables().elements();e.hasMoreElements();) {
309 Request r1 = (Request)e.nextElement();
310 if (r1.getAssignment()==null || !(r1 instanceof CourseRequest)) continue;
311 total += nrConflicts((Enrollment)r1.getAssignment());
312 for (Enumeration f=r1.getStudent().getRequests().elements();f.hasMoreElements();) {
313 Request r2 = (Request)f.nextElement();
314 if (r2.getAssignment()==null || r1.getId()>=r2.getId() || !(r2 instanceof CourseRequest)) continue;
315 total += nrConflicts((Enrollment)r1.getAssignment(), (Enrollment)r2.getAssignment());
316 }
317 }
318 return total;
319 }
320
321 /**
322 * Compute a set of all distance conflicts ({@link Conflict} objects).
323 */
324 public HashSet computeAllConflicts() {
325 HashSet ret = new HashSet();
326 for (Enumeration e=getModel().variables().elements();e.hasMoreElements();) {
327 Request r1 = (Request)e.nextElement();
328 if (r1.getAssignment()==null || !(r1 instanceof CourseRequest)) continue;
329 ret.addAll(conflicts((Enrollment)r1.getAssignment()));
330 for (Enumeration f=r1.getStudent().getRequests().elements();f.hasMoreElements();) {
331 Request r2 = (Request)f.nextElement();
332 if (r2.getAssignment()==null || r1.getId()>=r2.getId() || !(r2 instanceof CourseRequest)) continue;
333 ret.addAll(conflicts((Enrollment)r1.getAssignment(), (Enrollment)r2.getAssignment()));
334 }
335 }
336 return ret;
337 }
338
339 /**
340 * Quadratic average of two weights.
341 */
342 public double avg(double w1, double w2) {
343 return Math.sqrt(w1*w2);
344 }
345
346 /**
347 * Called before a value is assigned to a variable.
348 */
349 public void beforeAssigned(long iteration, Value value) {
350 if (value!=null) {
351 if (value.variable().getAssignment()!=null)
352 unassigned(iteration, value.variable().getAssignment());
353 iOldVariable=value.variable();
354 }
355 }
356
357 /**
358 * Called after a value is assigned to a variable.
359 */
360 public void afterAssigned(long iteration, Value value) {
361 iOldVariable=null;
362 if (value!=null) assigned(iteration, value);
363 }
364
365 /**
366 * Called after a value is unassigned from a variable.
367 */
368 public void afterUnassigned(long iteration, Value value) {
369 if (value!=null)
370 unassigned(iteration, value);
371 }
372
373 /** A representation of a distance conflict */
374 public class Conflict {
375 private double iWeight;
376 private Student iStudent;
377 private Section iS1, iS2;
378 private int iHashCode;
379
380 /**
381 * Constructor
382 * @param weight conflict weight
383 * @param student related student
384 * @param s1 first conflicting section
385 * @param s2 second conflicting section
386 */
387 public Conflict(double weight, Student student, Section s1, Section s2) {
388 iWeight = weight;
389 iStudent = student;
390 if (s1.getId()<s2.getId()) {
391 iS1 = s1; iS2 = s2;
392 } else {
393 iS1 = s2; iS2 = s1;
394 }
395 iHashCode = (iStudent.getId()+":"+iS1.getId()+":"+iS2.getId()).hashCode();
396 }
397
398 /** Conflict weight */
399 public double getWeight() {
400 return iWeight;
401 }
402
403 /** Related student */
404 public Student getStudent() {
405 return iStudent;
406 }
407
408 /** First section */
409 public Section getS1() {
410 return iS1;
411 }
412
413 /** Second section */
414 public Section getS2() {
415 return iS2;
416 }
417
418 public int hashCode() {
419 return iHashCode;
420 }
421
422 /** The distance between conflicting sections*/
423 public double getDistance() {
424 return Placement.getDistance(getS1().getPlacement(),getS2().getPlacement());
425 }
426
427 public boolean equals(Object o) {
428 if (o==null || !(o instanceof Conflict))
429 return false;
430 Conflict c = (Conflict)o;
431 return getStudent().getId()==c.getStudent().getId() &&
432 getS1().getId()==c.getS1().getId() &&
433 getS2().getId()==c.getS2().getId();
434 }
435
436 public String toString() {
437 return getStudent()+": (w:"+sDF.format(getWeight())+",d:"+sDF.format(10.0*getDistance())+"m) "+getS1()+" -- "+getS2();
438 }
439 }
440 }