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}