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