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