001 package net.sf.cpsolver.studentsct.check;
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.Hashtable;
009 import java.util.Iterator;
010 import java.util.Map;
011 import java.util.TreeSet;
012 import java.util.Vector;
013
014 import net.sf.cpsolver.ifs.util.CSVFile;
015 import net.sf.cpsolver.studentsct.StudentSectioningModel;
016 import net.sf.cpsolver.studentsct.model.Assignment;
017 import net.sf.cpsolver.studentsct.model.Course;
018 import net.sf.cpsolver.studentsct.model.CourseRequest;
019 import net.sf.cpsolver.studentsct.model.Enrollment;
020 import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
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 class looks and reports all cases when a student cannot obtain a complete schedule because of
027 * time assignments of the requested courses. Course and section limits are not checked.
028 *
029 * <br><br>
030 *
031 * Usage:<br>
032 * <code>
033 * InevitableStudentConflicts ch = new InevitableStudentConflicts(model);<br>
034 * if (!ch.check()) ch.getCSVFile().save(new File("inevitable-conflicts.csv"));
035 * </code>
036 *
037 * <br><br>
038 * Parameters:
039 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
040 * <tr><td>InevitableStudentConflicts.DeleteInevitable</td><td>{@link Boolean}</td><td>
041 * If true, for each no-good (the smallest set of requests of the same student that cannot be
042 * assigned at the same time), the problematic request (i.e., the request that was not
043 * assigned by {@link StudentCheck}) is removed from the model.
044 * </td></tr>
045 * </table>
046 *
047 * <br><br>
048 *
049 * @version
050 * StudentSct 1.1 (Student Sectioning)<br>
051 * Copyright (C) 2007 Tomáš Müller<br>
052 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
053 * Lazenska 391, 76314 Zlin, Czech Republic<br>
054 * <br>
055 * This library is free software; you can redistribute it and/or
056 * modify it under the terms of the GNU Lesser General Public
057 * License as published by the Free Software Foundation; either
058 * version 2.1 of the License, or (at your option) any later version.
059 * <br><br>
060 * This library is distributed in the hope that it will be useful,
061 * but WITHOUT ANY WARRANTY; without even the implied warranty of
062 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
063 * Lesser General Public License for more details.
064 * <br><br>
065 * You should have received a copy of the GNU Lesser General Public
066 * License along with this library; if not, write to the Free Software
067 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
068 */
069 public class InevitableStudentConflicts {
070 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(InevitableStudentConflicts.class);
071 private StudentSectioningModel iModel;
072 private CSVFile iCSVFile = null;
073 public static boolean sDebug = false;
074 private boolean iDeleteInevitable;
075
076 /** Constructor
077 * @param model student sectioning model
078 */
079 public InevitableStudentConflicts(StudentSectioningModel model) {
080 iModel = model;
081 iCSVFile = new CSVFile();
082 iCSVFile.setHeader(new CSVFile.CSVField[] {
083 new CSVFile.CSVField("NoGood"),
084 new CSVFile.CSVField("NrStud"),
085 new CSVFile.CSVField("StudWeight"),
086 new CSVFile.CSVField("1. Course"),
087 new CSVFile.CSVField("2. Course"),
088 new CSVFile.CSVField("3. Course"),
089 new CSVFile.CSVField("4. Course"),
090 new CSVFile.CSVField("5. Course")
091 });
092 iDeleteInevitable = model.getProperties().getPropertyBoolean("InevitableStudentConflicts.DeleteInevitable", false);
093 }
094
095 /** Return student sectioning model */
096 public StudentSectioningModel getModel() {
097 return iModel;
098 }
099
100 /** Return report */
101 public CSVFile getCSVFile() {
102 return iCSVFile;
103 }
104
105 /** Check model for inevitable student conflicts */
106 public boolean check() {
107 sLog.info("Checking for inevitable student conflicts...");
108 Hashtable noGoods = new Hashtable();
109 long studentWithoutCompleteSchedule = 0;
110 long inevitableRequests = 0;
111 double inevitableRequestWeight = 0.0;
112 long incompleteInevitableRequests = 0;
113 double incompleteInevitableRequestWeight = 0.0;
114 long total = 0;
115 Comparator simpleCmp = new Comparator() {
116 public int compare(Object o1, Object o2) {
117 return o1.toString().compareTo(o2.toString());
118 }
119 };
120 HashSet requests2remove = new HashSet();
121 for (Enumeration e=getModel().getStudents().elements();e.hasMoreElements();) {
122 Student student = (Student)e.nextElement();
123 sLog.debug(" Checking "+(++total)+". student "+student+"...");
124 if (student.isComplete()) {
125 for (Enumeration f=student.getRequests().elements();f.hasMoreElements();) {
126 Request request = (Request)f.nextElement();
127 if (request.getAssignment()==null) {
128 inevitableRequests++;
129 inevitableRequestWeight+=request.getWeight();
130 }
131 }
132 } else {
133 StudentCheck ch = new StudentCheck(student.getRequests());
134 ch.check();
135 if (!ch.isBestComplete()) {
136 sLog.info(" Student "+student+" cannot have a complete schedule");
137 studentWithoutCompleteSchedule++;
138 }
139 int idx = 0;
140 for (Enumeration f=student.getRequests().elements();f.hasMoreElements();idx++) {
141 Request request = (Request)f.nextElement();
142 Enrollment enrollment = ch.getBestAssignment()[idx];
143 if (enrollment==null) {
144 if (!ch.isBestComplete()) {
145 Vector noGood = noGood(student,ch,idx);
146 sLog.info(" Request "+request+" cannot be assigned");
147 for (Enumeration g=noGood.elements();g.hasMoreElements();) {
148 Request r = (Request)g.nextElement();
149 sLog.debug(" "+r);
150 Collection values = null;
151 if (r instanceof CourseRequest) {
152 values = ((CourseRequest)r).getEnrollmentsSkipSameTime();
153 } else {
154 values = request.computeEnrollments();
155 }
156 for (Iterator i=values.iterator();i.hasNext();) {
157 Enrollment en = (Enrollment)i.next();
158 sLog.debug(" "+enrollment2string(en));
159 }
160 }
161 if (iDeleteInevitable) {
162 requests2remove.add(request); //noGood.lastElement()
163 sLog.info(" -- request "+request+" picked to be removed from the model");
164 }
165 TreeSet key = new TreeSet(simpleCmp);
166 for (Enumeration g=noGood.elements();g.hasMoreElements();) {
167 Request r = (Request)g.nextElement();
168 if (r instanceof CourseRequest) {
169 key.add((Course)((CourseRequest)r).getCourses().firstElement());
170 } else {
171 key.add("Free "+((FreeTimeRequest)r).getTime().getLongName());
172 }
173 }
174 Object[] counter = (Object[])noGoods.get(key);
175 int ir = (counter==null?1:((Integer)counter[0]).intValue()+1);
176 double irw = (counter==null?0.0:((Double)counter[1]).doubleValue())+request.getWeight();
177 noGoods.put(key, new Object[]{new Integer(ir), new Double(irw)});
178 if (ch.canAssign(request, idx)) {
179 incompleteInevitableRequests++;
180 incompleteInevitableRequestWeight+=request.getWeight();
181 }
182 }
183 inevitableRequests++;
184 inevitableRequestWeight+=request.getWeight();
185 }
186 }
187 }
188 }
189 for (Iterator i=noGoods.entrySet().iterator();i.hasNext();) {
190 Map.Entry entry = (Map.Entry)i.next();
191 TreeSet noGood = (TreeSet)entry.getKey();
192 Object[] counter = (Object[])entry.getValue();
193 Vector fields = new Vector();
194 String courseStr = "";
195 for (Iterator j=noGood.iterator();j.hasNext();) {
196 Object x = (Object)j.next();
197 if (x instanceof Course) {
198 Course course = (Course)x;
199 courseStr += course.getName();
200 } else
201 courseStr += x.toString();
202 if (j.hasNext())
203 courseStr += ", ";
204 }
205 fields.add(new CSVFile.CSVField(courseStr));
206 fields.add(new CSVFile.CSVField(((Integer)counter[0]).intValue()));
207 fields.add(new CSVFile.CSVField(((Double)counter[1]).doubleValue()));
208 for (Iterator j=noGood.iterator();j.hasNext();) {
209 Object x = (Object)j.next();
210 if (x instanceof Course) {
211 Course course = (Course)x;
212 Vector courses = new Vector(1); courses.add(course);
213 CourseRequest cr = new CourseRequest(-1, 0, false, new Student(-1), courses, false);
214 String field = course.getName();
215 int idx = 0;
216 for (Iterator k=cr.getEnrollmentsSkipSameTime().iterator();k.hasNext();) {
217 if (idx++>20) {
218 field += "\n ..."; break;
219 } else {
220 field += "\n "+enrollment2string((Enrollment)k.next());
221 }
222 }
223 fields.add(new CSVFile.CSVField(field));
224 } else
225 fields.add(new CSVFile.CSVField(x.toString()));
226 }
227 iCSVFile.addLine(fields);
228 }
229 if (!requests2remove.isEmpty()) {
230 for (Iterator i=requests2remove.iterator();i.hasNext();) {
231 Request request = (Request)i.next();
232 removeRequest(request);
233 }
234 }
235 sLog.info("Students that can never obtain a complete schedule: "+studentWithoutCompleteSchedule);
236 sLog.info("Inevitable student requests: "+inevitableRequests);
237 sLog.info("Inevitable student request weight: "+inevitableRequestWeight);
238 sLog.info("Inevitable student requests of students without a complete schedule: "+incompleteInevitableRequests);
239 sLog.info("Inevitable student request weight of students without a complete schedule: "+incompleteInevitableRequestWeight);
240 if (iCSVFile.getLines()!=null)
241 Collections.sort(iCSVFile.getLines(), new Comparator() {
242 public int compare(Object o1, Object o2) {
243 CSVFile.CSVLine l1 = (CSVFile.CSVLine)o1;
244 CSVFile.CSVLine l2 = (CSVFile.CSVLine)o2;
245 int cmp = Double.compare(l2.getField(1).toDouble(),l1.getField(1).toDouble());
246 if (cmp!=0) return cmp;
247 return l1.getField(0).toString().compareTo(l2.getField(0).toString());
248 }
249 });
250 return (inevitableRequests==0);
251 }
252
253 /** Remove given request from the model */
254 private void removeRequest(Request request) {
255 request.getStudent().getRequests().remove(request);
256 for (Enumeration e=request.getStudent().getRequests().elements();e.hasMoreElements();) {
257 Request r = (Request)e.nextElement();
258 if (r.getPriority()>request.getPriority())
259 r.setPriority(r.getPriority()-1);
260 }
261 iModel.removeVariable(request);
262 if (request.getStudent().getRequests().isEmpty())
263 iModel.getStudents().remove(request.getStudent());
264 }
265
266 /** Convert given enrollment to a string (comma separated list of subpart names and time assignments only) */
267 private static String enrollment2string(Enrollment enrollment) {
268 StringBuffer sb = new StringBuffer();
269 Collection assignments = enrollment.getAssignments();
270 if (enrollment.isCourseRequest()) {
271 assignments = new TreeSet(new Comparator() {
272 public int compare(Object o1, Object o2) {
273 Section s1 = (Section)o1;
274 Section s2 = (Section)o2;
275 return s1.getSubpart().compareTo(s2.getSubpart());
276 }
277 });
278 assignments.addAll(enrollment.getAssignments());
279 }
280 for (Iterator i=assignments.iterator();i.hasNext();) {
281 Assignment a = (Assignment)i.next();
282 if (a instanceof Section)
283 sb.append(((Section)a).getSubpart().getName()+" ");
284 if (a.getTime()!=null)
285 sb.append(a.getTime().getLongName());
286 if (i.hasNext()) sb.append(", ");
287 }
288 return sb.toString();
289 }
290
291 /** No-good set of requests
292 * @param student student
293 * @param ch student checked that failed to find a complete schedule
294 * @param idx index of unassigned course in the best found schedule
295 * @return the smallest set of requests that cannot be assigned all together, containing the request with the given index
296 */
297 private Vector noGood(Student student, StudentCheck ch, int idx) {
298 Vector noGood = new Vector();
299 Request rx = (Request)student.getRequests().elementAt(idx);
300 for (int i=0;i<student.getRequests().size();i++) {
301 if (i==idx) noGood.add(rx);
302 else if (ch.getBestAssignment()[i]!=null) noGood.add(ch.getBestAssignment()[i].getRequest());
303 }
304 for (Enumeration e=noGood.elements();e.hasMoreElements();) {
305 Request r = (Request)e.nextElement();
306 if (r.equals(rx)) continue;
307 Vector newNoGood = new Vector(noGood);
308 newNoGood.remove(r);
309 StudentCheck chx = new StudentCheck(newNoGood);
310 chx.check();
311 if (!chx.isBestComplete()) noGood = newNoGood;
312 }
313 return noGood;
314 }
315
316 /** Use branch&bound technique to find out whether a student can get a complete schedule. */
317 public static class StudentCheck {
318 private Vector iRequests;
319 private Enrollment[] iAssignment, iBestAssignment;
320 private Hashtable iValues;
321 private int iBestNrAssigned = 0;
322 private boolean iBestComplete = false;
323
324 /**
325 * Constructor
326 * @param requests course and free time requests of a student
327 */
328 public StudentCheck(Vector requests) {
329 iRequests = requests;
330 }
331
332 /**
333 * Execute branch & bound, return the best found schedule for the selected student.
334 */
335 public void check() {
336 iAssignment = new Enrollment[iRequests.size()];
337 iBestAssignment = null; iBestNrAssigned = 0; iBestComplete = false;
338 iValues = new Hashtable();
339 backTrack(0);
340 }
341
342 /** Best schedule */
343 public Enrollment[] getBestAssignment() {
344 return iBestAssignment;
345 }
346
347 /** Number of requests assigned in the best schedule */
348 public int getBestNrAssigned() {
349 return iBestNrAssigned;
350 }
351
352 /** Bound for the number of assigned requests in the current schedule */
353 public int getNrAssignedBound(int idx) {
354 int bound = 0;
355 int i=0, alt=0;
356 for (Enumeration e=iRequests.elements();e.hasMoreElements();i++) {
357 Request r = (Request)e.nextElement();
358 if (i<idx) {
359 if (iAssignment[i]!=null)
360 bound++;
361 if (r.isAlternative()) {
362 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--;
363 } else {
364 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++;
365 }
366 } else {
367 if (!r.isAlternative())
368 bound ++;
369 else if (alt>0) {
370 bound ++; alt--;
371 }
372 }
373 }
374 return bound;
375 }
376
377 /** True when the best enrollment is complete */
378 public boolean isBestComplete() {
379 return iBestComplete;
380 }
381
382 /** Save the current schedule as the best */
383 public void saveBest() {
384 if (iBestAssignment==null)
385 iBestAssignment = new Enrollment[iAssignment.length];
386 iBestNrAssigned = 0;
387 for (int i=0;i<iAssignment.length;i++) {
388 iBestAssignment[i] = iAssignment[i];
389 if (iBestAssignment[i]!=null) iBestNrAssigned++;
390 }
391 int nrRequests = 0;
392 int nrAssignedRequests = 0;
393 int idx = 0;
394 for (Enumeration e=iRequests.elements();e.hasMoreElements();idx++) {
395 Request r = (Request)e.nextElement();
396 if (!(r instanceof CourseRequest)) continue; //ignore free times
397 if (!r.isAlternative()) nrRequests++;
398 if (iBestAssignment[idx]!=null) nrAssignedRequests++;
399 }
400 iBestComplete = (nrAssignedRequests==nrRequests);
401 }
402
403 /** First conflicting enrollment */
404 public Enrollment firstConflict(Enrollment enrollment) {
405 for (int i=0;i<iAssignment.length;i++) {
406 if (iAssignment[i]!=null && iAssignment[i].isOverlapping(enrollment)) return iAssignment[i];
407 }
408 return null;
409 }
410
411 /** True if the given request can be assigned */
412 public boolean canAssign(Request request, int idx) {
413 if (!request.isAlternative() || iAssignment[idx]!=null) return true;
414 int alt = 0;
415 int i = 0;
416 for (Enumeration e=iRequests.elements();e.hasMoreElements();i++) {
417 Request r = (Request)e.nextElement();
418 if (r.equals(request)) continue;
419 if (r.isAlternative()) {
420 if (iAssignment[i]!=null || (r instanceof CourseRequest && ((CourseRequest)r).isWaitlist())) alt--;
421 } else {
422 if (r instanceof CourseRequest && !((CourseRequest)r).isWaitlist() && iAssignment[i]==null) alt++;
423 }
424 }
425 return (alt>0);
426 }
427
428 /** Number of assigned requests in the current schedule */
429 public int getNrAssigned() {
430 int assigned = 0;
431 for (int i=0;i<iAssignment.length;i++)
432 if (iAssignment[i]!=null) assigned++;
433 return assigned;
434 }
435
436 /** branch & bound search */
437 public void backTrack(int idx) {
438 if (sDebug) sLog.debug("BT["+idx+"]: -- assigned:"+getNrAssigned()+", bound:"+getNrAssignedBound(idx)+", best:"+getBestNrAssigned());
439 if (idx==iAssignment.length) {
440 if (iBestAssignment==null || getNrAssigned()>getBestNrAssigned()) {
441 saveBest();
442 if (sDebug) sLog.debug("BT["+idx+"]: -- BEST "+getBestNrAssigned());
443 }
444 return;
445 } else if (isBestComplete() || getNrAssignedBound(idx)<=getBestNrAssigned()) {
446 if (sDebug) sLog.debug("BT["+idx+"]: -- BOUND "+getNrAssignedBound(idx)+" <= "+getBestNrAssigned());
447 return;
448 }
449 Request request = (Request)iRequests.elementAt(idx);
450 if (sDebug) sLog.debug("BT["+idx+"]: -- REQUEST "+request);
451 if (!canAssign(request, idx)) {
452 if (sDebug) sLog.debug("BT["+idx+"]: -- CANNOT ASSIGN");
453 backTrack(idx+1);
454 return;
455 }
456 Collection values = null;
457 if (request instanceof CourseRequest) {
458 CourseRequest courseRequest = (CourseRequest)request;
459 values = (Collection)iValues.get(courseRequest);
460 if (values==null) {
461 values = courseRequest.getEnrollmentsSkipSameTime();
462 iValues.put(courseRequest, values);
463 }
464 } else {
465 values = request.computeEnrollments();
466 }
467 if (sDebug) sLog.debug("BT["+idx+"]: -- VALUES: "+values.size());
468 boolean hasNoConflictValue = false;
469 for (Iterator i=values.iterator();i.hasNext() && !isBestComplete();) {
470 Enrollment enrollment = (Enrollment)i.next();
471 if (sDebug) sLog.debug("BT["+idx+"]: -- "+enrollment2string(enrollment));
472 Enrollment conflict = firstConflict(enrollment);
473 if (conflict!=null) {
474 if (sDebug) sLog.debug("BT["+idx+"]: -- conflict with "+conflict.getRequest()+" "+enrollment2string(conflict));
475 continue;
476 }
477 hasNoConflictValue = true;
478 iAssignment[idx] = enrollment;
479 backTrack(idx+1);
480 iAssignment[idx] = null;
481 }
482 if (!hasNoConflictValue || request instanceof CourseRequest) {
483 if (sDebug) sLog.debug("BT["+idx+"]: -- without assignment");
484 backTrack(idx+1);
485 }
486 }
487 }
488
489 }