    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}