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