001package net.sf.cpsolver.ifs.heuristics;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.Iterator;
006import java.util.List;
007import java.util.Set;
008
009import net.sf.cpsolver.ifs.constant.ConstantVariable;
010import net.sf.cpsolver.ifs.extension.ConflictStatistics;
011import net.sf.cpsolver.ifs.extension.Extension;
012import net.sf.cpsolver.ifs.model.Neighbour;
013import net.sf.cpsolver.ifs.model.Value;
014import net.sf.cpsolver.ifs.model.Variable;
015import net.sf.cpsolver.ifs.solution.Solution;
016import net.sf.cpsolver.ifs.solver.Solver;
017import net.sf.cpsolver.ifs.util.DataProperties;
018import net.sf.cpsolver.ifs.util.JProf;
019
020import 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 Tomáš Müller<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
069public 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}