001package net.sf.cpsolver.coursett.heuristics;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.Iterator;
006import java.util.List;
007
008import net.sf.cpsolver.coursett.model.Lecture;
009import net.sf.cpsolver.coursett.model.Placement;
010import net.sf.cpsolver.coursett.model.TimetableModel;
011import net.sf.cpsolver.ifs.extension.Extension;
012import net.sf.cpsolver.ifs.extension.MacPropagation;
013import net.sf.cpsolver.ifs.heuristics.VariableSelection;
014import net.sf.cpsolver.ifs.solution.Solution;
015import net.sf.cpsolver.ifs.solver.Solver;
016import net.sf.cpsolver.ifs.util.DataProperties;
017import net.sf.cpsolver.ifs.util.ToolBox;
018
019/**
020 * Lecture (variable) selection. <br>
021 * <br>
022 * If there are one or more variables unassigned, the variable selection
023 * criterion picks one of them randomly. We have tried several approaches using
024 * domain sizes, number of previous assignments, numbers of constraints in which
025 * the variable participates, etc., but there was no significant improvement in
026 * this timetabling problem towards the random selection of an unassigned
027 * variable. The reason is, that it is easy to go back when a wrong variable is
028 * picked - such a variable is unassigned when there is a conflict with it in
029 * some of the subsequent iterations. <br>
030 * <br>
031 * When all variables are assigned, an evaluation is made for each variable
032 * according to the above described weights. The variable with the worst
033 * evaluation is selected. This variable promises the best improvement in
034 * optimization. <br>
035 * <br>
036 * Parameters (selection among unassigned lectures):
037 * <table border='1'>
038 * <tr>
039 * <th>Parameter</th>
040 * <th>Type</th>
041 * <th>Comment</th>
042 * </tr>
043 * <tr>
044 * <td>Lecture.RouletteWheelSelection</td>
045 * <td>{@link Boolean}</td>
046 * <td>Roulette wheel selection</td>
047 * </tr>
048 * <tr>
049 * <td>Lecture.RandomWalkProb</td>
050 * <td>{@link Double}</td>
051 * <td>Random walk probability</td>
052 * </tr>
053 * <tr>
054 * <td>Lecture.DomainSizeWeight</td>
055 * <td>{@link Double}</td>
056 * <td>Domain size weight</td>
057 * </tr>
058 * <tr>
059 * <td>Lecture.NrAssignmentsWeight</td>
060 * <td>{@link Double}</td>
061 * <td>Number of assignments weight</td>
062 * </tr>
063 * <tr>
064 * <td>Lecture.InitialAssignmentWeight</td>
065 * <td>{@link Double}</td>
066 * <td>Initial assignment weight</td>
067 * </tr>
068 * <tr>
069 * <td>Lecture.NrConstraintsWeight</td>
070 * <td>{@link Double}</td>
071 * <td>Number of constraint weight</td>
072 * </tr>
073 * </table>
074 * <br>
075 * Parameters (selection among assigned lectures, when the solution is
076 * complete):
077 * <table border='1'>
078 * <tr>
079 * <th>Parameter</th>
080 * <th>Type</th>
081 * <th>Comment</th>
082 * </tr>
083 * <tr>
084 * <td>Comparator.HardStudentConflictWeight</td>
085 * <td>{@link Double}</td>
086 * <td>Hard student conflict weight</td>
087 * </tr>
088 * <tr>
089 * <td>Comparator.StudentConflictWeight</td>
090 * <td>{@link Double}</td>
091 * <td>Student conflict weight</td>
092 * </tr>
093 * <tr>
094 * <td>Comparator.TimePreferenceWeight</td>
095 * <td>{@link Double}</td>
096 * <td>Time preference weight</td>
097 * </tr>
098 * <tr>
099 * <td>Comparator.ContrPreferenceWeight</td>
100 * <td>{@link Double}</td>
101 * <td>Group constraint preference weight</td>
102 * </tr>
103 * <tr>
104 * <td>Comparator.RoomPreferenceWeight</td>
105 * <td>{@link Double}</td>
106 * <td>Room preference weight</td>
107 * </tr>
108 * <tr>
109 * <td>Comparator.UselessSlotWeight</td>
110 * <td>{@link Double}</td>
111 * <td>Useless slot weight</td>
112 * </tr>
113 * <tr>
114 * <td>Comparator.TooBigRoomWeight</td>
115 * <td>{@link Double}</td>
116 * <td>Too big room weight</td>
117 * </tr>
118 * <tr>
119 * <td>Comparator.DistanceInstructorPreferenceWeight</td>
120 * <td>{@link Double}</td>
121 * <td>Distance (of the rooms of the back-to-back classes) based instructor
122 * preferences weight</td>
123 * </tr>
124 * <tr>
125 * <td>Comparator.DeptSpreadPenaltyWeight</td>
126 * <td>{@link Double}</td>
127 * <td>Department balancing penalty (see
128 * {@link net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint})</td>
129 * </tr>
130 * </table>
131 * <br>
132 * Parameters (selection among subset of lectures (faster)):
133 * <table border='1'>
134 * <tr>
135 * <th>Parameter</th>
136 * <th>Type</th>
137 * <th>Comment</th>
138 * </tr>
139 * <tr>
140 * <td>Lecture.SelectionSubSet</td>
141 * <td>{@link Boolean}</td>
142 * <td>Selection among subset of lectures (faster)</td>
143 * </tr>
144 * <tr>
145 * <td>Lecture.SelectionSubSetMinSize</td>
146 * <td>{@link Double}</td>
147 * <td>Minimal subset size</td>
148 * </tr>
149 * <tr>
150 * <td>Lecture.SelectionSubSetPart</td>
151 * <td>{@link Double}</td>
152 * <td>Subset size in percentage of all lectures available for selection</td>
153 * </tr>
154 * </table>
155 * 
156 * @see PlacementSelection
157 * @version CourseTT 1.2 (University Course Timetabling)<br>
158 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
159 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
160 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
161 * <br>
162 *          This library is free software; you can redistribute it and/or modify
163 *          it under the terms of the GNU Lesser General Public License as
164 *          published by the Free Software Foundation; either version 3 of the
165 *          License, or (at your option) any later version. <br>
166 * <br>
167 *          This library is distributed in the hope that it will be useful, but
168 *          WITHOUT ANY WARRANTY; without even the implied warranty of
169 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
170 *          Lesser General Public License for more details. <br>
171 * <br>
172 *          You should have received a copy of the GNU Lesser General Public
173 *          License along with this library; if not see
174 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
175 */
176public class LectureSelection implements VariableSelection<Lecture, Placement> {
177    private double iRandomWalkProb;
178    private double iDomainSizeWeight;
179    private double iGoodValuesWeight;
180    private double iNrAssignmentsWeight;
181    private double iConstraintsWeight;
182    private double iInitialAssignmentWeight;
183    private boolean iRouletteWheelSelection;
184    private boolean iUnassignWhenNotGood;
185
186    private boolean iSubSetSelection;
187    private double iSelectionSubSetPart;
188    private int iSelectionSubSetMinSize;
189    private boolean iInteractiveMode;
190
191    private boolean iRW = false;
192    private boolean iMPP = false;
193
194    private MacPropagation<Lecture, Placement> iProp = null;
195
196    private int iTabuSize = 0;
197    private ArrayList<Lecture> iTabu = null;
198    private int iTabuPos = 0;
199
200    private int iVariableChanceIteration = 1000;
201    private double iVariableChanceProb = 0.05;
202
203    public LectureSelection(DataProperties properties) {
204        iRouletteWheelSelection = properties.getPropertyBoolean("Lecture.RouletteWheelSelection", true);
205        iUnassignWhenNotGood = properties.getPropertyBoolean("Lecture.UnassignWhenNotGood", false);
206        iRW = properties.getPropertyBoolean("General.RandomWalk", true);
207        iRandomWalkProb = (!iRW ? 0.0 : properties.getPropertyDouble("Lecture.RandomWalkProb", 1.00));
208        iGoodValuesWeight = properties.getPropertyDouble("Lecture.GoodValueProb", 1.0);
209        iDomainSizeWeight = properties.getPropertyDouble("Lecture.DomainSizeWeight", 30.0);
210
211        iInteractiveMode = properties.getPropertyBoolean("General.InteractiveMode", false);
212
213        iNrAssignmentsWeight = properties.getPropertyDouble("Lecture.NrAssignmentsWeight", 10.0);
214        iConstraintsWeight = properties.getPropertyDouble("Lecture.NrConstraintsWeight", 0.0);
215        iMPP = properties.getPropertyBoolean("General.MPP", false);
216        iInitialAssignmentWeight = (!iMPP ? 0.0 : properties.getPropertyDouble("Lecture.InitialAssignmentWeight", 20.0));
217
218        iSubSetSelection = properties.getPropertyBoolean("Lecture.SelectionSubSet", true);
219        iSelectionSubSetMinSize = properties.getPropertyInt("Lecture.SelectionSubSetMinSize", 10);
220        iSelectionSubSetPart = properties.getPropertyDouble("Lecture.SelectionSubSetPart", 0.2);
221
222        iTabuSize = properties.getPropertyInt("Lecture.TabuSize", 20);
223        if (iTabuSize > 0)
224            iTabu = new ArrayList<Lecture>(iTabuSize);
225
226        iVariableChanceIteration = properties.getPropertyInt("Lecture.VariableChanceIteration", 1000);
227        iVariableChanceProb = properties.getPropertyDouble("Lecture.VariableChanceProb", 0.05);
228    }
229
230    @Override
231    public void init(Solver<Lecture, Placement> solver) {
232        for (Extension<Lecture, Placement> extension : solver.getExtensions()) {
233            if (MacPropagation.class.isInstance(extension))
234                iProp = (MacPropagation<Lecture, Placement>) extension;
235        }
236    }
237
238    @Override
239    public Lecture selectVariable(Solution<Lecture, Placement> solution) {
240        TimetableModel model = (TimetableModel) solution.getModel();
241        Collection<Lecture> unassignedVariables = model.unassignedVariables();
242        if (iInteractiveMode) {
243            // remove variables that have no values
244            unassignedVariables = new ArrayList<Lecture>(unassignedVariables.size());
245            for (Lecture variable : model.unassignedVariables()) {
246                if (!variable.values().isEmpty())
247                    unassignedVariables.add(variable);
248            }
249        }
250
251        if (unassignedVariables.isEmpty()) {
252            Collection<Lecture> variables = model.perturbVariables();
253            if (variables.isEmpty())
254                variables = model.assignedVariables();
255
256            if (iRW && ToolBox.random() <= iRandomWalkProb)
257                return ToolBox.random(variables);
258
259            List<Lecture> selectionVariables = new ArrayList<Lecture>();
260            double worstValue = 0.0; 
261
262            for (Iterator<Lecture> i1 = (iSubSetSelection ? ToolBox.subSet(variables, iSelectionSubSetPart,
263                    iSelectionSubSetMinSize) : variables).iterator(); i1.hasNext();) {
264                Lecture selectedVariable = i1.next();
265
266                if (iTabu != null && iTabu.contains(selectedVariable))
267                    continue;
268
269                double value = selectedVariable.getAssignment().toDouble();
270                
271                if (selectionVariables.isEmpty() || value > worstValue) {
272                    selectionVariables.clear();
273                    selectionVariables.add(selectedVariable);
274                    worstValue = value;
275                } else if (worstValue == value) {
276                    selectionVariables.add(selectedVariable);
277                }
278            }
279
280            Lecture selectedVariable = ToolBox.random(selectionVariables);
281
282            if (selectedVariable == null)
283                selectedVariable = ToolBox.random(variables);
284
285            if (selectedVariable != null && iTabu != null) {
286                if (iTabu.size() == iTabuPos)
287                    iTabu.add(selectedVariable);
288                else
289                    iTabu.set(iTabuPos, selectedVariable);
290                iTabuPos = (iTabuPos + 1) % iTabuSize;
291            }
292
293            return selectedVariable;
294        } else {
295            if (iVariableChanceIteration > 0) {
296                List<Lecture> variablesWithChance = new ArrayList<Lecture>(unassignedVariables.size());
297                for (Lecture v : unassignedVariables) {
298                    if (v.countAssignments() > iVariableChanceIteration)
299                        continue;
300                    variablesWithChance.add(v);
301                }
302
303                if (variablesWithChance.isEmpty() && ToolBox.random() <= iVariableChanceProb
304                        && !model.assignedVariables().isEmpty())
305                    return ToolBox.random(model.assignedVariables());
306
307                if (ToolBox.random() <= iRandomWalkProb) {
308                    if (!variablesWithChance.isEmpty())
309                        return ToolBox.random(variablesWithChance);
310                    else
311                        return ToolBox.random(unassignedVariables);
312                }
313            } else {
314                if (ToolBox.random() <= iRandomWalkProb)
315                    return ToolBox.random(unassignedVariables);
316            }
317
318            if (iProp != null && iUnassignWhenNotGood) {
319                List<Lecture> noGoodVariables = new ArrayList<Lecture>();
320                for (Iterator<Lecture> i1 = ToolBox.subSet(unassignedVariables, iSelectionSubSetPart,
321                        iSelectionSubSetMinSize).iterator(); i1.hasNext();) {
322                    Lecture variable = i1.next();
323                    if (iProp.goodValues(variable).isEmpty())
324                        noGoodVariables.add(variable);
325                }
326                if (!noGoodVariables.isEmpty()) {
327                    if (ToolBox.random() < 0.02)
328                        return ToolBox.random(model.assignedVariables());
329                    for (int attempt = 0; attempt < 10; attempt++) {
330                        Lecture noGoodVariable = ToolBox.random(noGoodVariables);
331                        Placement noGoodValue = ToolBox.random(noGoodVariable.values());
332                        if (!iProp.noGood(noGoodValue).isEmpty())
333                            return ToolBox.random(iProp.noGood(noGoodValue)).variable();
334                    }
335                }
336            }
337
338            if (iRouletteWheelSelection) {
339                int iMaxDomainSize = 0;
340                int iMaxGoodDomainSize = 0;
341                int iMaxConstraints = 0;
342                long iMaxNrAssignments = 0;
343                Collection<Lecture> variables = (iSubSetSelection ? ToolBox.subSet(unassignedVariables,
344                        iSelectionSubSetPart, iSelectionSubSetMinSize) : unassignedVariables);
345                for (Lecture variable : variables) {
346
347                    if (iTabu != null && iTabu.contains(variable))
348                        continue;
349
350                    iMaxDomainSize = Math.max(iMaxDomainSize, variable.values().size());
351                    iMaxGoodDomainSize = (iProp == null ? 0 : Math.max(iMaxGoodDomainSize, iProp.goodValues(variable)
352                            .size()));
353                    iMaxConstraints = Math.max(iMaxConstraints, variable.constraints().size());
354                    iMaxNrAssignments = Math.max(iMaxNrAssignments, variable.countAssignments());
355                }
356
357                List<Integer> points = new ArrayList<Integer>();
358                int totalPoints = 0;
359
360                for (Lecture variable : variables) {
361
362                    long pointsThisVariable = Math
363                            .round(iDomainSizeWeight
364                                    * (((double) (iMaxDomainSize - variable.values().size())) / ((double) iMaxDomainSize))
365                                    + (iProp == null ? 0.0
366                                            : iGoodValuesWeight
367                                                    * (((double) (iMaxGoodDomainSize - iProp.goodValues(variable)
368                                                            .size())) / ((double) iMaxGoodDomainSize)))
369                                    + iNrAssignmentsWeight
370                                    * (((double) variable.countAssignments()) / ((double) iMaxNrAssignments))
371                                    + iConstraintsWeight
372                                    * (((double) (iMaxConstraints - variable.constraints().size())) / ((double) iMaxConstraints))
373                                    + iInitialAssignmentWeight
374                                    * (variable.getInitialAssignment() != null ? model.conflictValues(
375                                            variable.getInitialAssignment()).size() : 0.0));
376                    if (pointsThisVariable > 0) {
377                        totalPoints += pointsThisVariable;
378                        points.add(totalPoints);
379                    }
380                }
381
382                if (totalPoints > 0) {
383                    int rndPoints = ToolBox.random(totalPoints);
384                    Iterator<Lecture> x = variables.iterator();
385                    for (int i = 0; x.hasNext() && i < points.size(); i++) {
386                        Lecture variable = x.next();
387                        int tp = points.get(i);
388                        if (tp > rndPoints) {
389                            if (variable != null && iTabu != null) {
390                                if (iTabu.size() == iTabuPos)
391                                    iTabu.add(variable);
392                                else
393                                    iTabu.set(iTabuPos, variable);
394                                iTabuPos = (iTabuPos + 1) % iTabuSize;
395                            }
396                            return variable;
397                        }
398                    }
399                }
400
401            } else {
402
403                List<Lecture> selectionVariables = null;
404                long bestGood = 0;
405                for (Iterator<Lecture> i = ToolBox.subSet(unassignedVariables, iSelectionSubSetPart,
406                        iSelectionSubSetMinSize).iterator(); i.hasNext();) {
407                    Lecture variable = i.next();
408
409                    if (iTabu != null && iTabu.contains(variable))
410                        continue;
411
412                    long good = (long) (iDomainSizeWeight * variable.values().size() + iGoodValuesWeight
413                            * (iProp == null ? 0 : iProp.goodValues(variable).size()) + iNrAssignmentsWeight
414                            * variable.countAssignments() + iConstraintsWeight * variable.constraints().size() + iInitialAssignmentWeight
415                            * (variable.getInitialAssignment() != null ? model.conflictValues(
416                                    variable.getInitialAssignment()).size() : 0.0));
417                    if (selectionVariables == null || bestGood > good) {
418                        if (selectionVariables == null)
419                            selectionVariables = new ArrayList<Lecture>();
420                        else
421                            selectionVariables.clear();
422                        bestGood = good;
423                        selectionVariables.add(variable);
424                    } else if (good == bestGood) {
425                        selectionVariables.add(variable);
426                    }
427                }
428
429                if (!selectionVariables.isEmpty()) {
430                    Lecture selectedVariable = ToolBox.random(selectionVariables);
431
432                    if (selectedVariable != null && iTabu != null) {
433                        if (iTabu.size() == iTabuPos)
434                            iTabu.add(selectedVariable);
435                        else
436                            iTabu.set(iTabuPos, selectedVariable);
437                        iTabuPos = (iTabuPos + 1) % iTabuSize;
438                    }
439
440                    return selectedVariable;
441                }
442            }
443
444            Lecture selectedVariable = ToolBox.random(unassignedVariables);
445
446            if (selectedVariable != null && iTabu != null) {
447                if (iTabu.size() == iTabuPos)
448                    iTabu.add(selectedVariable);
449                else
450                    iTabu.set(iTabuPos, selectedVariable);
451                iTabuPos = (iTabuPos + 1) % iTabuSize;
452            }
453
454            return selectedVariable;
455        }
456    }
457
458}