    001package org.cpsolver.studentsct.heuristics.selection;
    002
    003import java.util.ArrayList;
    004import java.util.HashMap;
    005import java.util.Iterator;
    006import java.util.List;
    007import java.util.Map;
    008
    009import org.cpsolver.ifs.assignment.Assignment;
    010import org.cpsolver.ifs.heuristics.NeighbourSelection;
    011import org.cpsolver.ifs.model.Neighbour;
    012import org.cpsolver.ifs.solution.Solution;
    013import org.cpsolver.ifs.solver.Solver;
    014import org.cpsolver.ifs.util.DataProperties;
    015import org.cpsolver.ifs.util.Progress;
    016import org.cpsolver.ifs.util.ToolBox;
    017import org.cpsolver.studentsct.StudentSectioningModel;
    018import org.cpsolver.studentsct.model.Enrollment;
    019import org.cpsolver.studentsct.model.Request;
    020import org.cpsolver.studentsct.model.Request.RequestPriority;
    021import org.cpsolver.studentsct.model.Student;
    022import org.cpsolver.studentsct.model.Student.StudentPriority;
    023
    024
    025/**
    026 * Random unassignment of some (randomly selected) students.
    027 *
    028 * <br>
    029 * <br>
    030 * In each step a student is randomly selected with the given probabilty. Null
    031 * is returned otherwise (controll is passed to the following
    032 * {@link NeighbourSelection}).
    033 *
    034 * <br>
    035 * <br>
    036 * Parameters: <br>
    037 * <table border='1' summary='Related Solver Parameters'>
    038 * <tr>
    039 * <th>Parameter</th>
    040 * <th>Type</th>
    041 * <th>Comment</th>
    042 * </tr>
    043 * <tr>
    044 * <td>Neighbour.RandomUnassignmentProb</td>
    045 * <td>{@link Double}</td>
    046 * <td>Probability of a random selection of a student.</td>
    047 * </tr>
    048 * </table>
    049 * <br>
    050 * <br>
    051 *
    052 * @version StudentSct 1.3 (Student Sectioning)<br>
    053 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    054 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    055 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    056 * <br>
    057 *          This library is free software; you can redistribute it and/or modify
    058 *          it under the terms of the GNU Lesser General Public License as
    059 *          published by the Free Software Foundation; either version 3 of the
    060 *          License, or (at your option) any later version. <br>
    061 * <br>
    062 *          This library is distributed in the hope that it will be useful, but
    063 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    064 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    065 *          Lesser General Public License for more details. <br>
    066 * <br>
    067 *          You should have received a copy of the GNU Lesser General Public
    068 *          License along with this library; if not see
    069 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    070 */
    071public class RandomUnassignmentSelection implements NeighbourSelection<Request, Enrollment> {
    072    private List<Student> iStudents = null;
    073    protected double iRandom = 0.5;
    074    private RequestPriority iPriority;
    075
    076    /**
    077     * Constructor
    078     *
    079     * @param properties
    080     *            configuration
    081     */
    082    public RandomUnassignmentSelection(DataProperties properties, RequestPriority priority) {
    083        iRandom = properties.getPropertyDouble("Neighbour.RandomUnassignmentProb", iRandom);
    084        iPriority = priority;
    085    }
    086
    087    public RandomUnassignmentSelection(DataProperties properties) {
    088        this(properties, RequestPriority.Important);
    089    }
    090
    091    /**
    092     * Initialization
    093     */
    094    @Override
    095    public void init(Solver<Request, Enrollment> solver) {
    096        iStudents = ((StudentSectioningModel) solver.currentSolution().getModel()).getStudents();
    097        Progress.getInstance(solver.currentSolution().getModel()).setPhase("Random unassignment...", 1);
    098    }
    099
    100    /**
    101     * With the given probabilty, a student is randomly selected to be
    102     * unassigned. Null is returned otherwise.
    103     */
    104    @Override
    105    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    106        if (Math.random() < iRandom) {
    107            Student student = ToolBox.random(iStudents);
    108            return new UnassignStudentNeighbour(student, solution.getAssignment(), iPriority);
    109        }
    110        Progress.getInstance(solution.getModel()).incProgress();
    111        return null;
    112    }
    113
    114    /** Unassignment of all requests of a student */
    115    public static class UnassignStudentNeighbour implements Neighbour<Request, Enrollment> {
    116        private Student iStudent = null;
    117        private List<Request> iRequests = new ArrayList<Request>();
    118        private RequestPriority iPriority;
    119
    120        /**
    121         * Constructor
    122         *
    123         * @param student
    124         *            a student to be unassigned
    125         */
    126        public UnassignStudentNeighbour(Student student, Assignment<Request, Enrollment> assignment, RequestPriority priority) {
    127            iStudent = student;
    128            iPriority = priority;
    129            float credit = 0f;
    130            for (Request request : iStudent.getRequests()) {
    131                Enrollment enrollment = assignment.getValue(request);
    132                if (canUnassign(enrollment))
    133                    iRequests.add(request);
    134                else if (enrollment != null)
    135                    credit += enrollment.getCredit();
    136            }
    137            if (credit < iStudent.getMinCredit()) {
    138                for (Iterator<Request> i = iRequests.iterator(); i.hasNext(); ) {
    139                    Request request = i.next();
    140                    Enrollment enrollment = assignment.getValue(request);
    141                    if (enrollment != null && enrollment.getCredit() > 0f) {
    142                        credit += enrollment.getCredit();
    143                        i.remove();
    144                    }
    145                    if (credit >= iStudent.getMaxCredit()) break;
    146                }
    147            }
    148        }
    149
    150        /**
    151         * Check if the given enrollment can be unassigned
    152         * @param enrollment given enrollment
    153         * @return if running MPP, do not unassign initial enrollments
    154         */
    155        public boolean canUnassign(Enrollment enrollment) {
    156            if (enrollment == null) return false;
    157            if (enrollment.getRequest().isMPP() && enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false;
    158            if (enrollment.getStudent().getPriority().ordinal() < StudentPriority.Normal.ordinal()) return false;
    159            if (iPriority.isCritical(enrollment.getRequest())) return false;
    160            return true;
    161        }
    162
    163        @Override
    164        public double value(Assignment<Request, Enrollment> assignment) {
    165            double val = 0;
    166            for (Request request : iRequests) {
    167                Enrollment enrollment = assignment.getValue(request);
    168                if (enrollment != null)
    169                    val -= enrollment.toDouble(assignment);
    170            }
    171            return val;
    172        }
    173
    174        /** All requests of the given student are unassigned */
    175        @Override
    176        public void assign(Assignment<Request, Enrollment> assignment, long iteration) {
    177            for (Request request : iRequests)
    178                assignment.unassign(iteration, request);
    179        }
    180
    181        @Override
    182        public String toString() {
    183            StringBuffer sb = new StringBuffer("Un{");
    184            sb.append(" " + iStudent);
    185            sb.append(" }");
    186            return sb.toString();
    187        }
    188
    189        @Override
    190        public Map<Request, Enrollment> assignments() {
    191            Map<Request, Enrollment> ret = new HashMap<Request, Enrollment>();
    192            for (Request request : iRequests)
    193                ret.put(request, null);
    194            return ret;
    195        }
    196
    197    }
    198
    199}