001    package net.sf.cpsolver.coursett.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.List;
006    import java.util.Set;
007    
008    import net.sf.cpsolver.coursett.criteria.TimetablingCriterion;
009    import net.sf.cpsolver.coursett.model.Lecture;
010    import net.sf.cpsolver.coursett.model.Placement;
011    import net.sf.cpsolver.coursett.model.TimetableModel;
012    import net.sf.cpsolver.ifs.criteria.Criterion;
013    import net.sf.cpsolver.ifs.extension.Extension;
014    import net.sf.cpsolver.ifs.extension.MacPropagation;
015    import net.sf.cpsolver.ifs.heuristics.ValueSelection;
016    import net.sf.cpsolver.ifs.model.Constraint;
017    import net.sf.cpsolver.ifs.model.WeakeningConstraint;
018    import net.sf.cpsolver.ifs.solution.Solution;
019    import net.sf.cpsolver.ifs.solver.Solver;
020    import net.sf.cpsolver.ifs.util.DataProperties;
021    import net.sf.cpsolver.ifs.util.ToolBox;
022    
023    /**
024     * Placement (value) selection. <br>
025     * <br>
026     * We have implemented a hierarchical handling of the value selection criteria
027     * (see {@link HeuristicSelector}). <br>
028     * <br>
029     * The value selection heuristics also allow for random selection of a value
030     * with a given probability (random walk, e.g., 2%) and, in the case of MPP, to
031     * select the initial value (if it exists) with a given probability (e.g., 70%). <br>
032     * <br>
033     * Parameters (general):
034     * <table border='1'>
035     * <tr>
036     * <th>Parameter</th>
037     * <th>Type</th>
038     * <th>Comment</th>
039     * </tr>
040     * <tr>
041     * <td>Placement.RandomWalkProb</td>
042     * <td>{@link Double}</td>
043     * <td>Random walk probability</td>
044     * </tr>
045     * <tr>
046     * <td>Placement.GoodSelectionProb</td>
047     * <td>{@link Double}</td>
048     * <td>Good value (not removed from domain) selection probability (MAC related)</td>
049     * </tr>
050     * <tr>
051     * <td>Placement.TabuLength</td>
052     * <td>{@link Integer}</td>
053     * <td>Tabu-list length (-1 means do not use tabu-list)</td>
054     * </tr>
055     * <tr>
056     * <td>Placement.MPP_InitialProb</td>
057     * <td>{@link Double}</td>
058     * <td>MPP initial selection probability</td>
059     * </tr>
060     * <tr>
061     * <td>Placement.MPP_Limit</td>
062     * <td>{@link Integer}</td>
063     * <td>MPP: limit on the number of perturbations (-1 for no limit)</td>
064     * </tr>
065     * <tr>
066     * <td>Placement.MPP_PenaltyLimit</td>
067     * <td>{@link Double}</td>
068     * <td>MPP: limit on the perturbations penalty (-1 for no limit)</td>
069     * </tr>
070     * </table>
071     * <br>
072     * Parameters (for each level of selection):
073     * <table border='1'>
074     * <tr>
075     * <th>Parameter</th>
076     * <th>Type</th>
077     * <th>Comment</th>
078     * </tr>
079     * <tr>
080     * <td>Placement.NrAssignmentsWeight1<br>
081     * Placement.NrAssignmentsWeight2<br>
082     * Placement.NrAssignmentsWeight3</td>
083     * <td>{@link Double}</td>
084     * <td>Number of previous assignments of the value weight</td>
085     * </tr>
086     * <tr>
087     * <td>Placement.NrConflictsWeight1,2,3</td>
088     * <td>{@link Double}</td>
089     * <td>Number of conflicts weight</td>
090     * </tr>
091     * <tr>
092     * <td>Placement.WeightedConflictsWeight1,2,3</td>
093     * <td>{@link Double}</td>
094     * <td>Weighted conflicts weight (Conflict-based Statistics related)</td>
095     * </tr>
096     * <tr>
097     * <td>Placement.NrPotentialConflictsWeight1,2,3</td>
098     * <td>{@link Double}</td>
099     * <td>Number of potential conflicts weight (Conflict-based Statistics related)</td>
100     * </tr>
101     * <tr>
102     * <td>Placement.MPP_DeltaInitialAssignmentWeight1,2,3</td>
103     * <td>{@link Double}</td>
104     * <td>Delta initial assigments weight (MPP, violated initials related)</td>
105     * </tr>
106     * <tr>
107     * <td>Placement.NrHardStudConfsWeight1,2,3</td>
108     * <td>{@link Double}</td>
109     * <td>Hard student conflicts weight (student conflicts between single-section
110     * classes)</td>
111     * </tr>
112     * <tr>
113     * <td>Placement.NrStudConfsWeight1,2,3</td>
114     * <td>{@link Double}</td>
115     * <td>Student conflicts weight</td>
116     * </tr>
117     * <tr>
118     * <td>Placement.TimePreferenceWeight1,2,3</td>
119     * <td>{@link Double}</td>
120     * <td>Time preference weight</td>
121     * </tr>
122     * <tr>
123     * <td>Placement.DeltaTimePreferenceWeight1,2,3</td>
124     * <td>{@link Double}</td>
125     * <td>Time preference delta weight (difference between before and after
126     * assignemnt of the value)</td>
127     * </tr>
128     * <tr>
129     * <td>Placement.ConstrPreferenceWeight1,2,3</td>
130     * <td>{@link Double}</td>
131     * <td>Constraint preference weight</td>
132     * </tr>
133     * <tr>
134     * <td>Placement.RoomPreferenceWeight1,2,3</td>
135     * <td>{@link Double}</td>
136     * <td>Room preference weight</td>
137     * </tr>
138     * <tr>
139     * <td>Placement.UselessSlotsWeight1,2,3</td>
140     * <td>{@link Double}</td>
141     * <td>Useless slot weight</td>
142     * </tr>
143     * <tr>
144     * <td>Placement.TooBigRoomWeight1,2,3</td>
145     * <td>{@link Double}</td>
146     * <td>Too big room weight</td>
147     * </tr>
148     * <tr>
149     * <td>Placement.DistanceInstructorPreferenceWeight1,2,3</td>
150     * <td>{@link Double}</td>
151     * <td>Distance (of the rooms of the back-to-back classes) based instructor
152     * preferences weight</td>
153     * </tr>
154     * <tr>
155     * <td>Placement.DeptSpreadPenaltyWeight1,2,3</td>
156     * <td>{@link Double}</td>
157     * <td>Department spreading: penalty of when a slot over initial allowance is
158     * used</td>
159     * </tr>
160     * <tr>
161     * <td>Placement.ThresholdKoef1,2</td>
162     * <td>{@link Double}</td>
163     * <td>Threshold koeficient of the level</td>
164     * </tr>
165     * </table>
166     * 
167     * @see PlacementSelection
168     * @version CourseTT 1.2 (University Course Timetabling)<br>
169     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
170     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
171     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
172     * <br>
173     *          This library is free software; you can redistribute it and/or modify
174     *          it under the terms of the GNU Lesser General Public License as
175     *          published by the Free Software Foundation; either version 3 of the
176     *          License, or (at your option) any later version. <br>
177     * <br>
178     *          This library is distributed in the hope that it will be useful, but
179     *          WITHOUT ANY WARRANTY; without even the implied warranty of
180     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
181     *          Lesser General Public License for more details. <br>
182     * <br>
183     *          You should have received a copy of the GNU Lesser General Public
184     *          License along with this library; if not see
185     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
186     */
187    
188    public class PlacementSelection implements ValueSelection<Lecture, Placement> {
189        static final int NR_LEVELS = 3;
190        private static final double PRECISION = 1.0;
191        private static boolean USE_THRESHOLD = true;
192        private boolean iUseThreshold = USE_THRESHOLD;
193        
194        private double iGoodSelectionProb;
195        public static final String GOOD_SELECTION_PROB = "Placement.GoodSelectionProb";
196        private double iRandomWalkProb;
197        public static final String RW_SELECTION_PROB = "Placement.RandomWalkProb";
198        private double iInitialSelectionProb;
199        public static final String INITIAL_SELECTION_PROB = "Placement.MPP_InitialProb";
200        private int iMPPLimit;
201        public static final String NR_MPP_LIMIT = "Placement.MPP_Limit";
202        private double iMPPPenaltyLimit;
203        public static final String NR_MPP_PENALTY_LIMIT = "Placement.MPP_PenaltyLimit";
204    
205        private double[] iThresholdKoef = new double[NR_LEVELS];
206        public static final String NR_THRESHOLD_KOEF = "Placement.ThresholdKoef";
207    
208        private int iTabuSize = 0;
209        private ArrayList<Placement> iTabu = null;
210        private int iTabuPos = 0;
211        public static final String TABU_LENGTH = "Placement.TabuLength";
212    
213        private MacPropagation<Lecture, Placement> iProp = null;
214    
215        private boolean iRW = false;
216        private boolean iMPP = false;
217    
218        private boolean iCanUnassingSingleton = false;
219    
220        @Override
221        public void init(Solver<Lecture, Placement> solver) {
222            for (Extension<Lecture, Placement> extension : solver.getExtensions()) {
223                if (MacPropagation.class.isInstance(extension))
224                    iProp = (MacPropagation<Lecture, Placement>) extension;
225            }
226        }
227    
228        public PlacementSelection(DataProperties properties) {
229            iMPP = properties.getPropertyBoolean("General.MPP", false);
230            iRW = properties.getPropertyBoolean("General.RandomWalk", true);
231            iCanUnassingSingleton = properties.getPropertyBoolean("Placement.CanUnassingSingleton", iCanUnassingSingleton);
232            iRandomWalkProb = (iRW ? properties.getPropertyDouble(RW_SELECTION_PROB, 0.00) : 0.0);
233            iGoodSelectionProb = properties.getPropertyDouble(GOOD_SELECTION_PROB, 1.00);
234            iInitialSelectionProb = (iMPP ? properties.getPropertyDouble(INITIAL_SELECTION_PROB, 0.75) : 0.0);
235            iMPPLimit = (iMPP ? properties.getPropertyInt(NR_MPP_LIMIT, -1) : -1);
236            iMPPPenaltyLimit = (iMPP ? properties.getPropertyDouble(NR_MPP_PENALTY_LIMIT, -1.0) : -1.0);
237            iTabuSize = properties.getPropertyInt(TABU_LENGTH, -1);
238            if (iTabuSize > 0)
239                iTabu = new ArrayList<Placement>(iTabuSize);
240            iUseThreshold = properties.getPropertyBoolean("Placement.UseThreshold", USE_THRESHOLD);
241            for (int level = 0; level < NR_LEVELS; level++)
242                iThresholdKoef[level] = (USE_THRESHOLD ? properties.getPropertyDouble(NR_THRESHOLD_KOEF + (level + 1), (level == 0 ? 0.1 : 0.0)) : 0.0);
243        }
244    
245        @Override
246        public Placement selectValue(Solution<Lecture, Placement> solution, Lecture var) {
247            if (var == null)
248                return null;
249            Lecture selectedVariable = var;
250    
251            TimetableModel model = (TimetableModel) solution.getModel();
252            if (selectedVariable.getInitialAssignment() != null) {
253                if (iMPPLimit >= 0 && model.perturbVariables().size() >= iMPPLimit) {
254                    if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
255                        return checkValue(selectedVariable.getInitialAssignment());
256                } else if (iMPPPenaltyLimit >= 0.0 && solution.getPerturbationsCounter() != null && solution.getPerturbationsCounter().getPerturbationPenalty(model) > iMPPPenaltyLimit) {
257                    if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
258                        return checkValue(selectedVariable.getInitialAssignment());
259                } else if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
260                    if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
261                        return checkValue(selectedVariable.getInitialAssignment());
262                }
263            }
264    
265            List<Placement> values = selectedVariable.values();
266            if (iRW && ToolBox.random() <= iRandomWalkProb) {
267                for (int i = 0; i < 5; i++) {
268                    Placement ret = ToolBox.random(values);
269                    if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
270                        return checkValue(ret);
271                }
272            }
273            if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
274                Collection<Placement> goodValues = iProp.goodValues(selectedVariable);
275                if (!goodValues.isEmpty())
276                    values = new ArrayList<Placement>(goodValues);
277            }
278            if (values.size() == 1) {
279                Placement ret = values.get(0);
280                if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
281                    return checkValue(ret);
282            }
283    
284            long[] bestCost = new long[NR_LEVELS];
285            List<Placement> selectionValues = null;
286    
287            HeuristicSelector<Placement> selector = (iUseThreshold ? new HeuristicSelector<Placement>(iThresholdKoef) : null);
288            for (Placement value : values) {
289                if (iTabu != null && iTabu.contains(value))
290                    continue;
291                if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
292                    continue;
293    
294                Set<Placement> conflicts = value.variable().getModel().conflictValues(value);
295                
296                if (containsItselfSingletonOrCommited(model, conflicts, value))
297                    continue;
298    
299                if (iUseThreshold) {
300                    Double flt = selector.firstLevelThreshold();
301                    double[] costs = new double[NR_LEVELS];
302                    for (int level = 0; level < NR_LEVELS; level++) {
303                        costs[level] = getCost(level, value, conflicts);
304                        if (level == 0 && flt != null && costs[0] > flt.doubleValue()) {
305                            break;
306                        }
307                    }
308                    if (flt != null && costs[0] > flt.doubleValue())
309                        continue;
310                    selector.add(costs, value);
311                } else {
312                    boolean fail = false;
313                    boolean best = false;
314                    for (int level = 0; !fail && level < 1; level++) {
315                        double val = getCost(level, value, conflicts);
316                        long cost = Math.round(PRECISION * val);
317                        if (selectionValues != null && !best) {
318                            if (cost > bestCost[level]) {
319                                fail = true;
320                            }
321                            if (cost < bestCost[level]) {
322                                bestCost[level] = cost;
323                                selectionValues.clear();
324                                best = true;
325                            }
326                        } else {
327                            bestCost[level] = cost;
328                        }
329                    }
330                    if (selectionValues == null)
331                        selectionValues = new ArrayList<Placement>(values.size());
332                    if (!fail)
333                        selectionValues.add(value);
334                }
335            }
336            // ToolBox.print("Best "+selectionValues.size()+" locations for variable "+selectedVariable.getId()+" have "+bestConflicts+" conflicts ("+bestRemovals+" weighted) and "+bestStudentConflicts+" ("+bestOriginalStudentConflicts+" * "+bestKoef+" + "+bestPenalty+") preference.");
337            Placement selectedValue = null;
338            if (iUseThreshold) {
339                List<HeuristicSelector<Placement>.Element> selectionElements = selector.selection();
340    
341                if (selectedVariable.getInitialAssignment() != null) {
342                    for (HeuristicSelector<Placement>.Element element : selectionElements) {
343                        Placement value = element.getObject();
344                        if (value.equals(selectedVariable.getInitialAssignment())) {
345                            selectedValue = value;
346                            break;
347                        }
348                    }
349                    // &&
350                    // selectionValues.contains(selectedVariable.getInitialAssignment()))
351                    // return selectedVariable.getInitialAssignment();
352                }
353    
354                if (selectedValue == null) {
355                    HeuristicSelector<Placement>.Element selection = ToolBox.random(selectionElements);
356                    selectedValue = (selection == null ? null : selection.getObject());
357                }
358            } else {
359                if (selectedVariable.getInitialAssignment() != null
360                        && selectionValues.contains(selectedVariable.getInitialAssignment()))
361                    return checkValue(selectedVariable.getInitialAssignment());
362                selectedValue = ToolBox.random(selectionValues);
363            }
364            if (selectedValue != null && iTabu != null) {
365                if (iTabu.size() == iTabuPos)
366                    iTabu.add(selectedValue);
367                else
368                    iTabu.set(iTabuPos, selectedValue);
369                iTabuPos = (iTabuPos + 1) % iTabuSize;
370            }
371            return checkValue(selectedValue);
372        }
373    
374        public boolean containsItselfSingletonOrCommited(TimetableModel model, Set<Placement> values,
375                Placement selectedValue) {
376            if (values.contains(selectedValue))
377                return true;
378            if (model.hasConstantVariables()) {
379                for (Placement placement : values) {
380                    Lecture lecture = placement.variable();
381                    if (lecture.isCommitted())
382                        return true;
383                    if (!iCanUnassingSingleton && lecture.isSingleton())
384                        return true;
385                }
386                return false;
387            } else {
388                if (iCanUnassingSingleton)
389                    return false;
390                for (Placement placement : values) {
391                    Lecture lecture = placement.variable();
392                    if (lecture.isSingleton())
393                        return true;
394                }
395                return false;
396            }
397        }
398    
399        private Placement checkValue(Placement aValue) {
400            if (aValue == null)
401                return null;
402            for (Constraint<Lecture, Placement> c : aValue.variable().getWeakeningConstraints()) {
403                if (c.inConflict(aValue))
404                    ((WeakeningConstraint<?,?>) c).weaken();
405            }
406            return aValue;
407        }
408        
409        private double getCost(int level, Placement value, Set<Placement> conflicts) {
410            double ret = 0.0;
411            for (Criterion<Lecture, Placement> criterion: value.variable().getModel().getCriteria()) {
412                if (criterion instanceof TimetablingCriterion) {
413                    double w = ((TimetablingCriterion)criterion).getPlacementSelectionWeight(level);
414                    if (w != 0.0)
415                        ret += w * criterion.getValue(value, conflicts);
416                } else {
417                    ret += criterion.getWeightedValue(value, conflicts);
418                }
419            }
420            return ret;
421        }
422        
423    }