    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}