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