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     * &nbsp;&nbsp;&nbsp;&nbsp; InevitableStudentConflicts ch = new InevitableStudentConflicts(model);<br>
036     * &nbsp;&nbsp;&nbsp;&nbsp; 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    }