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