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