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