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