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}