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