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