001    package net.sf.cpsolver.coursett.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashMap;
006    import java.util.Iterator;
007    import java.util.List;
008    import java.util.Map;
009    import java.util.Set;
010    
011    import net.sf.cpsolver.coursett.model.Lecture;
012    import net.sf.cpsolver.coursett.model.Placement;
013    import net.sf.cpsolver.coursett.model.TimetableModel;
014    import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
015    import net.sf.cpsolver.ifs.model.Neighbour;
016    import net.sf.cpsolver.ifs.solution.Solution;
017    import net.sf.cpsolver.ifs.solver.Solver;
018    import net.sf.cpsolver.ifs.util.DataProperties;
019    import net.sf.cpsolver.ifs.util.JProf;
020    import net.sf.cpsolver.ifs.util.ToolBox;
021    
022    /**
023     * Neighbour selection which does the standard time neighbour selection most of
024     * the time, however, the very best neighbour is selected time to time (using
025     * backtracking based search).
026     * 
027     * @see StandardNeighbourSelection
028     * @version CourseTT 1.2 (University Course Timetabling)<br>
029     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
030     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
031     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
032     * <br>
033     *          This library is free software; you can redistribute it and/or modify
034     *          it under the terms of the GNU Lesser General Public License as
035     *          published by the Free Software Foundation; either version 3 of the
036     *          License, or (at your option) any later version. <br>
037     * <br>
038     *          This library is distributed in the hope that it will be useful, but
039     *          WITHOUT ANY WARRANTY; without even the implied warranty of
040     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
041     *          Lesser General Public License for more details. <br>
042     * <br>
043     *          You should have received a copy of the GNU Lesser General Public
044     *          License along with this library; if not see
045     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
046     */
047    
048    public class NeighbourSelectionWithSuggestions extends StandardNeighbourSelection<Lecture, Placement> {
049        private double iSuggestionProbability = 0.1;
050        private double iSuggestionProbabilityAllAssigned = 0.5;
051        private int iSuggestionTimeout = 500;
052        private int iSuggestionDepth = 4;
053    
054        private Solution<Lecture, Placement> iSolution = null;
055        private SuggestionNeighbour iSuggestionNeighbour = null;
056        private double iValue = 0;
057        private int iNrAssigned = 0;
058        private boolean iTimeoutReached = false;
059    
060        public NeighbourSelectionWithSuggestions(DataProperties properties) throws Exception {
061            super(properties);
062            iSuggestionProbability = properties
063                    .getPropertyDouble("Neighbour.SuggestionProbability", iSuggestionProbability);
064            iSuggestionProbabilityAllAssigned = properties.getPropertyDouble("Neighbour.SuggestionProbabilityAllAssigned",
065                    iSuggestionProbabilityAllAssigned);
066            iSuggestionTimeout = properties.getPropertyInt("Neighbour.SuggestionTimeout", iSuggestionTimeout);
067            iSuggestionDepth = properties.getPropertyInt("Neighbour.SuggestionDepth", iSuggestionDepth);
068        }
069    
070        public NeighbourSelectionWithSuggestions(Solver<Lecture, Placement> solver) throws Exception {
071            this(solver.getProperties());
072            init(solver);
073        }
074    
075        @Override
076        public void init(Solver<Lecture, Placement> solver) {
077            super.init(solver);
078        }
079    
080        @Override
081        public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
082            Neighbour<Lecture, Placement> neighbour = null;
083            if (solution.getModel().unassignedVariables().isEmpty()) {
084                for (int d = iSuggestionDepth; d > 1; d--) {
085                    if (ToolBox.random() < Math.pow(iSuggestionProbabilityAllAssigned, d - 1)) {
086                        neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d);
087                        break;
088                    }
089                }
090            } else {
091                for (int d = iSuggestionDepth; d > 1; d--) {
092                    if (ToolBox.random() < Math.pow(iSuggestionProbability, d - 1)) {
093                        neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d);
094                        break;
095                    }
096                }
097            }
098            return (neighbour != null ? neighbour : super.selectNeighbour(solution));
099        }
100    
101        public synchronized Neighbour<Lecture, Placement> selectNeighbourWithSuggestions(
102                Solution<Lecture, Placement> solution, Lecture lecture, int depth) {
103            if (lecture == null)
104                return null;
105    
106            iSolution = solution;
107            iSuggestionNeighbour = null;
108            iValue = solution.getModel().getTotalValue();
109            iNrAssigned = solution.getModel().assignedVariables().size();
110            iTimeoutReached = false;
111    
112            synchronized (solution) {
113                // System.out.println("BEFORE BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
114    
115                List<Lecture> initialLectures = new ArrayList<Lecture>(1);
116                initialLectures.add(lecture);
117                backtrack(JProf.currentTimeMillis(), initialLectures, new HashMap<Lecture, Placement>(),
118                        new HashMap<Lecture, Placement>(), depth);
119    
120                // System.out.println("AFTER  BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
121            }
122    
123            return iSuggestionNeighbour;
124        }
125    
126        private boolean containsCommited(Collection<Placement> values) {
127            if (((TimetableModel) iSolution.getModel()).hasConstantVariables()) {
128                for (Placement placement : values) {
129                    Lecture lecture = placement.variable();
130                    if (lecture.isCommitted())
131                        return true;
132                }
133            }
134            return false;
135        }
136    
137        private void backtrack(long startTime, List<Lecture> initialLectures, Map<Lecture, Placement> resolvedLectures,
138                HashMap<Lecture, Placement> conflictsToResolve, int depth) {
139            int nrUnassigned = conflictsToResolve.size();
140            if ((initialLectures == null || initialLectures.isEmpty()) && nrUnassigned == 0) {
141                if (iSolution.getModel().assignedVariables().size() > iNrAssigned
142                        || (iSolution.getModel().assignedVariables().size() == iNrAssigned && iValue > iSolution.getModel().getTotalValue())) {
143                    if (iSuggestionNeighbour == null || iSuggestionNeighbour.compareTo(iSolution) >= 0)
144                        iSuggestionNeighbour = new SuggestionNeighbour(resolvedLectures);
145                }
146                return;
147            }
148            if (depth <= 0)
149                return;
150            if (iTimeoutReached || iSuggestionTimeout > 0 && JProf.currentTimeMillis() - startTime > iSuggestionTimeout) {
151                iTimeoutReached = true;
152                return;
153            }
154            
155            for (Lecture lecture: initialLectures != null && !initialLectures.isEmpty() ? initialLectures : new ArrayList<Lecture>(conflictsToResolve.keySet())) {
156                if (iTimeoutReached) break;
157                if (resolvedLectures.containsKey(lecture))
158                    continue;
159                placements: for (Placement placement : lecture.values()) {
160                    if (iTimeoutReached) break;
161                    if (placement.equals(lecture.getAssignment()))
162                        continue;
163                    if (placement.isHard())
164                        continue;
165                    Set<Placement> conflicts = iSolution.getModel().conflictValues(placement);
166                    if (nrUnassigned + conflicts.size() > depth)
167                        continue;
168                    if (conflicts.contains(placement))
169                        continue;
170                    if (containsCommited(conflicts))
171                        continue;
172                    for (Iterator<Placement> i = conflicts.iterator();i.hasNext();) {
173                        Placement c = i.next();
174                        if (resolvedLectures.containsKey(c.variable()))
175                            continue placements;
176                    }
177                    Placement cur = lecture.getAssignment();
178                    for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
179                        Placement c = i.next();
180                        c.variable().unassign(0);
181                    }
182                    if (cur != null)
183                        lecture.unassign(0);
184                    lecture.assign(0, placement);
185                    for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
186                        Placement c = i.next();
187                        conflictsToResolve.put(c.variable(), c);
188                    }
189                    Placement resolvedConf = conflictsToResolve.remove(lecture);
190                    resolvedLectures.put(lecture, placement);
191                    backtrack(startTime, null, resolvedLectures, conflictsToResolve, depth - 1);
192                    resolvedLectures.remove(lecture);
193                    if (cur == null)
194                        lecture.unassign(0);
195                    else
196                        lecture.assign(0, cur);
197                    for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
198                        Placement p = i.next();
199                        p.variable().assign(0, p);
200                        conflictsToResolve.remove(p.variable());
201                    }
202                    if (resolvedConf != null)
203                        conflictsToResolve.put(lecture, resolvedConf);
204                }
205            }
206        }
207    
208        public class SuggestionNeighbour extends Neighbour<Lecture, Placement> {
209            private double iValue = 0;
210            private List<Placement> iDifferentAssignments = null;
211    
212            public SuggestionNeighbour(Map<Lecture, Placement> resolvedLectures) {
213                iValue = iSolution.getModel().getTotalValue();
214                iDifferentAssignments = new ArrayList<Placement>(resolvedLectures.values());
215            }
216    
217            @Override
218            public double value() {
219                return iValue;
220            }
221    
222            @Override
223            public void assign(long iteration) {
224                // System.out.println("START ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
225                // System.out.println("  "+this);
226                for (Placement p : iDifferentAssignments) {
227                    if (p.variable().getAssignment() != null)
228                        p.variable().unassign(iteration);
229                }
230                for (Placement p : iDifferentAssignments) {
231                    p.variable().assign(iteration, p);
232                }
233                // System.out.println("END ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
234            }
235    
236            public int compareTo(Solution<Lecture, Placement> solution) {
237                return Double.compare(iValue, iSolution.getModel().getTotalValue());
238            }
239    
240            @Override
241            public String toString() {
242                StringBuffer sb = new StringBuffer("Suggestion{value=" + (iValue - iSolution.getModel().getTotalValue()) + ": ");
243                for (Iterator<Placement> e = iDifferentAssignments.iterator(); e.hasNext();) {
244                    Placement p = e.next();
245                    sb.append("\n    " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : ""));
246                }
247                sb.append("}");
248                return sb.toString();
249            }
250        }
251    }