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 = null;
080            if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
081                variable = ToolBox.random(solution.getModel().unassignedVariables(solution.getAssignment()));
082            else
083                variable = ToolBox.random(solution.getModel().variables());
084            return backtrack(
085                    solution, solution.getModel().getTotalValue(solution.getAssignment()),
086                    solution.getModel().nrUnassignedVariables(solution.getAssignment()),
087                    JProf.currentTimeMillis(), variable, new HashMap<V, T>(), new HashMap<V, T>(), iSuggestionDepth);
088        } finally {
089            lock.unlock();
090        }
091    }
092    
093    private boolean containsCommited(Solution<V, T> solution, Collection<T> values) {
094        if (solution.getModel() instanceof ConstantModel) {
095            ConstantModel<V, T> model = (ConstantModel<V, T>)solution.getModel();
096            if (model.hasConstantVariables())
097                for (T value: values)
098                    if (model.isConstant(value.variable())) return true;
099        }
100        return false;
101    }
102
103    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) {
104        Model<V, T> model = solution.getModel();
105        Assignment<V, T> assignment = solution.getAssignment();
106        int nrUnassigned = conflictsToResolve.size();
107        if (initial == null && nrUnassigned == 0) {
108            if (model.nrUnassignedVariables(assignment) > un) return null;
109            double value = model.getTotalValue(assignment) - total;
110            if (!iHC || value <= 0)
111                return new SwapNeighbour(new ArrayList<T>(resolvedVariables.values()),
112                        un > model.nrUnassignedVariables(assignment) ? -1 : value);
113            else
114                return null;
115        }
116        if (depth <= 0) return null;
117
118        V variable = initial;
119        if (variable == null) {
120            for (V l: conflictsToResolve.keySet()) {
121                if (resolvedVariables.containsKey(l)) continue;
122                variable = l; break;
123            }
124            if (variable == null) return null;
125        } else {
126            if (resolvedVariables.containsKey(variable)) return null;
127        }
128        
129        List<T> values = variable.values(solution.getAssignment());
130        if (values.isEmpty()) return null;
131        
132        int idx = ToolBox.random(values.size());
133        int nrAttempts = 0;
134        values: for (int i = 0; i < values.size(); i++) {
135            if (nrAttempts >= iMaxAttempts || isTimeLimitReached(startTime)) break;
136            T value = values.get((i + idx) % values.size());
137
138            T cur = assignment.getValue(variable);
139            if (value.equals(cur)) continue;
140            
141            Set<T> conflicts = model.conflictValues(assignment, value);
142            if (nrUnassigned + conflicts.size() > depth) continue;
143            if (conflicts.contains(value)) continue;
144            if (containsCommited(solution, conflicts)) continue;
145            for (T c: conflicts)
146                if (resolvedVariables.containsKey(c.variable()))
147                    continue values;
148            
149            for (T c: conflicts) assignment.unassign(solution.getIteration(), c.variable());
150            if (cur != null) assignment.unassign(solution.getIteration(), variable);
151            
152            assignment.assign(solution.getIteration(), value);
153            for (T c: conflicts)
154                conflictsToResolve.put(c.variable(), c);
155
156            T resolvedConf = conflictsToResolve.remove(variable);
157            resolvedVariables.put(variable, value);
158            
159            SwapNeighbour n = backtrack(solution, total, un, startTime, null, resolvedVariables, conflictsToResolve, depth - 1);
160            nrAttempts ++;
161            
162            resolvedVariables.remove(variable);
163            if (cur == null) assignment.unassign(solution.getIteration(), variable);
164            else assignment.assign(solution.getIteration(), cur);
165            for (T c: conflicts) {
166                assignment.assign(solution.getIteration(), c);
167                conflictsToResolve.remove(c.variable());
168            }
169            if (resolvedConf != null)
170                conflictsToResolve.put(variable, resolvedConf);
171            
172            if (n != null) return n;
173        }
174        
175        return null;
176    }
177
178}