001 package net.sf.cpsolver.studentsct.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.List;
005 import java.util.Set;
006
007 import net.sf.cpsolver.ifs.extension.ConflictStatistics;
008 import net.sf.cpsolver.ifs.extension.Extension;
009 import net.sf.cpsolver.ifs.extension.MacPropagation;
010 import net.sf.cpsolver.ifs.extension.ViolatedInitials;
011 import net.sf.cpsolver.ifs.heuristics.GeneralValueSelection;
012 import net.sf.cpsolver.ifs.heuristics.ValueSelection;
013 import net.sf.cpsolver.ifs.solution.Solution;
014 import net.sf.cpsolver.ifs.solver.Solver;
015 import net.sf.cpsolver.ifs.util.DataProperties;
016 import net.sf.cpsolver.ifs.util.ToolBox;
017 import net.sf.cpsolver.studentsct.StudentSectioningModel;
018 import net.sf.cpsolver.studentsct.model.Enrollment;
019 import net.sf.cpsolver.studentsct.model.Request;
020 import 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 Tomas Muller<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 */
047 public 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 }