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 }