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