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}