    001package org.cpsolver.studentsct.heuristics.selection;
    002
    003import java.text.DecimalFormat;
    004import java.util.ArrayList;
    005import java.util.Collection;
    006import java.util.Collections;
    007import java.util.ConcurrentModificationException;
    008import java.util.HashMap;
    009import java.util.HashSet;
    010import java.util.LinkedList;
    011import java.util.List;
    012import java.util.ListIterator;
    013import java.util.Map;
    014import java.util.Set;
    015
    016
    017import org.apache.logging.log4j.Logger;
    018import org.cpsolver.ifs.assignment.Assignment;
    019import org.cpsolver.ifs.heuristics.NeighbourSelection;
    020import org.cpsolver.ifs.model.InfoProvider;
    021import org.cpsolver.ifs.model.Neighbour;
    022import org.cpsolver.ifs.solution.Solution;
    023import org.cpsolver.ifs.solver.Solver;
    024import org.cpsolver.ifs.solver.SolverListener;
    025import org.cpsolver.ifs.util.DataProperties;
    026import org.cpsolver.ifs.util.JProf;
    027import org.cpsolver.ifs.util.Progress;
    028import org.cpsolver.studentsct.StudentSectioningModel;
    029import org.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
    030import org.cpsolver.studentsct.heuristics.studentord.StudentOrder;
    031import org.cpsolver.studentsct.model.Course;
    032import org.cpsolver.studentsct.model.CourseRequest;
    033import org.cpsolver.studentsct.model.Enrollment;
    034import org.cpsolver.studentsct.model.Request;
    035import org.cpsolver.studentsct.model.Student;
    036import org.cpsolver.studentsct.model.Student.StudentPriority;
    037
    038/**
    039 * Pick a student (one by one) with an incomplete schedule, try to find an
    040 * improvement, identify problematic students. <br>
    041 * <br>
    042 * For each request that does not have an assignment and that can be assined
    043 * (see {@link Student#canAssign(Assignment, Request)}) a randomly selected sub-domain is
    044 * visited. For every such enrollment, a set of conflicting enrollments is
    045 * computed and a possible student that can get an alternative enrollment is
    046 * identified (if there is any). For each such move a value (the cost of moving
    047 * the problematic student somewhere else) is computed and the best possible
    048 * move is selected at the end. If there is no such move, a set of problematic
    049 * students is identified, i.e., the students whose enrollments are preventing
    050 * this student to get a request. <br>
    051 * <br>
    052 * Each student can be selected for this swap move multiple times, but only if
    053 * there is still a request that can be resolved. At the end (when there is no
    054 * other neighbour), the set of all such problematic students can be returned
    055 * using the {@link ProblemStudentsProvider} interface. <br>
    056 * <br>
    057 * Parameters: <br>
    058 * <table border='1'><caption>Related Solver Parameters</caption>
    059 * <tr>
    060 * <th>Parameter</th>
    061 * <th>Type</th>
    062 * <th>Comment</th>
    063 * </tr>
    064 * <tr>
    065 * <td>Neighbour.SwapStudentsTimeout</td>
    066 * <td>{@link Integer}</td>
    067 * <td>Timeout for each neighbour selection (in milliseconds).</td>
    068 * </tr>
    069 * <tr>
    070 * <td>Neighbour.SwapStudentsMaxValues</td>
    071 * <td>{@link Integer}</td>
    072 * <td>Limit for the number of considered values for each course request (see
    073 * {@link CourseRequest#computeRandomEnrollments(Assignment, int)}).</td>
    074 * </tr>
    075 * </table>
    076 * <br>
    077 * <br>
    078 *
    079 * @author  Tomáš Müller
    080 * @version StudentSct 1.3 (Student Sectioning)<br>
    081 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    082 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    083 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    084 * <br>
    085 *          This library is free software; you can redistribute it and/or modify
    086 *          it under the terms of the GNU Lesser General Public License as
    087 *          published by the Free Software Foundation; either version 3 of the
    088 *          License, or (at your option) any later version. <br>
    089 * <br>
    090 *          This library is distributed in the hope that it will be useful, but
    091 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    092 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    093 *          Lesser General Public License for more details. <br>
    094 * <br>
    095 *          You should have received a copy of the GNU Lesser General Public
    096 *          License along with this library; if not see
    097 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    098 */
    099
    100public class SwapStudentSelection implements NeighbourSelection<Request, Enrollment>, ProblemStudentsProvider, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> {
    101    private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(SwapStudentSelection.class);
    102    private Set<Student> iProblemStudents = Collections.synchronizedSet(new HashSet<Student>());
    103    private LinkedList<Student> iStudents = null;
    104    private static DecimalFormat sDF = new DecimalFormat("0.00");
    105    private int iTimeout = 5000;
    106    private int iMaxValues = 100;
    107    public static boolean sDebug = false;
    108    protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
    109    private boolean iPreferPriorityStudents = true;
    110    protected Map<Student, Integer> iFailedCounter = new HashMap<Student, Integer>();
    111
    112    protected long iNbrIterations = 0;
    113    protected long iTotalTime = 0;
    114    protected long iNbrTimeoutReached = 0;
    115    protected long iNbrNoSolution = 0;
    116    protected long iNbrStudents = 0;
    117
    118    /**
    119     * Constructor
    120     *
    121     * @param properties
    122     *            configuration
    123     */
    124    public SwapStudentSelection(DataProperties properties) {
    125        iTimeout = properties.getPropertyInt("Neighbour.SwapStudentsTimeout", iTimeout);
    126        iMaxValues = properties.getPropertyInt("Neighbour.SwapStudentsMaxValues", iMaxValues);
    127        if (properties.getProperty("Neighbour.SwapStudentsOrder") != null) {
    128            try {
    129                iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.SwapStudentsOrder"))
    130                        .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
    131            } catch (Exception e) {
    132                sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
    133            }
    134        }
    135        iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true);
    136    }
    137
    138    /** Initialization */
    139    @Override
    140    public void init(Solver<Request, Enrollment> solver) {
    141        List<Student> students = iOrder.order(((StudentSectioningModel) solver.currentSolution().getModel()).getStudents());
    142        iStudents = new LinkedList<Student>(students);
    143        iProblemStudents.clear();
    144        iFailedCounter.clear();
    145        Progress.getInstance(solver.currentSolution().getModel()).setPhase("Student swap...", students.size());
    146
    147        iNbrIterations = 0;
    148        iNbrTimeoutReached = 0;
    149        iNbrNoSolution = 0;
    150        iTotalTime = 0;
    151        iNbrStudents = iStudents.size();
    152    }
    153
    154    protected synchronized Student nextStudent() {
    155        return iStudents.poll();
    156    }
    157
    158    public synchronized void addStudent(Student student) {
    159        if (iStudents != null && student != null && !student.isDummy()) {
    160            Integer failed = iFailedCounter.getOrDefault(student, 0);
    161            iFailedCounter.put(student, 1 + failed);
    162            if (failed >= 10) return;
    163            if (student.getPriority().ordinal() < StudentPriority.Normal.ordinal()) {
    164                for (ListIterator<Student> i = iStudents.listIterator(); i.hasNext();) {
    165                    Student s = i.next();
    166                    if (s.getPriority().compareTo(student.getPriority()) > 0) {
    167                        i.previous(); // go one back
    168                        i.add(student);
    169                        return;
    170                    }
    171                }
    172            }
    173            iStudents.add(student);
    174        }
    175    }
    176
    177    /**
    178     * For each student that does not have a complete schedule, try to find a
    179     * request and a student that can be moved out of an enrollment so that the
    180     * selected student can be assigned to the selected request.
    181     */
    182    @Override
    183    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    184        Student student = null;
    185        while ((student = nextStudent()) != null) {
    186            Progress p = Progress.getInstance(solution.getModel());
    187            p.setProgress(iNbrStudents - iStudents.size());
    188            if (p.getProgress() > 2.0 * p.getProgressMax()) return null;
    189            if (student.isComplete(solution.getAssignment()) || student.nrAssignedRequests(solution.getAssignment()) == 0)
    190                continue;
    191            for (int i = 0; i < 5; i++) {
    192                try {
    193                    Selection selection = getSelection(solution.getAssignment(), student);
    194                    Neighbour<Request, Enrollment> neighbour = selection.select();
    195                    if (neighbour != null) {
    196                        addStudent(student);
    197                        return neighbour;
    198                    } else
    199                        iProblemStudents.addAll(selection.getProblemStudents());
    200                    break;
    201                } catch (ConcurrentModificationException e) {}
    202            }
    203        }
    204        return null;
    205    }
    206
    207    /** List of problematic students */
    208    @Override
    209    public Set<Student> getProblemStudents() {
    210        return iProblemStudents;
    211    }
    212
    213    /** Selection subclass for a student
    214     * @param assignment current assignment
    215     * @param student selected student
    216     * @return swap student selection
    217     **/
    218    public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) {
    219        return new Selection(student, assignment);
    220    }
    221
    222    /** This class looks for a possible swap move for the given student */
    223    public class Selection {
    224        private Student iStudent;
    225        private long iT0, iT1;
    226        private boolean iTimeoutReached;
    227        private Enrollment iBestEnrollment;
    228        private double iBestValue;
    229        private Set<Student> iProblemStudents;
    230        private List<Enrollment> iBestSwaps;
    231        private Assignment<Request, Enrollment> iAssignment;
    232
    233        /**
    234         * Constructor
    235         *
    236         * @param assignment current assignment
    237         * @param student
    238         *            given student
    239         */
    240        public Selection(Student student, Assignment<Request, Enrollment> assignment) {
    241            iStudent = student;
    242            iAssignment = assignment;
    243        }
    244
    245        /**
    246         * Check if the given conflicting enrollment can be unassigned
    247         * @param conflict given enrollment
    248         * @return if running MPP, do not unassign initial enrollments
    249         */
    250        public boolean canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request, Enrollment> assignment) {
    251            if (conflict.getRequest().isMPP() && conflict.equals(conflict.getRequest().getInitialAssignment()) &&
    252                    !enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false;
    253            if (conflict.getRequest() instanceof CourseRequest && ((CourseRequest)conflict.getRequest()).getFixedValue() != null) return false;
    254            if (conflict.getRequest().getStudent().hasMinCredit()) {
    255                float credit = conflict.getRequest().getStudent().getAssignedCredit(assignment) - conflict.getCredit();
    256                if (credit < conflict.getRequest().getStudent().getMinCredit()) return false;
    257            }
    258            if (!conflict.getRequest().isAlternative() && conflict.getRequest().getRequestPriority().isHigher(enrollment.getRequest())) return false;
    259            if (iPreferPriorityStudents || conflict.getRequest().getRequestPriority().isSame(enrollment.getRequest())) {
    260                if (conflict.getStudent().getPriority().isHigher(enrollment.getStudent())) return false;
    261            }
    262            return true;
    263        }
    264
    265        /**
    266         * The actual selection
    267         * @return student swap neighbour
    268         */
    269        public SwapStudentNeighbour select() {
    270            if (sDebug)
    271                sLog.debug("select(S" + iStudent.getId() + ")");
    272            iT0 = JProf.currentTimeMillis();
    273            iTimeoutReached = false;
    274            iBestEnrollment = null;
    275            iProblemStudents = new HashSet<Student>();
    276            Double initialValue = null;
    277            for (Request request : iStudent.getRequests()) {
    278                if (initialValue == null)
    279                    initialValue = request.getModel().getTotalValue(iAssignment);
    280                if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
    281                    if (!iTimeoutReached) {
    282                        if (sDebug)
    283                            sLog.debug("  -- timeout reached");
    284                        iTimeoutReached = true;
    285                    }
    286                    break;
    287                }
    288                if (iAssignment.getValue(request) != null)
    289                    continue;
    290                if (!iStudent.canAssign(iAssignment, request))
    291                    continue;
    292                if (sDebug)
    293                    sLog.debug("  -- checking request " + request);
    294                List<Enrollment> values = null;
    295                if (iMaxValues > 0 && request instanceof CourseRequest) {
    296                    values = ((CourseRequest) request).computeRandomEnrollments(iAssignment, iMaxValues);
    297                } else
    298                    values = request.values(iAssignment);
    299                values: for (Enrollment enrollment : values) {
    300                    // do not try to assign an enrollment that requires a parent course that is not assigned
    301                    if (enrollment.getCourse() != null && enrollment.getCourse().getParent() != null) {
    302                        Course parent = enrollment.getCourse().getParent();
    303                        for (Request r: iStudent.getRequests()) {
    304                            if (r.hasCourse(parent)) {
    305                                Enrollment e = iAssignment.getValue(r);
    306                                if (e == null || !parent.equals(e.getCourse())) continue values;
    307                            }
    308                        }
    309                    }
    310                    if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
    311                        if (!iTimeoutReached) {
    312                            if (sDebug)
    313                                sLog.debug("  -- timeout reached");
    314                            iTimeoutReached = true;
    315                        }
    316                        break;
    317                    }
    318                    if (sDebug)
    319                        sLog.debug("      -- enrollment " + enrollment);
    320                    Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(iAssignment, enrollment);
    321                    if (conflicts.contains(enrollment))
    322                        continue;
    323
    324                    double bound = enrollment.toDouble(iAssignment);
    325                    for (Enrollment conflict: conflicts) {
    326                        bound += conflict.variable().getBound();
    327                        if (!canUnassign(enrollment, conflict, iAssignment)) continue values;
    328                    }
    329                    if (iBestEnrollment != null && bound >= iBestValue)
    330                        continue;
    331
    332                    for (Enrollment conflict: conflicts)
    333                        iAssignment.unassign(0, conflict.variable());
    334                    iAssignment.assign(0, enrollment);
    335
    336                    boolean allResolved = true;
    337                    List<Enrollment> swaps = new ArrayList<Enrollment>(conflicts.size());
    338                    for (Enrollment conflict : conflicts) {
    339                        if (sDebug)
    340                            sLog.debug("        -- conflict " + conflict);
    341                        Enrollment other = bestSwap(iAssignment, conflict, enrollment, iProblemStudents);
    342                        if (other == null) {
    343                            if (sDebug)
    344                                sLog.debug("          -- unable to resolve");
    345                            allResolved = false;
    346                            break;
    347                        }
    348                        iAssignment.assign(0, other);
    349                        swaps.add(other);
    350                        if (sDebug)
    351                            sLog.debug("          -- can be resolved by switching to " + other.getName());
    352                    }
    353                    double value = request.getModel().getTotalValue(iAssignment) - initialValue;
    354
    355                    for (Enrollment other: swaps)
    356                        iAssignment.unassign(0, other.variable());
    357                    iAssignment.unassign(0, enrollment.variable());
    358                    for (Enrollment conflict: conflicts)
    359                        iAssignment.assign(0, conflict);
    360
    361                    if (allResolved && value <= 0.0 && (iBestEnrollment == null || iBestValue > value)) {
    362                        iBestEnrollment = enrollment;
    363                        iBestValue = value;
    364                        iBestSwaps = swaps;
    365                    }
    366                }
    367            }
    368            iT1 = JProf.currentTimeMillis();
    369
    370            iNbrIterations ++;
    371            iTotalTime += (iT1 - iT0);
    372            if (iTimeoutReached) iNbrTimeoutReached ++;
    373            if (iBestEnrollment == null) iNbrNoSolution ++;
    374
    375            if (sDebug)
    376                sLog.debug("  -- done, best enrollment is " + iBestEnrollment);
    377            if (iBestEnrollment == null) {
    378                if (iProblemStudents.isEmpty())
    379                    iProblemStudents.add(iStudent);
    380                if (sDebug)
    381                    sLog.debug("  -- problem students are: " + iProblemStudents);
    382                return null;
    383            }
    384            if (sDebug)
    385                sLog.debug("  -- value " + iBestValue);
    386            Enrollment[] assignment = new Enrollment[iStudent.getRequests().size()];
    387            int idx = 0;
    388            for (Request request : iStudent.getRequests()) {
    389                assignment[idx++] = (iBestEnrollment.getRequest().equals(request) ? iBestEnrollment
    390                        : (Enrollment) request.getAssignment(iAssignment));
    391            }
    392            return new SwapStudentNeighbour(iBestValue, iBestEnrollment, iBestSwaps);
    393        }
    394
    395        /** Was timeout reached during the selection
    396         * @return was timeout reached
    397         **/
    398        public boolean isTimeoutReached() {
    399            return iTimeoutReached;
    400        }
    401
    402        /** Time spent in the last selection
    403         * @return search time
    404         **/
    405        public long getTime() {
    406            return iT1 - iT0;
    407        }
    408
    409        /** The best enrollment found.
    410         * @return best enrollment
    411         **/
    412        public Enrollment getBestEnrollment() {
    413            return iBestEnrollment;
    414        }
    415
    416        /** Cost of the best enrollment found
    417         * @return best value
    418         **/
    419        public double getBestValue() {
    420            return iBestValue;
    421        }
    422
    423        /** Set of problematic students computed in the last selection
    424         * @return identified problematic students
    425         **/
    426        public Set<Student> getProblemStudents() {
    427            return iProblemStudents;
    428        }
    429
    430    }
    431
    432    /**
    433     * Identify the best swap for the given student
    434     *
    435     * @param assignment current assignment
    436     * @param conflict
    437     *            conflicting enrollment
    438     * @param enrl
    439     *            enrollment that is visited (to be assigned to the given
    440     *            student)
    441     * @param problematicStudents
    442     *            the current set of problematic students
    443     * @return best alternative enrollment for the student of the conflicting
    444     *         enrollment
    445     */
    446    public static Enrollment bestSwap(Assignment<Request, Enrollment> assignment, Enrollment conflict, Enrollment enrl, Set<Student> problematicStudents) {
    447        Enrollment bestEnrollment = null;
    448        double bestValue = 0;
    449        for (Enrollment enrollment : conflict.getRequest().values(assignment)) {
    450            if (conflict.variable().getModel().inConflict(assignment, enrollment))
    451                continue;
    452            double value = enrollment.toDouble(assignment);
    453            if (bestEnrollment == null || bestValue > value) {
    454                bestEnrollment = enrollment;
    455                bestValue = value;
    456            }
    457        }
    458        if (bestEnrollment == null && problematicStudents != null) {
    459            boolean added = false;
    460            for (Enrollment enrollment : conflict.getRequest().values(assignment)) {
    461                Set<Enrollment> conflicts = conflict.variable().getModel().conflictValues(assignment, enrollment);
    462                for (Enrollment c : conflicts) {
    463                    if (enrl.getStudent().isDummy() && !c.getStudent().isDummy())
    464                        continue;
    465                    if (enrl.getStudent().equals(c.getStudent()) || conflict.getStudent().equals(c.getStudent()))
    466                        continue;
    467                    problematicStudents.add(c.getStudent());
    468                }
    469            }
    470            if (!added && !enrl.getStudent().equals(conflict.getStudent()))
    471                problematicStudents.add(conflict.getStudent());
    472        }
    473        return bestEnrollment;
    474    }
    475
    476    /** Neighbour that contains the swap */
    477    public static class SwapStudentNeighbour implements Neighbour<Request, Enrollment> {
    478        private double iValue;
    479        private Enrollment iEnrollment;
    480        private List<Enrollment> iSwaps;
    481
    482        /**
    483         * Constructor
    484         *
    485         * @param value
    486         *            cost of the move
    487         * @param enrollment
    488         *            the enrollment which is to be assigned to the given
    489         *            student
    490         * @param swaps
    491         *            enrollment swaps
    492         */
    493        public SwapStudentNeighbour(double value, Enrollment enrollment, List<Enrollment> swaps) {
    494            iValue = value;
    495            iEnrollment = enrollment;
    496            iSwaps = swaps;
    497        }
    498
    499        @Override
    500        public double value(Assignment<Request, Enrollment> assignment) {
    501            return iValue;
    502        }
    503
    504        public Student getStudent() { return iEnrollment.getStudent(); }
    505
    506        /**
    507         * Perform the move. All the requeired swaps are identified and
    508         * performed as well.
    509         **/
    510        @Override
    511        public void assign(Assignment<Request, Enrollment> assignment, long iteration) {
    512            assignment.unassign(iteration, iEnrollment.variable());
    513            for (Enrollment swap : iSwaps) {
    514                assignment.unassign(iteration, swap.variable(), swap);
    515            }
    516            assignment.assign(iteration, iEnrollment);
    517            for (Enrollment swap : iSwaps) {
    518                assignment.assign(iteration, swap);
    519            }
    520        }
    521
    522        @Override
    523        public String toString() {
    524            StringBuffer sb = new StringBuffer("SwSt{");
    525            sb.append(" " + iEnrollment.getRequest().getStudent());
    526            sb.append(" (" + iValue + ")");
    527            sb.append("\n " + iEnrollment.getRequest());
    528            sb.append(" " + iEnrollment);
    529            for (Enrollment swap : iSwaps) {
    530                sb.append("\n " + swap.getRequest());
    531                sb.append(" -> " + swap);
    532            }
    533            sb.append("\n}");
    534            return sb.toString();
    535        }
    536
    537        @Override
    538        public Map<Request, Enrollment> assignments() {
    539            Map<Request, Enrollment> ret = new HashMap<Request, Enrollment>();
    540            ret.put(iEnrollment.variable(), iEnrollment);
    541            for (Enrollment swap : iSwaps)
    542                ret.put(swap.variable(), swap);
    543            return ret;
    544        }
    545    }
    546
    547    @Override
    548    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
    549        if (iNbrIterations > 0)
    550            info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" +
    551                    iNbrIterations + " iterations, " +
    552                    (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") +
    553                    sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iTimeout / 1000.0) + " seconds reached)");
    554    }
    555
    556    @Override
    557    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
    558    }
    559
    560    @Override
    561    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
    562        return false;
    563    }
    564    @Override
    565    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
    566        return false;
    567    }
    568    @Override
    569    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    570        return false;
    571    }
    572    @Override
    573    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    574        if (neighbour instanceof SwapStudentNeighbour)
    575            addStudent(((SwapStudentNeighbour)neighbour).getStudent());
    576    }
    577}