    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 * @author  Tomáš Müller
    038 * @version IFS 1.3 (Iterative Forward Search)<br>
    039 *          Copyright (C) 2014 Tomáš Müller<br>
    040 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    041 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    042 * <br>
    043 *          This library is free software; you can redistribute it and/or modify
    044 *          it under the terms of the GNU Lesser General Public License as
    045 *          published by the Free Software Foundation; either version 3 of the
    046 *          License, or (at your option) any later version. <br>
    047 * <br>
    048 *          This library is distributed in the hope that it will be useful, but
    049 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    050 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    051 *          Lesser General Public License for more details. <br>
    052 * <br>
    053 *          You should have received a copy of the GNU Lesser General Public
    054 *          License along with this library; if not see
    055 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    056 * @param <V> Variable
    057 * @param <T> Value
    058 */
    059public class SuggestionMove<V extends Variable<V, T>, T extends Value<V, T>> extends RandomSwapMove<V, T> {
    060    protected int iSuggestionDepth = 3;
    061    protected int iTimeLimit = 200;
    062
    063    public SuggestionMove(DataProperties config) throws Exception {
    064        super(config);
    065        iMaxAttempts = config.getPropertyInt("SuggestionMove.MaxAttempts", iMaxAttempts);
    066        iSuggestionDepth = config.getPropertyInt("SuggestionMove.Depth", iSuggestionDepth);
    067        iTimeLimit = config.getPropertyInt("SuggestionMove.TimeLimit", iTimeLimit);
    068    }
    069
    070    @Override
    071    public void init(Solver<V, T> solver) {
    072        super.init(solver);
    073    }
    074
    075    @Override
    076    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
    077        Lock lock = solution.getLock().writeLock();
    078        lock.lock();
    079        try {
    080            V variable = null;
    081            if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
    082                variable = ToolBox.random(solution.getModel().unassignedVariables(solution.getAssignment()));
    083            else
    084                variable = ToolBox.random(solution.getModel().variables());
    085            return backtrack(
    086                    solution, solution.getModel().getTotalValue(solution.getAssignment()),
    087                    solution.getModel().nrUnassignedVariables(solution.getAssignment()),
    088                    JProf.currentTimeMillis(), variable, new HashMap<V, T>(), new HashMap<V, T>(), iSuggestionDepth);
    089        } finally {
    090            lock.unlock();
    091        }
    092    }
    093
    094    private boolean containsCommited(Solution<V, T> solution, Collection<T> values) {
    095        if (solution.getModel() instanceof ConstantModel) {
    096            ConstantModel<V, T> model = (ConstantModel<V, T>)solution.getModel();
    097            if (model.hasConstantVariables())
    098                for (T value: values)
    099                    if (model.isConstant(value.variable())) return true;
    100        }
    101        return false;
    102    }
    103
    104    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) {
    105        Model<V, T> model = solution.getModel();
    106        Assignment<V, T> assignment = solution.getAssignment();
    107        int nrUnassigned = conflictsToResolve.size();
    108        if (initial == null && nrUnassigned == 0) {
    109            if (model.nrUnassignedVariables(assignment) > un) return null;
    110            double value = model.getTotalValue(assignment) - total;
    111            if (!iHC || value <= 0)
    112                return new SwapNeighbour(new ArrayList<T>(resolvedVariables.values()),
    113                        un > model.nrUnassignedVariables(assignment) ? -1 : value);
    114            else
    115                return null;
    116        }
    117        if (depth <= 0) return null;
    118
    119        V variable = initial;
    120        if (variable == null) {
    121            for (V l: conflictsToResolve.keySet()) {
    122                if (resolvedVariables.containsKey(l)) continue;
    123                variable = l; break;
    124            }
    125            if (variable == null) return null;
    126        } else {
    127            if (resolvedVariables.containsKey(variable)) return null;
    128        }
    129
    130        List<T> values = variable.values(solution.getAssignment());
    131        if (values.isEmpty()) return null;
    132
    133        int idx = ToolBox.random(values.size());
    134        int nrAttempts = 0;
    135        values: for (int i = 0; i < values.size(); i++) {
    136            if (nrAttempts >= iMaxAttempts || isTimeLimitReached(startTime)) break;
    137            T value = values.get((i + idx) % values.size());
    138
    139            T cur = assignment.getValue(variable);
    140            if (value.equals(cur)) continue;
    141
    142            Set<T> conflicts = model.conflictValues(assignment, value);
    143            if (nrUnassigned + conflicts.size() > depth) continue;
    144            if (conflicts.contains(value)) continue;
    145            if (containsCommited(solution, conflicts)) continue;
    146            for (T c: conflicts)
    147                if (resolvedVariables.containsKey(c.variable()))
    148                    continue values;
    149
    150            for (T c: conflicts) assignment.unassign(solution.getIteration(), c.variable());
    151            if (cur != null) assignment.unassign(solution.getIteration(), variable);
    152
    153            assignment.assign(solution.getIteration(), value);
    154            for (T c: conflicts)
    155                conflictsToResolve.put(c.variable(), c);
    156
    157            T resolvedConf = conflictsToResolve.remove(variable);
    158            resolvedVariables.put(variable, value);
    159
    160            SwapNeighbour n = backtrack(solution, total, un, startTime, null, resolvedVariables, conflictsToResolve, depth - 1);
    161            nrAttempts ++;
    162
    163            resolvedVariables.remove(variable);
    164            if (cur == null) assignment.unassign(solution.getIteration(), variable);
    165            else assignment.assign(solution.getIteration(), cur);
    166            for (T c: conflicts) {
    167                assignment.assign(solution.getIteration(), c);
    168                conflictsToResolve.remove(c.variable());
    169            }
    170            if (resolvedConf != null)
    171                conflictsToResolve.put(variable, resolvedConf);
    172
    173            if (n != null) return n;
    174        }
    175
    176        return null;
    177    }
    178
    179}