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    }