001package org.cpsolver.ifs.algorithms.neighbourhoods;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.HashMap;
006import java.util.List;
007import java.util.Map;
008import java.util.Set;
009import java.util.concurrent.locks.Lock;
010
011import org.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions;
012import org.cpsolver.ifs.algorithms.HillClimber;
013import org.cpsolver.ifs.assignment.Assignment;
014import org.cpsolver.ifs.constant.ConstantModel;
015import org.cpsolver.ifs.model.Model;
016import org.cpsolver.ifs.model.Neighbour;
017import org.cpsolver.ifs.model.Value;
018import org.cpsolver.ifs.model.Variable;
019import org.cpsolver.ifs.solution.Solution;
020import org.cpsolver.ifs.solver.Solver;
021import org.cpsolver.ifs.util.DataProperties;
022import org.cpsolver.ifs.util.JProf;
023import org.cpsolver.ifs.util.ToolBox;
024
025
026/**
027 * Suggestion move. A variable is selected randomly. A limited depth backtracking
028 * is used to find a possible change (much like the suggestions in UniTime when
029 * the interactive solver is used). Unlike in {@link NeighbourSelectionWithSuggestions},
030 * the very first found suggestion is returned. The depth is limited by 
031 * SuggestionMove.Depth parameter (defaults to 3). Also, instead of using a time limit, 
032 * the width of the search is limited by the number of values that are tried for each
033 * variable (parameter SuggestionMove.MaxAttempts, defaults to 10). When used in
034 * {@link HillClimber}, the first suggestion that does not worsen the solution is returned.
035 * <br>
036 * 
037 * @version IFS 1.3 (Iterative Forward Search)<br>
038 *          Copyright (C) 2014 Tomáš Müller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          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. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see
054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 * @param <V> Variable
056 * @param <T> Value
057 */
058public class SuggestionMove<V extends Variable<V, T>, T extends Value<V, T>> extends RandomSwapMove<V, T> {
059    protected int iSuggestionDepth = 3;
060    protected int iTimeLimit = 200;
061    
062    public SuggestionMove(DataProperties config) throws Exception {
063        super(config);
064        iMaxAttempts = config.getPropertyInt("SuggestionMove.MaxAttempts", iMaxAttempts);
065        iSuggestionDepth = config.getPropertyInt("SuggestionMove.Depth", iSuggestionDepth);
066        iTimeLimit = config.getPropertyInt("SuggestionMove.TimeLimit", iTimeLimit);
067    }
068
069    @Override
070    public void init(Solver<V, T> solver) {
071        super.init(solver);
072    }
073    
074    @Override
075    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
076        Lock lock = solution.getLock().writeLock();
077        lock.lock();
078        try {
079            V variable = ToolBox.random(solution.getModel().variables());
080            return backtrack(
081                    solution, solution.getModel().getTotalValue(solution.getAssignment()),
082                    solution.getModel().nrUnassignedVariables(solution.getAssignment()),
083                    JProf.currentTimeMillis(), variable, new HashMap<V, T>(), new HashMap<V, T>(), iSuggestionDepth);
084        } finally {
085            lock.unlock();
086        }
087    }
088    
089    private boolean containsCommited(Solution<V, T> solution, Collection<T> values) {
090        if (solution.getModel() instanceof ConstantModel) {
091            ConstantModel<V, T> model = (ConstantModel<V, T>)solution.getModel();
092            if (model.hasConstantVariables())
093                for (T value: values)
094                    if (model.isConstant(value.variable())) return true;
095        }
096        return false;
097    }
098
099    private SwapNeighbour backtrack(Solution<V, T> solution, double total, int un, long startTime, V initial, Map<V, T> resolvedVariables, HashMap<V, T> conflictsToResolve, int depth) {
100        Model<V, T> model = solution.getModel();
101        Assignment<V, T> assignment = solution.getAssignment();
102        int nrUnassigned = conflictsToResolve.size();
103        if (initial == null && nrUnassigned == 0) {
104            if (model.nrUnassignedVariables(assignment) > un) return null;
105            double value = model.getTotalValue(assignment) - total;
106            if (!iHC || value <= 0)
107                return new SwapNeighbour(new ArrayList<T>(resolvedVariables.values()), value);
108            else
109                return null;
110        }
111        if (depth <= 0) return null;
112
113        V variable = initial;
114        if (variable == null) {
115            for (V l: conflictsToResolve.keySet()) {
116                if (resolvedVariables.containsKey(l)) continue;
117                variable = l; break;
118            }
119            if (variable == null) return null;
120        } else {
121            if (resolvedVariables.containsKey(variable)) return null;
122        }
123        
124        List<T> values = variable.values(solution.getAssignment());
125        if (values.isEmpty()) return null;
126        
127        int idx = ToolBox.random(values.size());
128        int nrAttempts = 0;
129        values: for (int i = 0; i < values.size(); i++) {
130            if (nrAttempts >= iMaxAttempts || isTimeLimitReached(startTime)) break;
131            T value = values.get((i + idx) % values.size());
132
133            T cur = assignment.getValue(variable);
134            if (value.equals(cur)) continue;
135            
136            Set<T> conflicts = model.conflictValues(assignment, value);
137            if (nrUnassigned + conflicts.size() > depth) continue;
138            if (conflicts.contains(value)) continue;
139            if (containsCommited(solution, conflicts)) continue;
140            for (T c: conflicts)
141                if (resolvedVariables.containsKey(c.variable()))
142                    continue values;
143            
144            for (T c: conflicts) assignment.unassign(solution.getIteration(), c.variable());
145            if (cur != null) assignment.unassign(solution.getIteration(), variable);
146            
147            assignment.assign(solution.getIteration(), value);
148            for (T c: conflicts)
149                conflictsToResolve.put(c.variable(), c);
150
151            T resolvedConf = conflictsToResolve.remove(variable);
152            resolvedVariables.put(variable, value);
153            
154            SwapNeighbour n = backtrack(solution, total, un, startTime, null, resolvedVariables, conflictsToResolve, depth - 1);
155            nrAttempts ++;
156            
157            resolvedVariables.remove(variable);
158            if (cur == null) assignment.unassign(solution.getIteration(), variable);
159            else assignment.assign(solution.getIteration(), cur);
160            for (T c: conflicts) {
161                assignment.assign(solution.getIteration(), c);
162                conflictsToResolve.remove(c.variable());
163            }
164            if (resolvedConf != null)
165                conflictsToResolve.put(variable, resolvedConf);
166            
167            if (n != null) return n;
168        }
169        
170        return null;
171    }
172
173}