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}