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