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