001package org.cpsolver.studentsct.heuristics; 002 003import java.util.ArrayList; 004import java.util.List; 005import java.util.Set; 006 007import org.cpsolver.ifs.assignment.Assignment; 008import org.cpsolver.ifs.extension.ConflictStatistics; 009import org.cpsolver.ifs.extension.Extension; 010import org.cpsolver.ifs.extension.MacPropagation; 011import org.cpsolver.ifs.extension.ViolatedInitials; 012import org.cpsolver.ifs.heuristics.GeneralValueSelection; 013import org.cpsolver.ifs.heuristics.ValueSelection; 014import org.cpsolver.ifs.solution.Solution; 015import org.cpsolver.ifs.solver.Solver; 016import org.cpsolver.ifs.util.DataProperties; 017import org.cpsolver.ifs.util.ToolBox; 018import org.cpsolver.studentsct.StudentSectioningModel; 019import org.cpsolver.studentsct.model.Enrollment; 020import org.cpsolver.studentsct.model.Request; 021import org.cpsolver.studentsct.model.Student; 022 023 024/** 025 * Enrollment selection criterion. It is similar to 026 * {@link GeneralValueSelection}, however, it is not allowed to assign a 027 * enrollment to a dummy student {@link Student#isDummy()} that is conflicting 028 * with an enrollment of a real student. 029 * 030 * @version StudentSct 1.3 (Student Sectioning)<br> 031 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049public class EnrollmentSelection implements ValueSelection<Request, Enrollment> { 050 private double iRandomWalkProb = 0.0; 051 private double iInitialSelectionProb = 0.0; 052 private double iGoodSelectionProb = 0.0; 053 private int iMPPLimit = -1; 054 055 private double iWeightDeltaInitialAssignment = 0.0; 056 private double iWeightPotentialConflicts = 0.0; 057 private double iWeightWeightedCoflicts = 0.0; 058 private double iWeightCoflicts = 1.0; 059 private double iWeightValue = 0.0; 060 061 protected int iTabuSize = 0; 062 protected List<Enrollment> iTabu = null; 063 protected int iTabuPos = 0; 064 065 private boolean iMPP = false; 066 private ConflictStatistics<Request, Enrollment> iStat = null; 067 private MacPropagation<Request, Enrollment> iProp = null; 068 private ViolatedInitials<Request, Enrollment> iViolatedInitials = null; 069 070 public EnrollmentSelection() { 071 } 072 073 /** 074 * Constructor 075 * 076 * @param properties 077 * input configuration 078 */ 079 public EnrollmentSelection(DataProperties properties) { 080 iMPP = properties.getPropertyBoolean("General.MPP", false); 081 if (iMPP) { 082 iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1); 083 iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75); 084 iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0); 085 } 086 iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00); 087 iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 0.0); 088 iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0); 089 090 iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0); 091 iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0); 092 iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0); 093 iTabuSize = properties.getPropertyInt("Value.Tabu", 0); 094 if (iTabuSize > 0) 095 iTabu = new ArrayList<Enrollment>(iTabuSize); 096 } 097 098 /** Initialization */ 099 @Override 100 public void init(Solver<Request, Enrollment> solver) { 101 for (Extension<Request, Enrollment> extension : solver.getExtensions()) { 102 if (ConflictStatistics.class.isInstance(extension)) 103 iStat = (ConflictStatistics<Request, Enrollment>) extension; 104 if (MacPropagation.class.isInstance(extension)) 105 iProp = (MacPropagation<Request, Enrollment>) extension; 106 if (ViolatedInitials.class.isInstance(extension)) 107 iViolatedInitials = (ViolatedInitials<Request, Enrollment>) extension; 108 } 109 } 110 111 /** true, if it is allowed to assign given value 112 * @param assignment current assignment 113 * @param value given value 114 * @return true if it is allowed 115 **/ 116 public boolean isAllowed(Assignment<Request, Enrollment> assignment, Enrollment value, AssignmentCheck<Request, Enrollment> test) { 117 return isAllowed(assignment, value, null, test); 118 } 119 120 /** true, if it is allowed to assign given value 121 * @param assignment current assignment 122 * @param value given value 123 * @param conflicts conflicting assignments 124 * @return true if it is allowed 125 **/ 126 public boolean isAllowed(Assignment<Request, Enrollment> assignment, Enrollment value, Set<Enrollment> conflicts, AssignmentCheck<Request, Enrollment> test) { 127 if (value == null) 128 return true; 129 StudentSectioningModel model = (StudentSectioningModel) value.variable().getModel(); 130 if (model.getNrLastLikeRequests(false) == 0 || model.getNrRealRequests(false) == 0) { 131 // all students are dummy or all are real 132 if (test != null) { 133 // there is an assignment check >> check if all conflicts can be unassigned 134 if (conflicts == null) 135 conflicts = value.variable().getModel().conflictValues(assignment, value); 136 for (Enrollment conflict : conflicts) 137 if (!test.canUnassign(value, conflict, assignment)) return false; 138 } 139 return true; 140 } 141 Request request = value.variable(); 142 if (request.getStudent().isDummy()) { 143 // dummy student cannot unassign real student 144 if (conflicts == null) 145 conflicts = value.variable().getModel().conflictValues(assignment, value); 146 for (Enrollment conflict : conflicts) { 147 if (!conflict.getRequest().getStudent().isDummy()) 148 return false; 149 if (test != null && !test.canUnassign(value, conflict, assignment)) 150 return false; 151 } 152 } else { 153 // real student 154 if (conflicts == null) 155 conflicts = value.variable().getModel().conflictValues(assignment, value); 156 if (test == null) { 157 // no assignment check >> legacy behavior 158 if (conflicts.size() > (assignment.getValue(request) == null ? 1 : 0)) 159 return false; 160 } else { 161 // there is an assignment check >> check if all conflicts can be unassigned 162 for (Enrollment conflict : conflicts) 163 if (!test.canUnassign(value, conflict, assignment)) 164 return false; 165 } 166 } 167 return true; 168 } 169 170 /** Value selection */ 171 @Override 172 public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable) { 173 return selectValue(solution, selectedVariable, null); 174 } 175 176 public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable, AssignmentCheck<Request, Enrollment> test) { 177 Assignment<Request, Enrollment> assignment = solution.getAssignment(); 178 if (iMPP) { 179 if (selectedVariable.getInitialAssignment() != null) { 180 if (solution.getModel().unassignedVariables(assignment).isEmpty()) { 181 if (solution.getModel().perturbVariables(assignment).size() <= iMPPLimit) 182 iMPPLimit = solution.getModel().perturbVariables(assignment).size() - 1; 183 } 184 if (iMPPLimit >= 0 && solution.getModel().perturbVariables(assignment).size() > iMPPLimit) { 185 if (isAllowed(assignment, selectedVariable.getInitialAssignment(), test)) 186 return selectedVariable.getInitialAssignment(); 187 } 188 if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) { 189 if (isAllowed(assignment, selectedVariable.getInitialAssignment(), test)) 190 return selectedVariable.getInitialAssignment(); 191 } 192 } 193 } 194 195 List<Enrollment> values = selectedVariable.values(assignment); 196 if (ToolBox.random() <= iRandomWalkProb) { 197 Enrollment value = ToolBox.random(values); 198 if (isAllowed(assignment, value, test)) 199 return value; 200 } 201 if (iProp != null && assignment.getValue(selectedVariable) == null && ToolBox.random() <= iGoodSelectionProb) { 202 Set<Enrollment> goodValues = iProp.goodValues(assignment, selectedVariable); 203 if (!goodValues.isEmpty()) 204 values = new ArrayList<Enrollment>(goodValues); 205 } 206 if (values.size() == 1) { 207 Enrollment value = values.get(0); 208 if (isAllowed(assignment, value, test)) 209 return value; 210 else 211 return null; 212 } 213 214 List<Enrollment> bestValues = null; 215 double bestWeightedSum = 0; 216 217 for (Enrollment value : values) { 218 if (iTabu != null && iTabu.contains(value)) 219 continue; 220 if (assignment.getValue(selectedVariable) != null && assignment.getValue(selectedVariable).equals(value)) 221 continue; 222 223 Set<Enrollment> conf = solution.getModel().conflictValues(assignment, value); 224 if (conf.contains(value)) 225 continue; 226 227 if (!isAllowed(assignment, value, conf, test)) 228 continue; 229 230 double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(solution.getIteration(), conf, value)); 231 double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat.countPotentialConflicts(assignment, solution.getIteration(), value, 3)); 232 233 long deltaInitialAssignments = 0; 234 if (iMPP && iWeightDeltaInitialAssignment != 0.0) { 235 if (iViolatedInitials != null) { 236 Set<Enrollment> violations = iViolatedInitials.getViolatedInitials(value); 237 if (violations != null) { 238 for (Enrollment aValue : violations) { 239 if (assignment.getValue(aValue.variable()) == null || assignment.getValue(aValue.variable()).equals(aValue)) 240 deltaInitialAssignments += 2; 241 } 242 } 243 } 244 for (Enrollment aValue : conf) { 245 if (aValue.variable().getInitialAssignment() != null) 246 deltaInitialAssignments--; 247 } 248 if (selectedVariable.getInitialAssignment() != null 249 && !selectedVariable.getInitialAssignment().equals(value)) { 250 deltaInitialAssignments++; 251 } 252 if (iMPPLimit >= 0 && (solution.getModel().perturbVariables(assignment).size() + deltaInitialAssignments) > iMPPLimit) 253 continue; 254 } 255 256 double val = value.toDouble(assignment); 257 for (Enrollment c: conf) 258 val -= c.toDouble(assignment); 259 260 double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments) 261 + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts) 262 + (iWeightCoflicts * conf.size()) 263 + (iWeightValue * val); 264 265 if (bestValues == null || bestWeightedSum > weightedSum) { 266 bestWeightedSum = weightedSum; 267 if (bestValues == null) 268 bestValues = new ArrayList<Enrollment>(); 269 else 270 bestValues.clear(); 271 bestValues.add(value); 272 } else { 273 if (bestWeightedSum == weightedSum) 274 bestValues.add(value); 275 } 276 } 277 278 Enrollment selectedValue = (bestValues == null ? null : ToolBox.random(bestValues)); 279 if (selectedValue == null) 280 selectedValue = ToolBox.random(values); 281 if (iTabu != null) { 282 if (iTabu.size() == iTabuPos) 283 iTabu.add(selectedValue); 284 else 285 iTabu.set(iTabuPos, selectedValue); 286 iTabuPos = (iTabuPos + 1) % iTabuSize; 287 } 288 return (bestValues == null ? null : selectedValue); 289 } 290 291}