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