001package net.sf.cpsolver.ifs.dbt; 002 003import java.util.HashSet; 004import java.util.Set; 005 006import net.sf.cpsolver.ifs.extension.MacPropagation; 007import net.sf.cpsolver.ifs.model.Neighbour; 008import net.sf.cpsolver.ifs.model.Value; 009import net.sf.cpsolver.ifs.model.Variable; 010import net.sf.cpsolver.ifs.solution.Solution; 011import net.sf.cpsolver.ifs.solver.Solver; 012import net.sf.cpsolver.ifs.solver.SolverListener; 013import net.sf.cpsolver.ifs.util.DataProperties; 014 015/** 016 * Maintenance of arc consistency in dynamic backtracking. <br> 017 * <br> 018 * The difference between {@link MacPropagation} and this DBT propagation is 019 * that all not-assigned values of an assigned variable are marked as nogood. 020 * Also, when a dead end is reached, unassignment or failure takes place. <br> 021 * <br> 022 * This IFS solver extension is to be used only in case of dynamic backtracking 023 * and it has no parameters. 024 * 025 * 026 * @version IFS 1.2 (Iterative Forward Search)<br> 027 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 028 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 029 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 030 * <br> 031 * This library is free software; you can redistribute it and/or modify 032 * it under the terms of the GNU Lesser General Public License as 033 * published by the Free Software Foundation; either version 3 of the 034 * License, or (at your option) any later version. <br> 035 * <br> 036 * This library is distributed in the hope that it will be useful, but 037 * WITHOUT ANY WARRANTY; without even the implied warranty of 038 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 039 * Lesser General Public License for more details. <br> 040 * <br> 041 * You should have received a copy of the GNU Lesser General Public 042 * License along with this library; if not see <http://www.gnu.org/licenses/>. 043 * 044 */ 045public class DbtPropagation<V extends Variable<V, T>, T extends Value<V, T>> extends MacPropagation<V, T> implements 046 SolverListener<V, T> { 047 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(DbtPropagation.class); 048 049 /** 050 * Constructor. No parameter is taken from properties. 051 */ 052 public DbtPropagation(Solver<V, T> solver, DataProperties properties) { 053 super(solver, properties); 054 solver.addSolverListener(this); 055 } 056 057 /** 058 * Propagation takes place every time a value is assigned to a variable. <br> 059 * <br> 060 * <li>Prints a warning if the value is nogood (should not never happen), 061 * <li>sets all other values of the variable to nogood (explanation is the 062 * assigned value itself), <li>runs propagation. 063 * 064 * @see MacPropagation#propagate(Variable) 065 */ 066 @Override 067 public void afterAssigned(long iteration, T value) { 068 iIteration = iteration; 069 if (!isGood(value)) { 070 sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" 071 + noGood(value) + ")"); 072 setGood(value); 073 } 074 075 Set<T> noGood = new HashSet<T>(1); 076 077 noGood.add(value); 078 for (T anotherValue : value.variable().values()) { 079 if (anotherValue.equals(value) || !isGood(anotherValue)) 080 continue; 081 setNoGood(anotherValue, noGood); 082 } 083 propagate(value.variable()); 084 } 085 086 /** 087 * Undo propagation when a value is unassigned. <br> 088 * <br> 089 * <li>Prints an error if the value is nogood (should not never happen), <li> 090 * runs propagation undo. 091 * 092 * @see MacPropagation#undoPropagate(Variable) 093 */ 094 @Override 095 public void afterUnassigned(long iteration, T value) { 096 iIteration = iteration; 097 if (!isGood(value)) { 098 sLogger.error(value.variable().getName() + " = " + value.getName() 099 + " -- not good value unassigned (noGood:" + noGood(value) + ")"); 100 } 101 undoPropagate(value.variable()); 102 } 103 104 /** 105 * If no variable is selected (all variables are assinged), unassign the 106 * last assigned variable. <br> 107 * <br> 108 * Do not allow to select an assigned variable. <br> 109 * <br> 110 * If no variable is selected (because all variables are assigned, see 111 * {@link DbtVariableSelection}): 112 * <ul> 113 * <li>find the last assigned variable and 114 * <li>unassign it (explanation is a union of assignments of all other 115 * variables). 116 * </ul> 117 * 118 * @see DbtVariableSelection#selectVariable(Solution) 119 */ 120 @Override 121 public boolean variableSelected(long iteration, V variable) { 122 if (variable == null) { 123 sLogger.debug("No variable selected -> backtrack."); 124 V lastVariable = null; 125 126 for (V var : getModel().assignedVariables()) { 127 if (lastVariable == null 128 || lastVariable.getAssignment().lastAssignmentIteration() < var.getAssignment() 129 .lastAssignmentIteration()) { 130 lastVariable = var; 131 } 132 } 133 if (lastVariable == null) { 134 sLogger.error("No assignment -> fail"); 135 getSolver().stopSolver(); 136 return false; 137 } 138 sLogger.debug("Unassign:" + lastVariable.getName()); 139 Set<T> noGoods = new HashSet<T>(); 140 141 for (V var : getModel().assignedVariables()) { 142 if (!var.equals(lastVariable)) { 143 noGoods.add(var.getAssignment()); 144 } 145 } 146 T value = lastVariable.getAssignment(); 147 148 lastVariable.unassign(iteration); 149 setNoGood(value, noGoods); 150 return false; 151 } 152 if (variable.getAssignment() != null) { 153 sLogger.error("Assigned value selected -- not supported by DBT."); 154 return false; 155 } 156 return true; 157 } 158 159 /** 160 * If no value is selected (because of a dead end), make some unassignments. <br> 161 * <br> 162 * If no value is selected (e.g., because the selected variable has all 163 * values marked as nogood, see {@link DbtValueSelection}), 164 * <ul> 165 * <li>compute a union of explanations of all values, 166 * <ul> 167 * <li>if it is empty fail (inconsistency is found), 168 * </ul> 169 * <li>otherwise pick the last assigned variable from the computed union of 170 * explanation and unassign it 171 * <ul> 172 * (explanation for that is the computed union of explanations without the 173 * last assignment). 174 * </ul> 175 * </ul> 176 * 177 * @see DbtVariableSelection#selectVariable(Solution) 178 */ 179 @Override 180 public boolean valueSelected(long iteration, V variable, T value) { 181 if (variable != null && value == null) { 182 Set<T> noGoods = new HashSet<T>(); 183 184 for (T val : variable.values()) { 185 if (noGood(val) != null) { 186 noGoods.addAll(noGood(val)); 187 } 188 } 189 if (noGoods.isEmpty()) { 190 sLogger.debug("Fail"); 191 getSolver().stopSolver(); 192 return false; 193 } 194 V lastVariable = null; 195 196 for (T val : noGoods) { 197 V var = val.variable(); 198 199 if (lastVariable == null 200 || lastVariable.getAssignment().lastAssignmentIteration() < var.getAssignment() 201 .lastAssignmentIteration()) { 202 lastVariable = var; 203 } 204 } 205 T assignment = lastVariable.getAssignment(); 206 207 noGoods.remove(assignment); 208 lastVariable.unassign(iteration); 209 setNoGood(assignment, noGoods); 210 } 211 return true; 212 } 213 214 @Override 215 public boolean neighbourSelected(long iteration, Neighbour<V, T> neighbour) { 216 return true; 217 } 218}