001    package net.sf.cpsolver.coursett.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Iterator;
006    import java.util.List;
007    
008    import net.sf.cpsolver.coursett.model.Lecture;
009    import net.sf.cpsolver.coursett.model.Placement;
010    import net.sf.cpsolver.coursett.model.TimetableModel;
011    import net.sf.cpsolver.ifs.extension.Extension;
012    import net.sf.cpsolver.ifs.extension.MacPropagation;
013    import net.sf.cpsolver.ifs.heuristics.VariableSelection;
014    import net.sf.cpsolver.ifs.solution.Solution;
015    import net.sf.cpsolver.ifs.solver.Solver;
016    import net.sf.cpsolver.ifs.util.DataProperties;
017    import 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 Tomas Muller<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     */
176    public 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    }