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