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 for (Iterator i1=e1.getAssignments().iterator();i1.hasNext();) {
170 Section s1 = (Section)i1.next();
171 for (Iterator i2=e1.getAssignments().iterator();i2.hasNext();) {
172 Section s2 = (Section)i2.next();
173 if (s1.getId()<s2.getId() && inConflict(s1,s2))
174 ret.add(new Conflict(e1.getRequest().getWeight(),e1.getStudent(),s1,s2));
175 }
176 }
177 return ret;
178 }
179
180 /**
181 * Return a set of distance conflicts ({@link Conflict} objects) between given (course) enrollments.
182 * @param e1 an enrollment
183 * @param e2 an enrollment
184 * @return list of distance conflicts that are between assignment of the given enrollments
185 */
186 public HashSet conflicts(Enrollment e1, Enrollment e2) {
187 HashSet ret = new HashSet();
188 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent())) return ret;
189 for (Iterator i1=e1.getAssignments().iterator();i1.hasNext();) {
190 Section s1 = (Section)i1.next();
191 for (Iterator i2=e2.getAssignments().iterator();i2.hasNext();) {
192 Section s2 = (Section)i2.next();
193 if (inConflict(s1,s2))
194 ret.add(new Conflict(avg(e1.getRequest().getWeight(),e2.getRequest().getWeight()),e1.getStudent(),s1,s2));
195 }
196 }
197 return ret;
198 }
199
200 /**
201 * Allowed distance for the course that follows the given time assignment.
202 * @param time a time assignment of the first of two sections that are back-to-back
203 * @return the maximal allowed distance
204 */
205 public double getAllowedDistance(TimeLocation time) {
206 if (time.getBreakTime()>=15) return 100.0;
207 return 67.0;
208 }
209
210 /**
211 * Total sum of all conflict of the given enrollment and other enrollments that are assignmed to the same student.
212 */
213 public double nrAllConflicts(Enrollment enrollment) {
214 if (!enrollment.isCourseRequest()) return 0;
215 double cnt = nrConflicts(enrollment);
216 for (Enumeration e=enrollment.getStudent().getRequests().elements(); e.hasMoreElements();) {
217 Request request = (Request)e.nextElement();
218 if (request.equals(enrollment.getRequest()) || request.getAssignment()==null || request.equals(iOldVariable)) continue;
219 cnt += nrConflicts(enrollment, (Enrollment)request.getAssignment());
220 }
221 return cnt;
222 }
223
224 /**
225 * The set of all conflicts ({@link Conflict} objects) of the given enrollment and
226 * other enrollments that are assignmed to the same student.
227 */
228 public HashSet allConflicts(Enrollment enrollment) {
229 HashSet ret = new HashSet();
230 if (!enrollment.isCourseRequest()) return ret;
231 for (Enumeration e=enrollment.getStudent().getRequests().elements(); e.hasMoreElements();) {
232 Request request = (Request)e.nextElement();
233 if (request.equals(enrollment.getRequest()) || request.getAssignment()==null) continue;
234 ret.addAll(conflicts(enrollment, (Enrollment)request.getAssignment()));
235 }
236 return ret;
237 }
238
239 /**
240 * Called when a value is assigned to a variable.
241 * Internal number of distance conflicts is updated, see {@link DistanceConflict#getTotalNrConflicts()}.
242 */
243 public void assigned(long iteration, Value value) {
244 double inc = nrAllConflicts((Enrollment)value);
245 iTotalNrConflicts += inc;
246 if (sDebug) {
247 sLog.debug("A:"+value);
248 HashSet allConfs = computeAllConflicts();
249 double allConfWeight = 0.0;
250 for (Iterator i=allConfs.iterator();i.hasNext();)
251 allConfWeight += ((Conflict)i.next()).getWeight();
252 if (Math.abs(iTotalNrConflicts-allConfWeight)>0.0001) {
253 sLog.error("Different number of conflicts "+sDF.format(iTotalNrConflicts)+"!="+sDF.format(allConfWeight));
254 for (Iterator i=allConfs.iterator();i.hasNext();) {
255 Conflict c = (Conflict)i.next();
256 if (!iAllConflicts.contains(c))
257 sLog.debug(" +add+ "+c);
258 }
259 for (Iterator i=iAllConflicts.iterator();i.hasNext();) {
260 Conflict c = (Conflict)i.next();
261 if (!allConfs.contains(c))
262 sLog.debug(" -rem- "+c);
263 }
264 iTotalNrConflicts = allConfWeight;
265 }
266 iAllConflicts = allConfs;
267 if (inc!=0) {
268 sLog.debug("-- DC+"+sDF.format(inc)+" A: "+value);
269 HashSet confs = allConflicts((Enrollment)value);
270 for (Iterator i=confs.iterator();i.hasNext();)
271 sLog.debug(" -- "+i.next());
272 }
273 }
274 }
275
276 /**
277 * Called when a value is unassigned from a variable.
278 * Internal number of distance conflicts is updated, see {@link DistanceConflict#getTotalNrConflicts()}.
279 */
280 public void unassigned(long iteration, Value value) {
281 if (value.variable().equals(iOldVariable)) return;
282 double dec = nrAllConflicts((Enrollment)value);
283 iTotalNrConflicts -= dec;
284 if (sDebug) {
285 sLog.debug("U:"+value);
286 if (dec!=0) {
287 sLog.debug("-- DC-"+sDF.format(dec)+" U: "+value);
288 HashSet confs = allConflicts((Enrollment)value);
289 for (Iterator i=confs.iterator();i.hasNext();)
290 sLog.debug(" -- "+i.next());
291 }
292 }
293 }
294
295 /** Actual number of all distance conflicts */
296 public double getTotalNrConflicts() {
297 return iTotalNrConflicts;
298 }
299
300 /**
301 * Compute the actual number of all distance conflicts.
302 * Should be equal to {@link DistanceConflict#getTotalNrConflicts()}.
303 */
304 public double countTotalNrConflicts() {
305 double total = 0;
306 for (Enumeration e=getModel().variables().elements();e.hasMoreElements();) {
307 Request r1 = (Request)e.nextElement();
308 if (r1.getAssignment()==null || !(r1 instanceof CourseRequest)) continue;
309 total += nrConflicts((Enrollment)r1.getAssignment());
310 for (Enumeration f=r1.getStudent().getRequests().elements();f.hasMoreElements();) {
311 Request r2 = (Request)f.nextElement();
312 if (r2.getAssignment()==null || r1.getId()>=r2.getId() || !(r2 instanceof CourseRequest)) continue;
313 total += nrConflicts((Enrollment)r1.getAssignment(), (Enrollment)r2.getAssignment());
314 }
315 }
316 return total;
317 }
318
319 /**
320 * Compute a set of all distance conflicts ({@link Conflict} objects).
321 */
322 public HashSet computeAllConflicts() {
323 HashSet ret = new HashSet();
324 for (Enumeration e=getModel().variables().elements();e.hasMoreElements();) {
325 Request r1 = (Request)e.nextElement();
326 if (r1.getAssignment()==null || !(r1 instanceof CourseRequest)) continue;
327 ret.addAll(conflicts((Enrollment)r1.getAssignment()));
328 for (Enumeration f=r1.getStudent().getRequests().elements();f.hasMoreElements();) {
329 Request r2 = (Request)f.nextElement();
330 if (r2.getAssignment()==null || r1.getId()>=r2.getId() || !(r2 instanceof CourseRequest)) continue;
331 ret.addAll(conflicts((Enrollment)r1.getAssignment(), (Enrollment)r2.getAssignment()));
332 }
333 }
334 return ret;
335 }
336
337 /**
338 * Quadratic average of two weights.
339 */
340 public double avg(double w1, double w2) {
341 return Math.sqrt(w1*w2);
342 }
343
344 /**
345 * Called before a value is assigned to a variable.
346 */
347 public void beforeAssigned(long iteration, Value value) {
348 if (value!=null) {
349 if (value.variable().getAssignment()!=null)
350 unassigned(iteration, value.variable().getAssignment());
351 iOldVariable=value.variable();
352 }
353 }
354
355 /**
356 * Called after a value is assigned to a variable.
357 */
358 public void afterAssigned(long iteration, Value value) {
359 iOldVariable=null;
360 if (value!=null) assigned(iteration, value);
361 }
362
363 /**
364 * Called after a value is unassigned from a variable.
365 */
366 public void afterUnassigned(long iteration, Value value) {
367 if (value!=null)
368 unassigned(iteration, value);
369 }
370
371 /** A representation of a distance conflict */
372 public class Conflict {
373 private double iWeight;
374 private Student iStudent;
375 private Section iS1, iS2;
376 private int iHashCode;
377
378 /**
379 * Constructor
380 * @param weight conflict weight
381 * @param student related student
382 * @param s1 first conflicting section
383 * @param s2 second conflicting section
384 */
385 public Conflict(double weight, Student student, Section s1, Section s2) {
386 iWeight = weight;
387 iStudent = student;
388 if (s1.getId()<s2.getId()) {
389 iS1 = s1; iS2 = s2;
390 } else {
391 iS1 = s2; iS2 = s1;
392 }
393 iHashCode = (iStudent.getId()+":"+iS1.getId()+":"+iS2.getId()).hashCode();
394 }
395
396 /** Conflict weight */
397 public double getWeight() {
398 return iWeight;
399 }
400
401 /** Related student */
402 public Student getStudent() {
403 return iStudent;
404 }
405
406 /** First section */
407 public Section getS1() {
408 return iS1;
409 }
410
411 /** Second section */
412 public Section getS2() {
413 return iS2;
414 }
415
416 public int hashCode() {
417 return iHashCode;
418 }
419
420 /** The distance between conflicting sections*/
421 public double getDistance() {
422 return Placement.getDistance(getS1().getPlacement(),getS2().getPlacement());
423 }
424
425 public boolean equals(Object o) {
426 if (o==null || !(o instanceof Conflict))
427 return false;
428 Conflict c = (Conflict)o;
429 return getStudent().getId()==c.getStudent().getId() &&
430 getS1().getId()==c.getS1().getId() &&
431 getS2().getId()==c.getS2().getId();
432 }
433
434 public String toString() {
435 return getStudent()+": (w:"+sDF.format(getWeight())+",d:"+sDF.format(10.0*getDistance())+"m) "+getS1()+" -- "+getS2();
436 }
437 }
438 }