    001package net.sf.cpsolver.studentsct.heuristics.selection;
    002
    003import java.util.ArrayList;
    004import java.util.HashSet;
    005import java.util.Iterator;
    006import java.util.List;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    010import net.sf.cpsolver.ifs.model.Neighbour;
    011import net.sf.cpsolver.ifs.solution.Solution;
    012import net.sf.cpsolver.ifs.solver.Solver;
    013import net.sf.cpsolver.ifs.util.DataProperties;
    014import net.sf.cpsolver.ifs.util.JProf;
    015import net.sf.cpsolver.ifs.util.Progress;
    016import net.sf.cpsolver.studentsct.StudentSectioningModel;
    017import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
    018import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
    019import net.sf.cpsolver.studentsct.model.CourseRequest;
    020import net.sf.cpsolver.studentsct.model.Enrollment;
    021import net.sf.cpsolver.studentsct.model.Request;
    022import net.sf.cpsolver.studentsct.model.Student;
    023
    024import org.apache.log4j.Logger;
    025
    026/**
    027 * Pick a student (one by one) with an incomplete schedule, try to find an
    028 * improvement, identify problematic students. <br>
    029 * <br>
    030 * For each request that does not have an assignment and that can be assined
    031 * (see {@link Student#canAssign(Request)}) a randomly selected sub-domain is
    032 * visited. For every such enrollment, a set of conflicting enrollments is
    033 * computed and a possible student that can get an alternative enrollment is
    034 * identified (if there is any). For each such move a value (the cost of moving
    035 * the problematic student somewhere else) is computed and the best possible
    036 * move is selected at the end. If there is no such move, a set of problematic
    037 * students is identified, i.e., the students whose enrollments are preventing
    038 * this student to get a request. <br>
    039 * <br>
    040 * Each student can be selected for this swap move multiple times, but only if
    041 * there is still a request that can be resolved. At the end (when there is no
    042 * other neighbour), the set of all such problematic students can be returned
    043 * using the {@link ProblemStudentsProvider} interface. <br>
    044 * <br>
    045 * Parameters: <br>
    046 * <table border='1'>
    047 * <tr>
    048 * <th>Parameter</th>
    049 * <th>Type</th>
    050 * <th>Comment</th>
    051 * </tr>
    052 * <tr>
    053 * <td>Neighbour.SwapStudentsTimeout</td>
    054 * <td>{@link Integer}</td>
    055 * <td>Timeout for each neighbour selection (in milliseconds).</td>
    056 * </tr>
    057 * <tr>
    058 * <td>Neighbour.SwapStudentsMaxValues</td>
    059 * <td>{@link Integer}</td>
    060 * <td>Limit for the number of considered values for each course request (see
    061 * {@link CourseRequest#computeRandomEnrollments(int)}).</td>
    062 * </tr>
    063 * </table>
    064 * <br>
    065 * <br>
    066 *
    067 * @version StudentSct 1.2 (Student Sectioning)<br>
    068 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    069 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    070 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    071 * <br>
    072 *          This library is free software; you can redistribute it and/or modify
    073 *          it under the terms of the GNU Lesser General Public License as
    074 *          published by the Free Software Foundation; either version 3 of the
    075 *          License, or (at your option) any later version. <br>
    076 * <br>
    077 *          This library is distributed in the hope that it will be useful, but
    078 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    079 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    080 *          Lesser General Public License for more details. <br>
    081 * <br>
    082 *          You should have received a copy of the GNU Lesser General Public
    083 *          License along with this library; if not see
    084 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    085 */
    086
    087public class SwapStudentSelection implements NeighbourSelection<Request, Enrollment>, ProblemStudentsProvider {
    088    private static Logger sLog = Logger.getLogger(SwapStudentSelection.class);
    089    private Set<Student> iProblemStudents = new HashSet<Student>();
    090    private Student iStudent = null;
    091    private Iterator<Student> iStudentsEnumeration = null;
    092    private int iTimeout = 5000;
    093    private int iMaxValues = 100;
    094    public static boolean sDebug = false;
    095    protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
    096
    097    /**
    098     * Constructor
    099     *
    100     * @param properties
    101     *            configuration
    102     */
    103    public SwapStudentSelection(DataProperties properties) {
    104        iTimeout = properties.getPropertyInt("Neighbour.SwapStudentsTimeout", iTimeout);
    105        iMaxValues = properties.getPropertyInt("Neighbour.SwapStudentsMaxValues", iMaxValues);
    106        if (properties.getProperty("Neighbour.SwapStudentsOrder") != null) {
    107            try {
    108                iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.SwapStudentsOrder"))
    109                        .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
    110            } catch (Exception e) {
    111                sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
    112            }
    113        }
    114    }
    115
    116    /** Initialization */
    117    @Override
    118    public void init(Solver<Request, Enrollment> solver) {
    119        List<Student> students = iOrder.order(((StudentSectioningModel) solver.currentSolution().getModel())
    120                .getStudents());
    121        iStudentsEnumeration = students.iterator();
    122        iProblemStudents.clear();
    123        Progress.getInstance(solver.currentSolution().getModel()).setPhase("Student swap...", students.size());
    124    }
    125
    126    /**
    127     * For each student that does not have a complete schedule, try to find a
    128     * request and a student that can be moved out of an enrollment so that the
    129     * selected student can be assigned to the selected request.
    130     */
    131    @Override
    132    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    133        if (iStudent != null && !iStudent.isComplete()) {
    134            Selection selection = getSelection(iStudent);
    135            Neighbour<Request, Enrollment> neighbour = selection.select();
    136            if (neighbour != null)
    137                return neighbour;
    138            else
    139                iProblemStudents.addAll(selection.getProblemStudents());
    140        }
    141        iStudent = null;
    142        while (iStudentsEnumeration.hasNext()) {
    143            Student student = iStudentsEnumeration.next();
    144            Progress.getInstance(solution.getModel()).incProgress();
    145            if (student.isComplete() || student.nrAssignedRequests() == 0)
    146                continue;
    147            Selection selection = getSelection(student);
    148            Neighbour<Request, Enrollment> neighbour = selection.select();
    149            if (neighbour != null) {
    150                iStudent = student;
    151                return neighbour;
    152            } else
    153                iProblemStudents.addAll(selection.getProblemStudents());
    154        }
    155        return null;
    156    }
    157
    158    /** List of problematic students */
    159    @Override
    160    public Set<Student> getProblemStudents() {
    161        return iProblemStudents;
    162    }
    163
    164    /** Selection subclass for a student */
    165    public Selection getSelection(Student student) {
    166        return new Selection(student);
    167    }
    168
    169    /** This class looks for a possible swap move for the given student */
    170    public class Selection {
    171        private Student iStudent;
    172        private long iT0, iT1;
    173        private boolean iTimeoutReached;
    174        private Enrollment iBestEnrollment;
    175        private double iBestValue;
    176        private Set<Student> iProblemStudents;
    177        private List<Enrollment> iBestSwaps;
    178
    179        /**
    180         * Constructor
    181         *
    182         * @param student
    183         *            given student
    184         */
    185        public Selection(Student student) {
    186            iStudent = student;
    187        }
    188
    189        /**
    190         * The actual selection
    191         */
    192        public SwapStudentNeighbour select() {
    193            if (sDebug)
    194                sLog.debug("select(S" + iStudent.getId() + ")");
    195            iT0 = JProf.currentTimeMillis();
    196            iTimeoutReached = false;
    197            iBestEnrollment = null;
    198            iProblemStudents = new HashSet<Student>();
    199            Double initialValue = null;
    200            for (Request request : iStudent.getRequests()) {
    201                if (initialValue == null)
    202                    initialValue = request.getModel().getTotalValue();
    203                if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
    204                    if (!iTimeoutReached) {
    205                        if (sDebug)
    206                            sLog.debug("  -- timeout reached");
    207                        iTimeoutReached = true;
    208                    }
    209                    break;
    210                }
    211                if (request.getAssignment() != null)
    212                    continue;
    213                if (!iStudent.canAssign(request))
    214                    continue;
    215                if (sDebug)
    216                    sLog.debug("  -- checking request " + request);
    217                List<Enrollment> values = null;
    218                if (iMaxValues > 0 && request instanceof CourseRequest) {
    219                    values = ((CourseRequest) request).computeRandomEnrollments(iMaxValues);
    220                } else
    221                    values = request.values();
    222                for (Enrollment enrollment : values) {
    223                    if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
    224                        if (!iTimeoutReached) {
    225                            if (sDebug)
    226                                sLog.debug("  -- timeout reached");
    227                            iTimeoutReached = true;
    228                        }
    229                        break;
    230                    }
    231                    if (sDebug)
    232                        sLog.debug("      -- enrollment " + enrollment);
    233                    Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(enrollment);
    234                    if (conflicts.contains(enrollment))
    235                        continue;
    236
    237                    double bound = enrollment.toDouble();
    238                    for (Enrollment conflict: conflicts)
    239                        bound += conflict.variable().getBound();
    240                    if (iBestEnrollment != null && bound >= iBestValue)
    241                        continue;
    242
    243                    for (Enrollment conflict: conflicts)
    244                        conflict.variable().unassign(0);
    245                    enrollment.variable().assign(0, enrollment);
    246
    247                    boolean allResolved = true;
    248                    List<Enrollment> swaps = new ArrayList<Enrollment>(conflicts.size());
    249                    for (Enrollment conflict : conflicts) {
    250                        if (sDebug)
    251                            sLog.debug("        -- conflict " + conflict);
    252                        Enrollment other = bestSwap(conflict, enrollment, iProblemStudents);
    253                        if (other == null) {
    254                            if (sDebug)
    255                                sLog.debug("          -- unable to resolve");
    256                            allResolved = false;
    257                            break;
    258                        }
    259                        other.variable().assign(0, other);
    260                        swaps.add(other);
    261                        if (sDebug)
    262                            sLog.debug("          -- can be resolved by switching to " + other.getName());
    263                    }
    264                    double value = request.getModel().getTotalValue() - initialValue;
    265
    266                    for (Enrollment other: swaps)
    267                        other.variable().unassign(0);
    268                    enrollment.variable().unassign(0);
    269                    for (Enrollment conflict: conflicts)
    270                        conflict.variable().assign(0, conflict);
    271
    272                    if (allResolved && value <= 0.0 && (iBestEnrollment == null || iBestValue > value)) {
    273                        iBestEnrollment = enrollment;
    274                        iBestValue = value;
    275                        iBestSwaps = swaps;
    276                    }
    277                }
    278            }
    279            iT1 = JProf.currentTimeMillis();
    280            if (sDebug)
    281                sLog.debug("  -- done, best enrollment is " + iBestEnrollment);
    282            if (iBestEnrollment == null) {
    283                if (iProblemStudents.isEmpty())
    284                    iProblemStudents.add(iStudent);
    285                if (sDebug)
    286                    sLog.debug("  -- problem students are: " + iProblemStudents);
    287                return null;
    288            }
    289            if (sDebug)
    290                sLog.debug("  -- value " + iBestValue);
    291            Enrollment[] assignment = new Enrollment[iStudent.getRequests().size()];
    292            int idx = 0;
    293            for (Request request : iStudent.getRequests()) {
    294                assignment[idx++] = (iBestEnrollment.getRequest().equals(request) ? iBestEnrollment
    295                        : (Enrollment) request.getAssignment());
    296            }
    297            return new SwapStudentNeighbour(iBestValue, iBestEnrollment, iBestSwaps);
    298        }
    299
    300        /** Was timeout reached during the selection */
    301        public boolean isTimeoutReached() {
    302            return iTimeoutReached;
    303        }
    304
    305        /** Time spent in the last selection */
    306        public long getTime() {
    307            return iT1 - iT0;
    308        }
    309
    310        /** The best enrollment found. */
    311        public Enrollment getBestEnrollment() {
    312            return iBestEnrollment;
    313        }
    314
    315        /** Cost of the best enrollment found */
    316        public double getBestValue() {
    317            return iBestValue;
    318        }
    319
    320        /** Set of problematic students computed in the last selection */
    321        public Set<Student> getProblemStudents() {
    322            return iProblemStudents;
    323        }
    324
    325    }
    326
    327    /**
    328     * Identify the best swap for the given student
    329     *
    330     * @param conflict
    331     *            conflicting enrollment
    332     * @param enrl
    333     *            enrollment that is visited (to be assigned to the given
    334     *            student)
    335     * @param problematicStudents
    336     *            the current set of problematic students
    337     * @return best alternative enrollment for the student of the conflicting
    338     *         enrollment
    339     */
    340    public static Enrollment bestSwap(Enrollment conflict, Enrollment enrl, Set<Student> problematicStudents) {
    341        Enrollment bestEnrollment = null;
    342        double bestValue = 0;
    343        for (Enrollment enrollment : conflict.getRequest().values()) {
    344            if (conflict.variable().getModel().inConflict(enrollment))
    345                continue;
    346            double value = enrollment.toDouble();
    347            if (bestEnrollment == null || bestValue > value) {
    348                bestEnrollment = enrollment;
    349                bestValue = value;
    350            }
    351        }
    352        if (bestEnrollment == null && problematicStudents != null) {
    353            boolean added = false;
    354            for (Enrollment enrollment : conflict.getRequest().values()) {
    355                Set<Enrollment> conflicts = conflict.variable().getModel().conflictValues(enrollment);
    356                for (Enrollment c : conflicts) {
    357                    if (enrl.getStudent().isDummy() && !c.getStudent().isDummy())
    358                        continue;
    359                    if (enrl.getStudent().equals(c.getStudent()) || conflict.getStudent().equals(c.getStudent()))
    360                        continue;
    361                    problematicStudents.add(c.getStudent());
    362                }
    363            }
    364            if (!added && !enrl.getStudent().equals(conflict.getStudent()))
    365                problematicStudents.add(conflict.getStudent());
    366        }
    367        return bestEnrollment;
    368    }
    369
    370    /** Neighbour that contains the swap */
    371    public static class SwapStudentNeighbour extends Neighbour<Request, Enrollment> {
    372        private double iValue;
    373        private Enrollment iEnrollment;
    374        private List<Enrollment> iSwaps;
    375
    376        /**
    377         * Constructor
    378         *
    379         * @param value
    380         *            cost of the move
    381         * @param enrollment
    382         *            the enrollment which is to be assigned to the given
    383         *            student
    384         * @param swaps
    385         *            enrollment swaps
    386         */
    387        public SwapStudentNeighbour(double value, Enrollment enrollment, List<Enrollment> swaps) {
    388            iValue = value;
    389            iEnrollment = enrollment;
    390            iSwaps = swaps;
    391        }
    392
    393        @Override
    394        public double value() {
    395            return iValue;
    396        }
    397
    398        /**
    399         * Perform the move. All the requeired swaps are identified and
    400         * performed as well.
    401         **/
    402        @Override
    403        public void assign(long iteration) {
    404            if (iEnrollment.variable().getAssignment() != null)
    405                iEnrollment.variable().unassign(iteration);
    406            for (Enrollment swap : iSwaps) {
    407                swap.variable().unassign(iteration);
    408            }
    409            iEnrollment.variable().assign(iteration, iEnrollment);
    410            for (Enrollment swap : iSwaps) {
    411                swap.variable().assign(iteration, swap);
    412            }
    413        }
    414
    415        @Override
    416        public String toString() {
    417            StringBuffer sb = new StringBuffer("SwSt{");
    418            sb.append(" " + iEnrollment.getRequest().getStudent());
    419            sb.append(" (" + iValue + ")");
    420            sb.append("\n " + iEnrollment.getRequest());
    421            sb.append(" " + iEnrollment);
    422            for (Enrollment swap : iSwaps) {
    423                sb.append("\n " + swap.getRequest());
    424                sb.append(" " + swap.variable().getAssignment());
    425                sb.append(" -> " + swap);
    426            }
    427            sb.append("\n}");
    428            return sb.toString();
    429        }
    430    }
    431}