    001package net.sf.cpsolver.studentsct.check;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Collections;
    006import java.util.Comparator;
    007import java.util.HashSet;
    008import java.util.HashMap;
    009import java.util.Iterator;
    010import java.util.List;
    011import java.util.Map;
    012import java.util.TreeSet;
    013
    014import net.sf.cpsolver.ifs.util.CSVFile;
    015import net.sf.cpsolver.studentsct.StudentSectioningModel;
    016import net.sf.cpsolver.studentsct.model.Assignment;
    017import net.sf.cpsolver.studentsct.model.Course;
    018import net.sf.cpsolver.studentsct.model.CourseRequest;
    019import net.sf.cpsolver.studentsct.model.Enrollment;
    020import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
    021import net.sf.cpsolver.studentsct.model.Request;
    022import net.sf.cpsolver.studentsct.model.Section;
    023import 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 Tomáš Müller<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 */
    081public 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}