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}