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}