001 package net.sf.cpsolver.ifs.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.Iterator;
006 import java.util.List;
007 import java.util.Set;
008
009 import net.sf.cpsolver.ifs.constant.ConstantVariable;
010 import net.sf.cpsolver.ifs.extension.ConflictStatistics;
011 import net.sf.cpsolver.ifs.extension.Extension;
012 import net.sf.cpsolver.ifs.model.Neighbour;
013 import net.sf.cpsolver.ifs.model.Value;
014 import net.sf.cpsolver.ifs.model.Variable;
015 import net.sf.cpsolver.ifs.solution.Solution;
016 import net.sf.cpsolver.ifs.solver.Solver;
017 import net.sf.cpsolver.ifs.util.DataProperties;
018 import net.sf.cpsolver.ifs.util.JProf;
019
020 import org.apache.log4j.Logger;
021
022 /**
023 * Backtracking-based neighbour selection. A best neighbour that is found by a
024 * backtracking-based algorithm within a limited depth from a selected variable
025 * is returned. <br>
026 * <br>
027 * Parameters: <br>
028 * <table border='1'>
029 * <tr>
030 * <th>Parameter</th>
031 * <th>Type</th>
032 * <th>Comment</th>
033 * </tr>
034 * <tr>
035 * <td>Neighbour.BackTrackTimeout</td>
036 * <td>{@link Integer}</td>
037 * <td>Timeout for each neighbour selection (in milliseconds).</td>
038 * </tr>
039 * <tr>
040 * <td>Neighbour.BackTrackDepth</td>
041 * <td>{@link Integer}</td>
042 * <td>Limit of search depth.</td>
043 * </tr>
044 * </table>
045 *
046 * <br>
047 * <br>
048 *
049 * @version StudentSct 1.2 (Student Sectioning)<br>
050 * Copyright (C) 2007 - 2010 Tomas Muller<br>
051 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
052 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
053 * <br>
054 * This library is free software; you can redistribute it and/or modify
055 * it under the terms of the GNU Lesser General Public License as
056 * published by the Free Software Foundation; either version 3 of the
057 * License, or (at your option) any later version. <br>
058 * <br>
059 * This library is distributed in the hope that it will be useful, but
060 * WITHOUT ANY WARRANTY; without even the implied warranty of
061 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
062 * Lesser General Public License for more details. <br>
063 * <br>
064 * You should have received a copy of the GNU Lesser General Public
065 * License along with this library; if not see
066 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
067 */
068
069 public class BacktrackNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends
070 StandardNeighbourSelection<V, T> {
071 private ConflictStatistics<V, T> iStat = null;
072 private static Logger sLog = Logger.getLogger(BacktrackNeighbourSelection.class);
073 private int iTimeout = 5000;
074 private int iDepth = 4;
075
076 protected Solution<V, T> iSolution = null;
077 protected BackTrackNeighbour iBackTrackNeighbour = null;
078 protected double iValue = 0;
079 private int iNrAssigned = 0;
080 private long iT0, iT1;
081 private boolean iTimeoutReached = false;
082 private int iMaxIters = -1, iNrIters = 0;
083 private boolean iMaxItersReached = false;
084
085 /**
086 * Constructor
087 *
088 * @param properties
089 * configuration
090 * @throws Exception
091 */
092 public BacktrackNeighbourSelection(DataProperties properties) throws Exception {
093 super(properties);
094 iTimeout = properties.getPropertyInt("Neighbour.BackTrackTimeout", iTimeout);
095 iDepth = properties.getPropertyInt("Neighbour.BackTrackDepth", iDepth);
096 iMaxIters = properties.getPropertyInt("Neighbour.BackTrackMaxIters", iMaxIters);
097 }
098
099 /** Solver initialization */
100 @Override
101 public void init(Solver<V, T> solver) {
102 super.init(solver);
103 for (Extension<V, T> extension : solver.getExtensions()) {
104 if (ConflictStatistics.class.isInstance(extension))
105 iStat = (ConflictStatistics<V, T>) extension;
106 }
107 }
108
109 /**
110 * Select neighbour. The standard variable selection (see
111 * {@link StandardNeighbourSelection#getVariableSelection()}) is used to
112 * select a variable. A backtracking of a limited depth is than employed
113 * from this variable. The best assignment found is returned (see
114 * {@link BackTrackNeighbour}).
115 **/
116 @Override
117 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
118 return selectNeighbour(solution, getVariableSelection().selectVariable(solution));
119 }
120
121 /**
122 * Select neighbour -- starts from the provided variable. A backtracking of
123 * a limited depth is employed from the given variable. The best assignment
124 * found is returned (see {@link BackTrackNeighbour}).
125 **/
126 public synchronized Neighbour<V, T> selectNeighbour(Solution<V, T> solution, V variable) {
127 if (variable == null)
128 return null;
129
130 iSolution = solution;
131 iBackTrackNeighbour = null;
132 iValue = solution.getModel().getTotalValue();
133 iNrAssigned = solution.getModel().assignedVariables().size();
134 iT0 = JProf.currentTimeMillis();
135 iNrIters = 0;
136 iTimeoutReached = false;
137 iMaxItersReached = false;
138
139 synchronized (solution) {
140 if (sLog.isDebugEnabled())
141 sLog.debug("-- before BT (" + variable.getName() + "): nrAssigned="
142 + iSolution.getModel().assignedVariables().size() + ", value="
143 + iSolution.getModel().getTotalValue());
144
145 List<V> variables2resolve = new ArrayList<V>(1);
146 variables2resolve.add(variable);
147 backtrack(variables2resolve, 0, iDepth);
148
149 if (sLog.isDebugEnabled())
150 sLog.debug("-- after BT (" + variable.getName() + "): nrAssigned="
151 + iSolution.getModel().assignedVariables().size() + ", value="
152 + iSolution.getModel().getTotalValue());
153 }
154
155 iT1 = JProf.currentTimeMillis();
156
157 if (sLog.isDebugEnabled())
158 sLog.debug("-- selected neighbour: " + iBackTrackNeighbour);
159 return iBackTrackNeighbour;
160 }
161
162 /** Time needed to find a neighbour (last call of selectNeighbour method) */
163 public long getTime() {
164 return iT1 - iT0;
165 }
166
167 /**
168 * True, if timeout was reached during the last call of selectNeighbour
169 * method
170 */
171 public boolean isTimeoutReached() {
172 return iTimeoutReached;
173 }
174
175 /**
176 * True, if the maximum number of iterations was reached by the last call of
177 * selectNeighbour method
178 */
179 public boolean isMaxItersReached() {
180 return iMaxItersReached;
181 }
182
183 private boolean containsConstantValues(Collection<T> values) {
184 for (T value : values) {
185 if (value.variable() instanceof ConstantVariable && ((ConstantVariable) value.variable()).isConstant())
186 return true;
187 }
188 return false;
189 }
190
191 /** List of values of the given variable that will be considered */
192 protected Iterator<T> values(V variable) {
193 return variable.values().iterator();
194 }
195
196 /** Check bound */
197 protected boolean checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts) {
198 int nrUnassigned = variables2resolve.size() - idx;
199 if ((nrUnassigned + conflicts.size() > depth)) {
200 if (sLog.isDebugEnabled())
201 sLog.debug(" -- too deap");
202 return false;
203 }
204 if (containsConstantValues(conflicts)) {
205 if (sLog.isDebugEnabled())
206 sLog.debug(" -- contains constants values");
207 return false;
208 }
209 boolean containAssigned = false;
210 for (Iterator<T> i = conflicts.iterator(); !containAssigned && i.hasNext();) {
211 T conflict = i.next();
212 int confIdx = variables2resolve.indexOf(conflict.variable());
213 if (confIdx >= 0 && confIdx <= idx) {
214 if (sLog.isDebugEnabled())
215 sLog.debug(" -- contains resolved variable " + conflict.variable());
216 containAssigned = true;
217 }
218 }
219 if (containAssigned)
220 return false;
221 return true;
222 }
223
224 /** Check whether backtrack can continue */
225 protected boolean canContinue(List<V> variables2resolve, int idx, int depth) {
226 if (depth <= 0) {
227 if (sLog.isDebugEnabled())
228 sLog.debug(" -- depth reached");
229 return false;
230 }
231 if (iTimeoutReached) {
232 if (sLog.isDebugEnabled())
233 sLog.debug(" -- timeout reached");
234 return false;
235 }
236 if (iMaxItersReached) {
237 if (sLog.isDebugEnabled())
238 sLog.debug(" -- max number of iterations reached");
239 return false;
240 }
241 return true;
242 }
243
244 protected boolean canContinueEvaluation() {
245 return !iTimeoutReached && !iMaxItersReached;
246 }
247
248 /** Backtracking */
249 protected void backtrack(List<V> variables2resolve, int idx, int depth) {
250 if (sLog.isDebugEnabled())
251 sLog.debug(" -- bt[" + depth + "]: " + idx + " of " + variables2resolve.size() + " " + variables2resolve);
252 if (!iTimeoutReached && iTimeout > 0 && JProf.currentTimeMillis() - iT0 > iTimeout)
253 iTimeoutReached = true;
254 if (!iMaxItersReached && iMaxIters > 0 && iNrIters++ > iMaxIters)
255 iMaxItersReached = true;
256 int nrUnassigned = variables2resolve.size() - idx;
257 if (nrUnassigned == 0) {
258 if (sLog.isDebugEnabled())
259 sLog.debug(" -- all assigned");
260 if (iSolution.getModel().assignedVariables().size() > iNrAssigned
261 || (iSolution.getModel().assignedVariables().size() == iNrAssigned && iValue > iSolution.getModel()
262 .getTotalValue())) {
263 if (sLog.isDebugEnabled())
264 sLog.debug(" -- better than current");
265 if (iBackTrackNeighbour == null || iBackTrackNeighbour.compareTo(iSolution) >= 0) {
266 if (sLog.isDebugEnabled())
267 sLog.debug(" -- better than best");
268 iBackTrackNeighbour = new BackTrackNeighbour(variables2resolve);
269 }
270 }
271 return;
272 }
273 if (!canContinue(variables2resolve, idx, depth))
274 return;
275 V variable = variables2resolve.get(idx);
276 if (sLog.isDebugEnabled())
277 sLog.debug(" -- variable " + variable);
278 for (Iterator<T> e = values(variable); canContinueEvaluation() && e.hasNext();) {
279 T value = e.next();
280 if (value.equals(variable.getAssignment()))
281 continue;
282 if (sLog.isDebugEnabled())
283 sLog.debug(" -- value " + value);
284 Set<T> conflicts = iSolution.getModel().conflictValues(value);
285 if (sLog.isDebugEnabled())
286 sLog.debug(" -- conflicts " + conflicts);
287 if (!checkBound(variables2resolve, idx, depth, value, conflicts))
288 continue;
289 T current = variable.getAssignment();
290 List<V> newVariables2resolve = new ArrayList<V>(variables2resolve);
291 for (Iterator<T> i = conflicts.iterator(); i.hasNext();) {
292 T conflict = i.next();
293 conflict.variable().unassign(0);
294 if (!newVariables2resolve.contains(conflict.variable()))
295 newVariables2resolve.add(conflict.variable());
296 }
297 if (current != null)
298 current.variable().unassign(0);
299 value.variable().assign(0, value);
300 backtrack(newVariables2resolve, idx + 1, depth - 1);
301 if (current == null)
302 variable.unassign(0);
303 else
304 variable.assign(0, current);
305 for (Iterator<T> i = conflicts.iterator(); i.hasNext();) {
306 T conflict = i.next();
307 conflict.variable().assign(0, conflict);
308 }
309 }
310 }
311
312 /** Backtracking neighbour */
313 public class BackTrackNeighbour extends Neighbour<V, T> {
314 private double iTotalValue = 0;
315 private double iValue = 0;
316 private List<T> iDifferentAssignments = null;
317
318 /**
319 * Constructor
320 *
321 * @param resolvedVariables
322 * variables that has been changed
323 */
324 public BackTrackNeighbour(List<V> resolvedVariables) {
325 iTotalValue = iSolution.getModel().getTotalValue();
326 iValue = 0;
327 iDifferentAssignments = new ArrayList<T>();
328 for (V variable : resolvedVariables) {
329 T value = variable.getAssignment();
330 iDifferentAssignments.add(value);
331 iValue += value.toDouble();
332 }
333 }
334
335 /** Neighbour value (solution total value if the neighbour is applied). */
336 public double getTotalValue() {
337 return iTotalValue;
338 }
339
340 /**
341 * Sum of values of variables from the neighbour that change their
342 * values
343 */
344 @Override
345 public double value() {
346 return iValue;
347 }
348
349 /** Neighbour assignments */
350 public List<T> getAssignments() {
351 return iDifferentAssignments;
352 }
353
354 /**
355 * Assign the neighbour
356 */
357 @Override
358 public void assign(long iteration) {
359 if (sLog.isDebugEnabled())
360 sLog.debug("-- before assignment: nrAssigned=" + iSolution.getModel().assignedVariables().size()
361 + ", value=" + iSolution.getModel().getTotalValue());
362 if (sLog.isDebugEnabled())
363 sLog.debug(" " + this);
364 int idx = 0;
365 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext(); idx++) {
366 T p = e.next();
367 if (p.variable().getAssignment() != null) {
368 if (idx > 0 && iStat != null)
369 iStat.variableUnassigned(iteration, p.variable().getAssignment(), iDifferentAssignments.get(0));
370 p.variable().unassign(iteration);
371 }
372 }
373 for (T p : iDifferentAssignments) {
374 p.variable().assign(iteration, p);
375 }
376 if (sLog.isDebugEnabled())
377 sLog.debug("-- after assignment: nrAssigned=" + iSolution.getModel().assignedVariables().size()
378 + ", value=" + iSolution.getModel().getTotalValue());
379 }
380
381 /**
382 * Compare two neighbours
383 */
384 public int compareTo(Solution<V, T> solution) {
385 return Double.compare(iTotalValue, solution.getModel().getTotalValue());
386 }
387
388 @Override
389 public String toString() {
390 StringBuffer sb = new StringBuffer("BT{value=" + (iTotalValue - iSolution.getModel().getTotalValue())
391 + ": ");
392 for (Iterator<T> e = iDifferentAssignments.iterator(); e.hasNext();) {
393 T p = e.next();
394 sb.append("\n " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : ""));
395 }
396 sb.append("}");
397 return sb.toString();
398 }
399 }
400
401 /** Return maximal depth */
402 public int getDepth() {
403 return iDepth;
404 }
405
406 /** Set maximal depth */
407 public void setDepth(int depth) {
408 iDepth = depth;
409 }
410
411 /** Return time limit */
412 public int getTimeout() {
413 return iTimeout;
414 }
415
416 /** Set time limit */
417 public void setTimeout(int timeout) {
418 iTimeout = timeout;
419 }
420
421 /** Return maximal number of iterations */
422 public int getMaxIters() {
423 return iMaxIters;
424 }
425
426 /** Set maximal number of iterations */
427 public void setMaxIters(int maxIters) {
428 iMaxIters = maxIters;
429 }
430 }