001package net.sf.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;
010
011import net.sf.cpsolver.coursett.model.Lecture;
012import net.sf.cpsolver.coursett.model.Placement;
013import net.sf.cpsolver.coursett.model.TimetableModel;
014import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
015import net.sf.cpsolver.ifs.model.Neighbour;
016import net.sf.cpsolver.ifs.solution.Solution;
017import net.sf.cpsolver.ifs.solver.Solver;
018import net.sf.cpsolver.ifs.util.DataProperties;
019import net.sf.cpsolver.ifs.util.JProf;
020import 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 Tomáš Müller<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
048public 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}