001 package net.sf.cpsolver.coursett.heuristics;
002
003
004 import java.util.*;
005
006 import net.sf.cpsolver.coursett.constraint.*;
007 import net.sf.cpsolver.coursett.model.*;
008 import net.sf.cpsolver.ifs.extension.*;
009 import net.sf.cpsolver.ifs.heuristics.*;
010 import net.sf.cpsolver.ifs.model.*;
011 import net.sf.cpsolver.ifs.perturbations.*;
012 import net.sf.cpsolver.ifs.solution.*;
013 import net.sf.cpsolver.ifs.solver.*;
014 import net.sf.cpsolver.ifs.util.*;
015
016 /**
017 * Placement (value) selection.
018 * <br><br>
019 * We have implemented a hierarchical handling of the value selection criteria (see {@link HeuristicSelector}).
020 * <br><br>
021 * The value selection heuristics also allow for random selection of a value with a given probability
022 * (random walk, e.g., 2%) and, in the case of MPP, to select the initial value (if it exists) with a given probability (e.g., 70%).
023 * <br><br>
024 * Parameters (general):
025 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
026 * <tr><td>Placement.RandomWalkProb</td><td>{@link Double}</td><td>Random walk probability</td></tr>
027 * <tr><td>Placement.GoodSelectionProb</td><td>{@link Double}</td><td>Good value (not removed from domain) selection probability (MAC related)</td></tr>
028 * <tr><td>Placement.TabuLength</td><td>{@link Integer}</td><td>Tabu-list length (-1 means do not use tabu-list)</td></tr>
029 * <tr><td>Placement.MPP_InitialProb</td><td>{@link Double}</td><td>MPP initial selection probability </td></tr>
030 * <tr><td>Placement.MPP_Limit</td><td>{@link Integer}</td><td>MPP: limit on the number of perturbations (-1 for no limit)</td></tr>
031 * <tr><td>Placement.MPP_PenaltyLimit</td><td>{@link Double}</td><td>MPP: limit on the perturbations penalty (-1 for no limit)</td></tr>
032 * </table>
033 * <br>
034 * Parameters (for each level of selection):
035 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
036 * <tr><td>Placement.NrAssignmentsWeight1<br>Placement.NrAssignmentsWeight2<br>Placement.NrAssignmentsWeight3</td><td>{@link Double}</td><td>Number of previous assignments of the value weight</td></tr>
037 * <tr><td>Placement.NrConflictsWeight1,2,3</td><td>{@link Double}</td><td>Number of conflicts weight</td></tr>
038 * <tr><td>Placement.WeightedConflictsWeight1,2,3</td><td>{@link Double}</td><td>Weighted conflicts weight (Conflict-based Statistics related)</td></tr>
039 * <tr><td>Placement.NrPotentialConflictsWeight1,2,3</td><td>{@link Double}</td><td>Number of potential conflicts weight (Conflict-based Statistics related)</td></tr>
040 * <tr><td>Placement.MPP_DeltaInitialAssignmentWeight1,2,3</td><td>{@link Double}</td><td>Delta initial assigments weight (MPP, violated initials related)</td></tr>
041 * <tr><td>Placement.NrHardStudConfsWeight1,2,3</td><td>{@link Double}</td><td>Hard student conflicts weight (student conflicts between single-section classes)</td></tr>
042 * <tr><td>Placement.NrStudConfsWeight1,2,3</td><td>{@link Double}</td><td>Student conflicts weight</td></tr>
043 * <tr><td>Placement.TimePreferenceWeight1,2,3</td><td>{@link Double}</td><td>Time preference weight</td></tr>
044 * <tr><td>Placement.DeltaTimePreferenceWeight1,2,3</td><td>{@link Double}</td><td>Time preference delta weight (difference between before and after assignemnt of the value)</td></tr>
045 * <tr><td>Placement.ConstrPreferenceWeight1,2,3</td><td>{@link Double}</td><td>Constraint preference weight</td></tr>
046 * <tr><td>Placement.RoomPreferenceWeight1,2,3</td><td>{@link Double}</td><td>Room preference weight</td></tr>
047 * <tr><td>Placement.UselessSlotsWeight1,2,3</td><td>{@link Double}</td><td>Useless slot weight</td></tr>
048 * <tr><td>Placement.TooBigRoomWeight1,2,3</td><td>{@link Double}</td><td>Too big room weight</td></tr>
049 * <tr><td>Placement.DistanceInstructorPreferenceWeight1,2,3</td><td>{@link Double}</td><td>Distance (of the rooms of the back-to-back classes) based instructor preferences weight</td></tr>
050 * <tr><td>Placement.DeptSpreadPenaltyWeight1,2,3</td><td>{@link Double}</td><td>Department spreading: penalty of when a slot over initial allowance is used</td></tr>
051 * <tr><td>Placement.ThresholdKoef1,2</td><td>{@link Double}</td><td>Threshold koeficient of the level</td></tr>
052 * </table>
053 *
054 * @see PlacementSelection
055 * @version
056 * CourseTT 1.1 (University Course Timetabling)<br>
057 * Copyright (C) 2006 Tomáš Müller<br>
058 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
059 * Lazenska 391, 76314 Zlin, Czech Republic<br>
060 * <br>
061 * This library is free software; you can redistribute it and/or
062 * modify it under the terms of the GNU Lesser General Public
063 * License as published by the Free Software Foundation; either
064 * version 2.1 of the License, or (at your option) any later version.
065 * <br><br>
066 * This library is distributed in the hope that it will be useful,
067 * but WITHOUT ANY WARRANTY; without even the implied warranty of
068 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
069 * Lesser General Public License for more details.
070 * <br><br>
071 * You should have received a copy of the GNU Lesser General Public
072 * License along with this library; if not, write to the Free Software
073 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
074 */
075
076 public class PlacementSelection implements ValueSelection {
077 static final int NR_LEVELS = 3;
078 private static final double PRECISION = 1.0;
079 private static final boolean USE_THRESHOLD = true;
080 private boolean iUseThreshold = USE_THRESHOLD;
081
082 private double iGoodSelectionProb;
083 public static final String GOOD_SELECTION_PROB = "Placement.GoodSelectionProb";
084 private double iRandomWalkProb;
085 public static final String RW_SELECTION_PROB = "Placement.RandomWalkProb";
086 private double iInitialSelectionProb;
087 public static final String INITIAL_SELECTION_PROB = "Placement.MPP_InitialProb";
088 private int iMPPLimit;
089 public static final String NR_MPP_LIMIT = "Placement.MPP_Limit";
090 private double iMPPPenaltyLimit;
091 public static final String NR_MPP_PENALTY_LIMIT = "Placement.MPP_PenaltyLimit";
092
093 private double[] iNrConflictsWeight = new double[NR_LEVELS];
094 public static final String NR_CONFLICTS_WEIGHT = "Placement.NrConflictsWeight";
095 private double[] iNrPotentialConflictsWeight = new double[NR_LEVELS];
096 public static final String NR_POTENTIAL_CONFLICTS_WEIGHT = "Placement.NrPotentialConflictsWeight";
097 private double[] iNrWeightedConflictsWeight = new double[NR_LEVELS];
098 public static final String WEIGHTED_CONFLICTS_WEIGHT = "Placement.WeightedConflictsWeight";
099 private double[] iDeltaTimePreferenceWeight = new double[NR_LEVELS];
100 public static final String DELTA_TIME_PREFERENCE_WEIGHT = "Placement.DeltaTimePreferenceWeight";
101 private double[] iPerturbationPenaltyWeight = new double[NR_LEVELS];
102 public static final String DELTA_INITIAL_ASSIGNMENT_WEIGHT = "Placement.MPP_DeltaInitialAssignmentWeight";
103 private double[] iNrStudentConflictsWeight = new double[NR_LEVELS];
104 public static final String NR_STUDENT_CONF_WEIGHT = "Placement.NrStudConfsWeight";
105 private double[] iNrHardStudentConflictsWeight = new double[NR_LEVELS];
106 public static final String NR_HARD_STUDENT_CONF_WEIGHT = "Placement.NrHardStudConfsWeight";
107 private double[] iNrCommitedStudentConflictsWeight = new double[NR_LEVELS];
108 public static final String NR_COMMITED_STUDENT_CONF_WEIGHT = "Placement.NrCommitedStudConfsWeight";
109 private double[] iUselessSlotsWeight = new double[NR_LEVELS];
110 public static final String USELESS_SLOTS_WEIGHT = "Placement.UselessSlotsWeight";
111 private double[] iSumConstrPreferencesWeight = new double[NR_LEVELS];
112 public static final String SUM_CONSTR_PREFERENCE_WEIGHT = "Placement.ConstrPreferenceWeight";
113 private double[] iSumRoomPreferencesWeight = new double[NR_LEVELS];
114 public static final String SUM_ROOM_PREFERENCE_WEIGHT = "Placement.RoomPreferenceWeight";
115 private double[] iSumTimePreferencesWeight = new double[NR_LEVELS];
116 public static final String SUM_TIME_PREFERENCE_WEIGHT = "Placement.TimePreferenceWeight";
117 private double[] iNrAssignmentsWeight = new double[NR_LEVELS];
118 public static final String NR_ASSIGNMENTS_WEIGHT = "Placement.NrAssignmentsWeight";
119 private double[] iThresholdKoef = new double[NR_LEVELS];
120 public static final String NR_THRESHOLD_KOEF = "Placement.ThresholdKoef";
121 private double[] iTooBigRoomWeight = new double[NR_LEVELS];
122 public static final String TOO_BIG_ROOM_WEIGHT = "Placement.TooBigRoomWeight";
123 private double[] iDeptSpreadWeight = new double[NR_LEVELS];
124 public static final String DEPT_SPREAD_WEIGHT = "Placement.DeptSpreadPenaltyWeight";
125 private double[] iDistanceInstructorPreferenceWeight = new double[NR_LEVELS];
126 public static final String DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT = "Placement.DistanceInstructorPreferenceWeight";
127 private double[] iSpreadWeight = new double[NR_LEVELS];
128 public static final String SPREAD_WEIGHT = "Placement.SpreadPenaltyWeight";
129
130 private int iTabuSize = 0;
131 private ArrayList iTabu = null;
132 private int iTabuPos = 0;
133 public static final String TABU_LENGTH = "Placement.TabuLength";
134
135 private ConflictStatistics iStat = null;
136 private MacPropagation iProp = null;
137 private ViolatedInitials iViolatedInitials = null;
138 private PerturbationsCounter iPerturbationsCounter = null;
139
140 private boolean iRW = false;
141 private boolean iMPP = false;
142 private boolean iSW = false;
143
144 private boolean iCanUnassingSingleton = false;
145
146 public void init(Solver solver) {
147 for (Enumeration i=solver.getExtensions().elements();i.hasMoreElements();) {
148 Extension extension = (Extension)i.nextElement();
149 if (extension instanceof ConflictStatistics)
150 iStat = (ConflictStatistics) extension;
151 if (extension instanceof MacPropagation)
152 iProp = (MacPropagation)extension;
153 if (extension instanceof ViolatedInitials)
154 iViolatedInitials = (ViolatedInitials)extension;
155 }
156 iPerturbationsCounter = solver.getPerturbationsCounter();
157 }
158
159 public PlacementSelection(DataProperties properties) {
160 iMPP = properties.getPropertyBoolean("General.MPP", false);
161 iRW = properties.getPropertyBoolean("General.RandomWalk", true);
162 iSW = properties.getPropertyBoolean("General.SwitchStudents",true);
163 iCanUnassingSingleton = properties.getPropertyBoolean("Placement.CanUnassingSingleton", iCanUnassingSingleton);
164 boolean autoconfigure = properties.getPropertyBoolean("Placement.AutoConfigure", false);
165 iRandomWalkProb = (iRW?properties.getPropertyDouble(RW_SELECTION_PROB,0.00):0.0);
166 iGoodSelectionProb = properties.getPropertyDouble(GOOD_SELECTION_PROB,1.00);
167 iInitialSelectionProb = (iMPP?properties.getPropertyDouble(INITIAL_SELECTION_PROB, 0.75):0.0);
168 iMPPLimit = (iMPP?properties.getPropertyInt(NR_MPP_LIMIT, -1):-1);
169 iMPPPenaltyLimit = (iMPP?properties.getPropertyDouble(NR_MPP_PENALTY_LIMIT, -1.0):-1.0);
170 iTabuSize = properties.getPropertyInt(TABU_LENGTH, -1);
171 if (iTabuSize>0) iTabu=new ArrayList(iTabuSize);
172 iUseThreshold = properties.getPropertyBoolean("Placement.UseThreshold", USE_THRESHOLD);
173
174 for (int level=0; level<NR_LEVELS; level++) {
175 iNrConflictsWeight[level] = properties.getPropertyDouble(NR_CONFLICTS_WEIGHT+(level+1),(level==0?1.0:0.0));
176 iNrPotentialConflictsWeight[level] = properties.getPropertyDouble(NR_POTENTIAL_CONFLICTS_WEIGHT+(level+1),0.0);
177 iNrWeightedConflictsWeight[level] = properties.getPropertyDouble(WEIGHTED_CONFLICTS_WEIGHT+(level+1),(level==0?1.0:0.0));
178 iDeltaTimePreferenceWeight[level] = properties.getPropertyDouble(DELTA_TIME_PREFERENCE_WEIGHT+(level+1), (level==0?0.5:0.0));
179 iPerturbationPenaltyWeight[level] = (iMPP?properties.getPropertyDouble(DELTA_INITIAL_ASSIGNMENT_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0)):0.0);
180 iNrStudentConflictsWeight[level] = properties.getPropertyDouble(NR_STUDENT_CONF_WEIGHT+(level+1),(level==0?0.1:(level==1?0.2:0.0)));
181 iNrHardStudentConflictsWeight[level] = (iSW?properties.getPropertyDouble(NR_HARD_STUDENT_CONF_WEIGHT+(level+1),(level==0?0.5:level==1?1.0:0.0)):0.0);
182 iNrCommitedStudentConflictsWeight[level] = properties.getPropertyDouble(NR_COMMITED_STUDENT_CONF_WEIGHT+(level+1),(level==0?0.2:level==1?1.0:0.0));
183 iUselessSlotsWeight[level] = properties.getPropertyDouble(USELESS_SLOTS_WEIGHT+(level+1), 0.0);
184 iSumConstrPreferencesWeight[level] = properties.getPropertyDouble(SUM_CONSTR_PREFERENCE_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0));
185 iSumRoomPreferencesWeight[level] = properties.getPropertyDouble(SUM_ROOM_PREFERENCE_WEIGHT+(level+1), (level==1?0.1:0.0));
186 iSumTimePreferencesWeight[level] = properties.getPropertyDouble(SUM_TIME_PREFERENCE_WEIGHT+(level+1), (level==1?1.0:0.0));
187 iNrAssignmentsWeight[level] = properties.getPropertyDouble(NR_ASSIGNMENTS_WEIGHT+(level+1), 0.0);
188 iThresholdKoef[level] = (USE_THRESHOLD?properties.getPropertyDouble(NR_THRESHOLD_KOEF+(level+1), (level==0?0.1:0.0)):0.0);
189 iTooBigRoomWeight[level] = properties.getPropertyDouble(TOO_BIG_ROOM_WEIGHT+(level+1), 0.0);
190 iDeptSpreadWeight[level] = properties.getPropertyDouble(DEPT_SPREAD_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0));
191 iSpreadWeight[level] = properties.getPropertyDouble(SPREAD_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0));
192 iDistanceInstructorPreferenceWeight[level] = properties.getPropertyDouble(DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT+(level+1), (level==0?0.1:level==1?1.0:0.0));
193 }
194
195 if (autoconfigure) {
196 iNrConflictsWeight[0] = 3.0;
197 iNrPotentialConflictsWeight[0] = 0.0;
198 iNrWeightedConflictsWeight[0] = 3.0;
199 iDeltaTimePreferenceWeight[0] = properties.getPropertyDouble("Comparator.TimePreferenceWeight",1.0)/2.0;
200 iNrAssignmentsWeight[0] = 0.0;
201 iThresholdKoef[0] = 0.1;
202
203 iNrStudentConflictsWeight[0] = properties.getPropertyDouble("Comparator.StudentConflictWeight",0.2);
204 iNrHardStudentConflictsWeight[0] = properties.getPropertyDouble("Comparator.HardStudentConflictWeight",1.0);
205 iNrCommitedStudentConflictsWeight[0] = properties.getPropertyDouble("Comparator.CommitedStudentConflictWeight",1.0);
206 iUselessSlotsWeight[0] = properties.getPropertyDouble("Comparator.UselessSlotWeight",0.0);
207 iSumConstrPreferencesWeight[0] = properties.getPropertyDouble("Comparator.ContrPreferenceWeight",1.0);
208 iSumRoomPreferencesWeight[0] = properties.getPropertyDouble("Comparator.RoomPreferenceWeight",0.1);
209 iSumTimePreferencesWeight[0] = properties.getPropertyDouble("Comparator.TimePreferenceWeight",1.0);
210 iTooBigRoomWeight[0] = properties.getPropertyDouble("Comparator.TooBigRoomWeight",0.0);
211 iDeptSpreadWeight[0] = properties.getPropertyDouble("Comparator.DeptSpreadPenaltyWeight",1.0);
212 iSpreadWeight[0] = properties.getPropertyDouble("Comparator.SpreadPenaltyWeight",1.0);
213 iDistanceInstructorPreferenceWeight[0] = properties.getPropertyDouble("Comparator.DistanceInstructorPreferenceWeight",1.0);
214 iPerturbationPenaltyWeight[0] = (iMPP?properties.getPropertyDouble("Comparator.PerturbationPenaltyWeight",1.0):0.0);
215
216 iNrConflictsWeight[1] = 0.0;
217 iNrPotentialConflictsWeight[1] = 0.0;
218 iNrWeightedConflictsWeight[1] = 0.0;
219 iDeltaTimePreferenceWeight[1] = 0.0;
220 iNrAssignmentsWeight[1] = 0.0;
221 iThresholdKoef[1] = 0.0;
222
223 iNrStudentConflictsWeight[1] = properties.getPropertyDouble("Comparator.StudentConflictWeight",0.2);
224 iNrHardStudentConflictsWeight[1] = properties.getPropertyDouble("Comparator.HardStudentConflictWeight",1.0);
225 iNrCommitedStudentConflictsWeight[1] = properties.getPropertyDouble("Comparator.CommitedStudentConflictWeight",1.0);
226 iUselessSlotsWeight[1] = properties.getPropertyDouble("Comparator.UselessSlotWeight",0.0);
227 iSumConstrPreferencesWeight[1] = properties.getPropertyDouble("Comparator.ContrPreferenceWeight",1.0);
228 iSumRoomPreferencesWeight[1] = properties.getPropertyDouble("Comparator.RoomPreferenceWeight",0.1);
229 iSumTimePreferencesWeight[1] = properties.getPropertyDouble("Comparator.TimePreferenceWeight",1.0);
230 iTooBigRoomWeight[1] = properties.getPropertyDouble("Comparator.TooBigRoomWeight",0.0);
231 iDeptSpreadWeight[1] = properties.getPropertyDouble("Comparator.DeptSpreadPenaltyWeight",1.0);
232 iSpreadWeight[1] = properties.getPropertyDouble("Comparator.SpreadPenaltyWeight",1.0);
233 iDistanceInstructorPreferenceWeight[1] = properties.getPropertyDouble("Comparator.DistanceInstructorPreferenceWeight",1.0);
234 iPerturbationPenaltyWeight[1] = (iMPP?properties.getPropertyDouble("Comparator.PerturbationPenaltyWeight",1.0):0.0);
235
236 iNrConflictsWeight[2] = 0.0;
237 iNrPotentialConflictsWeight[2] = 0.0;
238 iNrWeightedConflictsWeight[2] = 0.0;
239 iDeltaTimePreferenceWeight[2] = 0.0;
240 iPerturbationPenaltyWeight[2] = 0.0;
241 iNrStudentConflictsWeight[2] = 0.0;
242 iNrHardStudentConflictsWeight[2] = 0.0;
243 iNrCommitedStudentConflictsWeight[2] = 0.0;
244 iUselessSlotsWeight[2] = 0.0;
245 iSumConstrPreferencesWeight[2] = 0.0;
246 iSumRoomPreferencesWeight[2] = 0.0;
247 iSumTimePreferencesWeight[2] = 0.0;
248 iNrAssignmentsWeight[2] = 0.0;
249 iThresholdKoef[2] = 0.0;
250 iTooBigRoomWeight[2] = 0.0;
251 iDeptSpreadWeight[2] = 0.0;
252 iSpreadWeight[2] = 0.0;
253 iDistanceInstructorPreferenceWeight[2] = 0.0;
254 }
255 }
256
257 public Value selectValue(Solution solution, Variable selectedVariable) {
258 if (selectedVariable==null) return null;
259 TimetableModel model = (TimetableModel)solution.getModel();
260 /*if (iMPPLimit>=0 && solution.getModel().unassignedVariables().isEmpty() && iMPPLimit>solution.getModel().perturbVariables().size()) {
261 ToolBox.print("A complete solution with "+solution.getModel().perturbVariables().size()+" perturbances found");
262 iMPPLimit = solution.getModel().perturbVariables().size()-1;
263 ToolBox.print("MPP limit decreased to "+iMPPLimit);
264 }*/
265 if (selectedVariable.getInitialAssignment()!=null) {
266 if (iMPPLimit>=0 && model.perturbVariables().size()>=iMPPLimit) {
267 if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()),selectedVariable.getInitialAssignment()))
268 return checkValue(selectedVariable.getInitialAssignment());
269 } else if (iMPPPenaltyLimit>=0.0 && solution.getPerturbationsCounter()!=null && solution.getPerturbationsCounter().getPerturbationPenalty(model)>iMPPPenaltyLimit) {
270 if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()),selectedVariable.getInitialAssignment()))
271 return checkValue(selectedVariable.getInitialAssignment());
272 } else if (selectedVariable.getInitialAssignment()!=null && ToolBox.random()<=iInitialSelectionProb) {
273 if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()),selectedVariable.getInitialAssignment()))
274 return checkValue(selectedVariable.getInitialAssignment());
275 }
276 }
277
278 Vector values = selectedVariable.values();
279 if (iRW && ToolBox.random()<=iRandomWalkProb) {
280 for (int i=0;i<5;i++) {
281 Value ret = (Value)ToolBox.random(values);
282 if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
283 return checkValue(ret);
284 }
285 }
286 if (iProp!=null && selectedVariable.getAssignment()==null && ToolBox.random()<=iGoodSelectionProb) {
287 Collection goodValues = iProp.goodValues(selectedVariable);
288 if (!goodValues.isEmpty()) values=new FastVector(goodValues);
289 }
290 if (values.size()==1) {
291 Value ret = (Value)values.firstElement();
292 if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
293 return checkValue(ret);
294 }
295
296 long[] bestCost = new long[NR_LEVELS];
297 Vector selectionValues = null;
298
299
300 HeuristicSelector selector = (iUseThreshold?new HeuristicSelector(iThresholdKoef):null);
301 for (Enumeration i1=values.elements();i1.hasMoreElements();) {
302 Value value = (Value) i1.nextElement();
303 if (iTabu!=null && iTabu.contains(value)) continue;
304 if (selectedVariable.getAssignment()!=null && selectedVariable.getAssignment().equals(value)) continue;
305
306 ParamRetriever paramRetriever = new ParamRetriever(solution, (Lecture)selectedVariable, (Placement)value);
307 if (containsItselfSingletonOrCommited(model, paramRetriever.conflicts(), value)) continue;
308
309 if (iUseThreshold) {
310 Double flt = selector.firstLevelThreshold();
311 double[] costs = new double[NR_LEVELS];
312 for (int level=0;level<NR_LEVELS;level++) {
313 costs[level] = getCost(paramRetriever, level, flt);
314 if (level==0 && flt!=null && costs[0]>flt.doubleValue()) {
315 break;
316 }
317 }
318 if (flt!=null && costs[0]>flt.doubleValue()) continue;
319 selector.add(costs, value);
320 } else {
321 Double flt = (selectionValues==null?null:new Double(0.5+bestCost[0]));
322 boolean fail = false;
323 boolean best = false;
324 for (int level=0;!fail && level<1;level++) {
325 long cost = Math.round( PRECISION * getCost(paramRetriever, level, flt));
326 if (selectionValues!=null && !best) {
327 if (cost>bestCost[level]) { fail=true; }
328 if (cost<bestCost[level]) { bestCost[level]=cost; selectionValues.clear(); best=true; }
329 } else {
330 bestCost[level]=cost;
331 }
332 }
333 if (selectionValues==null) selectionValues = new FastVector(values.size());
334 if (!fail) selectionValues.addElement(value);
335 }
336 }
337 //ToolBox.print("Best "+selectionValues.size()+" locations for variable "+selectedVariable.getId()+" have "+bestConflicts+" conflicts ("+bestRemovals+" weighted) and "+bestStudentConflicts+" ("+bestOriginalStudentConflicts+" * "+bestKoef+" + "+bestPenalty+") preference.");
338 Value selectedValue = null;
339 if (iUseThreshold) {
340 selectionValues = selector.selection();
341
342 if (selectedVariable.getInitialAssignment()!=null) {
343 for (Enumeration e=selectionValues.elements();e.hasMoreElements();) {
344 Value value = (Value)((HeuristicSelector.Element) e.nextElement()).getObject();
345 if (value.equals(selectedVariable.getInitialAssignment())) {
346 selectedValue = value;
347 break;
348 }
349 }
350 //&& selectionValues.contains(selectedVariable.getInitialAssignment())) return selectedVariable.getInitialAssignment();
351 }
352
353 if (selectedValue==null) {
354 HeuristicSelector.Element selection = (HeuristicSelector.Element)ToolBox.random(selectionValues);
355 selectedValue = (Value)(selection==null?null:selection.getObject());
356 }
357 } else {
358 if (selectedVariable.getInitialAssignment()!=null && selectionValues.contains(selectedVariable.getInitialAssignment())) return checkValue(selectedVariable.getInitialAssignment());
359 selectedValue = (Value)ToolBox.random(selectionValues);
360 }
361 if (selectedValue!=null && iTabu!=null) {
362 if (iTabu.size()==iTabuPos)
363 iTabu.add(selectedValue);
364 else
365 iTabu.set(iTabuPos, selectedValue);
366 iTabuPos = (iTabuPos + 1) % iTabuSize;
367 }
368 return checkValue(selectedValue);
369 }
370
371 public boolean containsItselfSingletonOrCommited(TimetableModel model, Collection values, Value selectedValue) {
372 if (values.contains(selectedValue)) return true;
373 if (model.hasConstantVariables()) {
374 for (Iterator i=values.iterator();i.hasNext();) {
375 Placement placement = (Placement)i.next();
376 Lecture lecture = (Lecture)placement.variable();
377 if (lecture.isCommitted()) return true;
378 if (!iCanUnassingSingleton && lecture.isSingleton()) return true;
379 }
380 return false;
381 } else {
382 if (iCanUnassingSingleton) return false;
383 for (Iterator i=values.iterator();i.hasNext();) {
384 Placement placement = (Placement)i.next();
385 Lecture lecture = (Lecture)placement.variable();
386 if (lecture.isSingleton()) return true;
387 }
388 return false;
389 }
390 }
391
392 private Value checkValue(Value aValue) {
393 if (aValue==null) return null;
394 for (Iterator i=((Lecture)aValue.variable()).getWeakeningConstraints().iterator();i.hasNext();) {
395 Constraint c = (Constraint)i.next();
396 if (c.inConflict(aValue)) ((WeakeningConstraint)c).weaken();
397 }
398 return aValue;
399 }
400
401 public ParamRetriever getParameters(Solution solution, Lecture lecture, Placement placement) {
402 return new ParamRetriever(solution, lecture, placement);
403 }
404
405 public double getCost(ParamRetriever paramRetriever, int level, Double flt) {
406 if (level==0 && flt!=null) {
407 double cost =
408 (iNrConflictsWeight[level]==0.0?0.0:iNrConflictsWeight[level]*paramRetriever.nrContlicts())+
409 (iNrWeightedConflictsWeight[level]==0.0?0.0:iNrWeightedConflictsWeight[level]*paramRetriever.weightedConflicts())+
410 (iNrPotentialConflictsWeight[level]==0.0?0.0:iNrPotentialConflictsWeight[level]*paramRetriever.potentialConflicts(3))+
411 (iDeltaTimePreferenceWeight[level]==0.0?0.0:iDeltaTimePreferenceWeight[level]*paramRetriever.deltaTimePreference())+
412 (iSumConstrPreferencesWeight[level]==0.0?0.0:iSumConstrPreferencesWeight[level]*paramRetriever.constrPreference())+
413 (iSumRoomPreferencesWeight[level]==0.0?0.0:iSumRoomPreferencesWeight[level]*paramRetriever.roomPreference())+
414 (iSumTimePreferencesWeight[level]==0.0?0.0:iSumTimePreferencesWeight[level]*paramRetriever.timePreference())+
415 (iNrAssignmentsWeight[level]==0.0?0.0:iNrAssignmentsWeight[level]*paramRetriever.nrAssignments())
416 ;
417 if (cost>flt.doubleValue()) return cost;
418 cost +=
419 (iUselessSlotsWeight[level]==0.0?0.0:iUselessSlotsWeight[level]*paramRetriever.emptySingleHalfHours())+
420 (iTooBigRoomWeight[level]==0.0?0.0:iTooBigRoomWeight[level]*paramRetriever.tooBig())
421 ;
422 if (cost>flt.doubleValue()) return cost;
423 cost +=
424 (iPerturbationPenaltyWeight[level]==0.0?0.0:iPerturbationPenaltyWeight[level]*paramRetriever.perturbationsPenalty())
425 ;
426 if (cost>flt.doubleValue()) return cost;
427 cost +=
428 (iDistanceInstructorPreferenceWeight[level]==0.0?0.0:iDistanceInstructorPreferenceWeight[level]*paramRetriever.distanceInstructorPreference())
429 ;
430 if (cost>flt.doubleValue()) return cost;
431 cost +=
432 (iDeptSpreadWeight[level]==0.0?0.0:iDeptSpreadWeight[level]*paramRetriever.deptSpread())+
433 (iSpreadWeight[level]==0.0?0.0:iSpreadWeight[level]*paramRetriever.spread())
434 ;
435 if (cost>flt.doubleValue()) return cost;
436 cost +=
437 (iNrStudentConflictsWeight[level]==0.0?0.0:iNrStudentConflictsWeight[level]*paramRetriever.sumStudentConflicts())+
438 (iNrHardStudentConflictsWeight[level]==0.0?0.0:iNrHardStudentConflictsWeight[level]*paramRetriever.sumHardStudentConflicts())+
439 (iNrCommitedStudentConflictsWeight[level]==0.0?0.0:iNrCommitedStudentConflictsWeight[level]*paramRetriever.sumCommitedStudentConflicts())
440 ;
441 return cost;
442 }
443 double cost =
444 (iNrConflictsWeight[level]==0.0?0.0:iNrConflictsWeight[level]*paramRetriever.nrContlicts())+
445 (iNrWeightedConflictsWeight[level]==0.0?0.0:iNrWeightedConflictsWeight[level]*paramRetriever.weightedConflicts())+
446 (iNrPotentialConflictsWeight[level]==0.0?0.0:iNrPotentialConflictsWeight[level]*paramRetriever.potentialConflicts(3))+
447 (iDeltaTimePreferenceWeight[level]==0.0?0.0:iDeltaTimePreferenceWeight[level]*paramRetriever.deltaTimePreference())+
448 (iPerturbationPenaltyWeight[level]==0.0?0.0:iPerturbationPenaltyWeight[level]*paramRetriever.perturbationsPenalty())+
449 (iNrStudentConflictsWeight[level]==0.0?0.0:iNrStudentConflictsWeight[level]*paramRetriever.sumStudentConflicts())+
450 (iNrHardStudentConflictsWeight[level]==0.0?0.0:iNrHardStudentConflictsWeight[level]*paramRetriever.sumHardStudentConflicts())+
451 (iUselessSlotsWeight[level]==0.0?0.0:iUselessSlotsWeight[level]*paramRetriever.emptySingleHalfHours())+
452 (iSumConstrPreferencesWeight[level]==0.0?0.0:iSumConstrPreferencesWeight[level]*paramRetriever.constrPreference())+
453 (iSumRoomPreferencesWeight[level]==0.0?0.0:iSumRoomPreferencesWeight[level]*paramRetriever.roomPreference())+
454 (iSumTimePreferencesWeight[level]==0.0?0.0:iSumTimePreferencesWeight[level]*paramRetriever.timePreference())+
455 (iNrAssignmentsWeight[level]==0.0?0.0:iNrAssignmentsWeight[level]*paramRetriever.nrAssignments())+
456 (iTooBigRoomWeight[level]==0.0?0.0:iTooBigRoomWeight[level]*paramRetriever.tooBig())+
457 (iDeptSpreadWeight[level]==0.0?0.0:iDeptSpreadWeight[level]*paramRetriever.deptSpread())+
458 (iSpreadWeight[level]==0.0?0.0:iSpreadWeight[level]*paramRetriever.spread())+
459 (iDistanceInstructorPreferenceWeight[level]==0.0?0.0:iDistanceInstructorPreferenceWeight[level]*paramRetriever.distanceInstructorPreference())+
460 (iNrCommitedStudentConflictsWeight[level]==0.0?0.0:iNrCommitedStudentConflictsWeight[level]*paramRetriever.sumCommitedStudentConflicts())
461 ;
462 return cost;
463 }
464
465 public class ParamRetriever {
466 private Lecture iLecture;
467 private Placement iPlacement;
468 private Solution iSolution;
469 private ParamRetriever(Solution solution, Lecture lecture, Placement placement) {
470 iSolution = solution;
471 iLecture = lecture;
472 iPlacement = placement;
473 }
474
475 Collection iConf = null;
476 public Collection conflicts() {
477 if (iConf == null) iConf = iSolution.getModel().conflictValues(iPlacement);
478 return iConf;
479 }
480
481 public long nrContlicts() {
482 return conflicts().size();
483 }
484
485 private Double iWeightedConflicts = null;
486 public double weightedConflicts() {
487 if (iWeightedConflicts==null)
488 iWeightedConflicts = new Double(iStat==null?0.0:iStat.countRemovals(iSolution.getIteration(), conflicts(), iPlacement));
489 return iWeightedConflicts.doubleValue();
490 }
491
492 private Double iPotentialConflicts = null;
493 public double potentialConflicts(int limit) {
494 if (iPotentialConflicts==null)
495 iPotentialConflicts = new Double(iStat==null?0.0:iStat.countPotentialConflicts(iSolution.getIteration(),iPlacement, limit));
496 return iPotentialConflicts.doubleValue();
497 }
498
499 Double iDeltaTimePreference = null;
500 public double deltaTimePreference() {
501 if (iDeltaTimePreference==null) {
502 double deltaTimePreference = 0;
503 for (Iterator it1=conflicts().iterator(); it1.hasNext(); ) {
504 Placement placement = (Placement)it1.next();
505 double timePref = placement.getTimeLocation().getNormalizedPreference();
506 deltaTimePreference -= timePref - ((Lecture)placement.variable()).getBestTimePreference();
507 }
508 deltaTimePreference += iPlacement.getTimeLocation().getNormalizedPreference() - iLecture.getBestTimePreference();
509 iDeltaTimePreference = new Double(deltaTimePreference);
510 }
511 return iDeltaTimePreference.doubleValue();
512 }
513
514 Double iPerturbationsPenalty = null;
515 public double perturbationsPenalty() {
516 if (iPerturbationsCounter==null) return 0.0;
517 if (iPerturbationsPenalty==null) {
518 iPerturbationsPenalty = new Double(iPerturbationsCounter.getPerturbationPenalty(iSolution.getModel(),iPlacement,conflicts()));
519 }
520 return iPerturbationsPenalty.doubleValue();
521 }
522
523 public void countStudentConflicts() {
524 long all = 0;
525 int hard = 0;
526 if (!iLecture.isSingleSection()) {
527 for (Enumeration i=iLecture.jenrlConstraints();i.hasMoreElements();) {
528 JenrlConstraint jc = (JenrlConstraint)i.nextElement();
529 all += jc.jenrl(iLecture,iPlacement);
530 }
531 } else {
532 for (Enumeration i=iLecture.jenrlConstraints();i.hasMoreElements();) {
533 JenrlConstraint jc = (JenrlConstraint)i.nextElement();
534 long jenrl = jc.jenrl(iLecture,iPlacement);
535 if (((Lecture)jc.another(iLecture)).isSingleSection()) hard += jenrl;
536 all += jenrl;
537 }
538 }
539 iSumStudentConflicts = new Integer((int)all);
540 iSumHardStudentConflicts = new Integer(hard);
541 }
542
543 Integer iSumStudentConflicts = null;
544 public int sumStudentConflicts() {
545 if (iSumStudentConflicts==null) countStudentConflicts();
546 return iSumStudentConflicts.intValue();
547 }
548
549 Integer iConstrPreference = null;
550 public int constrPreference() {
551 if (iConstrPreference==null) {
552 int constrPreference = 0;
553 for (Iterator i2=iLecture.groupConstraints().iterator();i2.hasNext();) {
554 GroupConstraint gc = (GroupConstraint)i2.next();
555 constrPreference += gc.getCurrentPreference(iPlacement);
556 }
557 iConstrPreference = new Integer(constrPreference);
558 }
559 return iConstrPreference.intValue();
560 }
561
562 Integer iEmptySingleHalfHours = null;
563 public int emptySingleHalfHours() {
564 if (iEmptySingleHalfHours==null) {
565 iEmptySingleHalfHours = new Integer(iPlacement.nrUselessHalfHours());
566 }
567 return iEmptySingleHalfHours.intValue();
568 }
569
570 Integer iSumHardStudentConflicts = null;
571 public int sumHardStudentConflicts() {
572 if (iSumHardStudentConflicts==null) countStudentConflicts();
573 return iSumHardStudentConflicts.intValue();
574 }
575
576 public int sumCommitedStudentConflicts() {
577 return iLecture.getCommitedConflicts(iPlacement);
578 }
579
580 public int roomPreference() {
581 return iPlacement.sumRoomPreference();
582 }
583
584 public long nrAssignments() {
585 return iPlacement.countAssignments();
586 }
587
588 public double timePreference() {
589 return iPlacement.getTimeLocation().getNormalizedPreference();
590 }
591
592 public int tooBig() {
593 return iPlacement.getTooBigRoomPreference();
594 }
595
596 Integer iDeptSpreadCache = null;
597 public int deptSpread() {
598 if (iLecture.getDeptSpreadConstraint()==null) return 0;
599 if (iDeptSpreadCache==null)
600 iDeptSpreadCache = new Integer(iLecture.getDeptSpreadConstraint().getPenalty(iPlacement));
601 return iDeptSpreadCache.intValue();
602 }
603
604 Integer iSpreadCache = null;
605 public int spread() {
606 if (iLecture.getSpreadConstraints().isEmpty()) return 0;
607 if (iSpreadCache==null) {
608 iSpreadCache = new Integer(iPlacement.getSpreadPenalty());
609 }
610 return iSpreadCache.intValue();
611 }
612
613 Integer iDistanceInstructorPreferenceCache = null;
614 public int distanceInstructorPreference() {
615 if (iDistanceInstructorPreferenceCache==null) {
616 int pref = 0;
617 for (Enumeration i2=iLecture.constraints().elements();i2.hasMoreElements();) {
618 Constraint constraint = (Constraint)i2.nextElement();
619 if (constraint instanceof InstructorConstraint) {
620 pref += ((InstructorConstraint)constraint).getPreference(iPlacement);
621 }
622 }
623 iDistanceInstructorPreferenceCache = new Integer(pref);
624 }
625 return iDistanceInstructorPreferenceCache.intValue();
626 }
627 }
628
629 public PerturbationsCounter getPerturbationsCounter() {
630 return iPerturbationsCounter;
631 }
632 }