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