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", 1.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) { 117 return isAllowed(assignment, value, null); 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) { 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 return true; 132 Request request = value.variable(); 133 if (request.getStudent().isDummy()) { 134 if (conflicts == null) 135 conflicts = value.variable().getModel().conflictValues(assignment, value); 136 for (Enrollment conflict : conflicts) { 137 if (!conflict.getRequest().getStudent().isDummy()) 138 return false; 139 } 140 } else { 141 if (conflicts == null) 142 conflicts = value.variable().getModel().conflictValues(assignment, value); 143 if (conflicts.size() > (assignment.getValue(request) == null ? 1 : 0)) 144 return false; 145 } 146 return true; 147 } 148 149 /** Value selection */ 150 @Override 151 public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable) { 152 Assignment<Request, Enrollment> assignment = solution.getAssignment(); 153 if (iMPP) { 154 if (selectedVariable.getInitialAssignment() != null) { 155 if (solution.getModel().unassignedVariables(assignment).isEmpty()) { 156 if (solution.getModel().perturbVariables(assignment).size() <= iMPPLimit) 157 iMPPLimit = solution.getModel().perturbVariables(assignment).size() - 1; 158 } 159 if (iMPPLimit >= 0 && solution.getModel().perturbVariables(assignment).size() > iMPPLimit) { 160 if (isAllowed(assignment, selectedVariable.getInitialAssignment())) 161 return selectedVariable.getInitialAssignment(); 162 } 163 if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) { 164 if (isAllowed(assignment, selectedVariable.getInitialAssignment())) 165 return selectedVariable.getInitialAssignment(); 166 } 167 } 168 } 169 170 List<Enrollment> values = selectedVariable.values(assignment); 171 if (ToolBox.random() <= iRandomWalkProb) { 172 Enrollment value = ToolBox.random(values); 173 if (isAllowed(assignment, value)) 174 return value; 175 } 176 if (iProp != null && assignment.getValue(selectedVariable) == null && ToolBox.random() <= iGoodSelectionProb) { 177 Set<Enrollment> goodValues = iProp.goodValues(assignment, selectedVariable); 178 if (!goodValues.isEmpty()) 179 values = new ArrayList<Enrollment>(goodValues); 180 } 181 if (values.size() == 1) { 182 Enrollment value = values.get(0); 183 if (isAllowed(assignment, value)) 184 return value; 185 else 186 return null; 187 } 188 189 List<Enrollment> bestValues = null; 190 double bestWeightedSum = 0; 191 192 for (Enrollment value : values) { 193 if (iTabu != null && iTabu.contains(value)) 194 continue; 195 if (assignment.getValue(selectedVariable) != null && assignment.getValue(selectedVariable).equals(value)) 196 continue; 197 198 Set<Enrollment> conf = solution.getModel().conflictValues(assignment, value); 199 if (conf.contains(value)) 200 continue; 201 202 if (!isAllowed(assignment, value, conf)) 203 continue; 204 205 double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(solution.getIteration(), conf, value)); 206 double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat.countPotentialConflicts(assignment, solution.getIteration(), value, 3)); 207 208 long deltaInitialAssignments = 0; 209 if (iMPP && iWeightDeltaInitialAssignment != 0.0) { 210 if (iViolatedInitials != null) { 211 Set<Enrollment> violations = iViolatedInitials.getViolatedInitials(value); 212 if (violations != null) { 213 for (Enrollment aValue : violations) { 214 if (assignment.getValue(aValue.variable()) == null || assignment.getValue(aValue.variable()).equals(aValue)) 215 deltaInitialAssignments += 2; 216 } 217 } 218 } 219 for (Enrollment aValue : conf) { 220 if (aValue.variable().getInitialAssignment() != null) 221 deltaInitialAssignments--; 222 } 223 if (selectedVariable.getInitialAssignment() != null 224 && !selectedVariable.getInitialAssignment().equals(value)) { 225 deltaInitialAssignments++; 226 } 227 if (iMPPLimit >= 0 && (solution.getModel().perturbVariables(assignment).size() + deltaInitialAssignments) > iMPPLimit) 228 continue; 229 } 230 231 double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments) 232 + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts) 233 + (iWeightCoflicts * conf.size()) 234 + (iWeightValue * value.toDouble(assignment)); 235 236 if (bestValues == null || bestWeightedSum > weightedSum) { 237 bestWeightedSum = weightedSum; 238 if (bestValues == null) 239 bestValues = new ArrayList<Enrollment>(); 240 else 241 bestValues.clear(); 242 bestValues.add(value); 243 } else { 244 if (bestWeightedSum == weightedSum) 245 bestValues.add(value); 246 } 247 } 248 249 Enrollment selectedValue = (bestValues == null ? null : ToolBox.random(bestValues)); 250 if (selectedValue == null) 251 selectedValue = ToolBox.random(values); 252 if (iTabu != null) { 253 if (iTabu.size() == iTabuPos) 254 iTabu.add(selectedValue); 255 else 256 iTabu.set(iTabuPos, selectedValue); 257 iTabuPos = (iTabuPos + 1) % iTabuSize; 258 } 259 return (bestValues == null ? null : selectedValue); 260 } 261 262}