001 package net.sf.cpsolver.ifs.extension;
002
003
004 import java.util.*;
005
006 import net.sf.cpsolver.ifs.model.*;
007 import net.sf.cpsolver.ifs.solver.*;
008 import net.sf.cpsolver.ifs.util.*;
009
010 /**
011 * Another implementation of MAC propagation.
012 *
013 * @see MacPropagation
014 *
015 * @version
016 * IFS 1.1 (Iterative Forward Search)<br>
017 * Copyright (C) 2006 Tomáš Müller<br>
018 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
019 * Lazenska 391, 76314 Zlin, Czech Republic<br>
020 * <br>
021 * This library is free software; you can redistribute it and/or
022 * modify it under the terms of the GNU Lesser General Public
023 * License as published by the Free Software Foundation; either
024 * version 2.1 of the License, or (at your option) any later version.
025 * <br><br>
026 * This library is distributed in the hope that it will be useful,
027 * but WITHOUT ANY WARRANTY; without even the implied warranty of
028 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
029 * Lesser General Public License for more details.
030 * <br><br>
031 * You should have received a copy of the GNU Lesser General Public
032 * License along with this library; if not, write to the Free Software
033 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
034 */
035
036 public class MacRevised extends Extension {
037 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacRevised.class);
038 private boolean iDbt = false;
039 private Progress iProgress;
040
041 /** List of constraints on which arc-consistency is to be maintained */
042 protected Vector iConstraints = null;
043 /** Current iteration */
044 protected long iIteration = 0;
045
046 /** Constructor */
047 public MacRevised(Solver solver, DataProperties properties) {
048 super(solver, properties);
049 iDbt = properties.getPropertyBoolean("MacRevised.Dbt", false);
050 }
051
052 /** Adds a constraint on which arc-consistency is to be maintained */
053 public void addConstraint(Constraint constraint) {
054 if (iConstraints == null) iConstraints = new FastVector();
055 iConstraints.addElement(constraint);
056 }
057
058 /** Returns true, if arc-consistency is to be maintained on the given constraint */
059 public boolean contains(Constraint constraint) {
060 if (iConstraints == null) return true;
061 return iConstraints.contains(constraint);
062 }
063
064 /** Before a value is unassigned: until the value is inconsistent with the current solution,
065 * an assignment from its explanation is picked and unassigned.
066 */
067 public void beforeAssigned(long iteration, Value value) {
068 sLogger.debug("Before assign "+value.variable().getName() + " = " + value.getName());
069 iIteration = iteration;
070 if (value == null) return;
071 while (!isGood(value) && !noGood(value).isEmpty()) {
072 if (iDbt) sLogger.warn("Going to assign a no-good value "+value+" (noGood:" + noGood(value) + ").");
073 Value noGoodValue = (Value)noGood(value).iterator().next();
074 noGoodValue.variable().unassign(iteration);
075 }
076 if (!isGood(value)) {
077 sLogger.warn("Going to assign a bad value "+value+" with empty no-good.");
078 }
079 }
080
081 /** After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value),
082 * propagation over the assigned variable takes place.
083 */
084 public void afterAssigned(long iteration, Value value) {
085 sLogger.debug("After assign "+value.variable().getName() + " = " + value.getName());
086 iIteration = iteration;
087 if (!isGood(value)) {
088 sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(value) + ")");
089 setGood(value);
090 }
091
092 HashSet noGood = new HashSet(1); noGood.add(value);
093 Vector queue = new Vector();
094 for (Enumeration i = value.variable().values().elements(); i.hasMoreElements(); ) {
095 Value anotherValue = (Value)i.nextElement();
096 if (anotherValue.equals(value) || !isGood(anotherValue)) continue;
097 setNoGood(anotherValue, noGood);
098 queue.add(anotherValue);
099 }
100 propagate(queue);
101 }
102
103 /** After a value is unassigned: explanations of all values of unassigned variable are recomputed ({@link Value#conflicts()}), propagation
104 * undo over the unassigned variable takes place.
105 */
106 public void afterUnassigned(long iteration, Value value) {
107 sLogger.debug("After unassign "+value.variable().getName() + " = " + value.getName());
108 iIteration = iteration;
109 if (!isGood(value))
110 sLogger.error(value.variable().getName() + " = " + value.getName() + " -- not good value unassigned (noGood:" + noGood(value) + ")");
111
112 Vector back = new Vector(supportValues(value.variable()));
113 for (Enumeration e=back.elements();e.hasMoreElements();) {
114 Value aValue = (Value)e.nextElement();
115 if (aValue.variable().getAssignment()!=null) {
116 HashSet noGood = new HashSet(1); noGood.add(aValue.variable().getAssignment());
117 setNoGood(aValue, noGood);
118 } else
119 setGood(aValue);
120 }
121
122 Vector queue = new Vector();
123 for (Enumeration e=back.elements();e.hasMoreElements();) {
124 Value aValue = (Value)e.nextElement();
125 if (!isGood(aValue) || revise(aValue))
126 queue.add(aValue);
127 }
128
129 propagate(queue);
130 }
131
132 public void propagate(Vector queue) {
133 int idx = 0;
134 while (queue.size()>idx) {
135 Value value = (Value)queue.elementAt(idx++);
136 sLogger.debug(" -- propagate "+value.variable().getName()+" = " + value.getName()+" (noGood:" + noGood(value) + ")");
137 if (goodValues(value.variable()).isEmpty()) {
138 sLogger.info("Empty domain detected for variable "+value.variable().getName());
139 continue;
140 }
141 for (Enumeration e=value.variable().hardConstraints().elements(); e.hasMoreElements(); ) {
142 Constraint constraint = (Constraint)e.nextElement();
143 if (!contains(constraint)) continue;
144 propagate(constraint, value, queue);
145 }
146 }
147 }
148
149 public void propagate(Constraint constraint, Value noGoodValue, Vector queue) {
150 for (Enumeration e1 = constraint.variables().elements();e1.hasMoreElements();) {
151 Variable aVariable = (Variable)e1.nextElement();
152 if (aVariable.equals(noGoodValue.variable())) continue;
153 for (Enumeration e2=aVariable.values().elements(); e2.hasMoreElements();) {
154 Value aValue = (Value)e2.nextElement();
155 if (isGood(aValue) && constraint.isConsistent(noGoodValue,aValue) && !hasSupport(constraint, aValue, noGoodValue.variable())) {
156 setNoGood(aValue, explanation(constraint, aValue, noGoodValue.variable()));
157 queue.addElement(aValue);
158 }
159 }
160 }
161 }
162
163 public boolean revise(Value value) {
164 sLogger.debug(" -- revise "+value.variable().getName()+" = " + value.getName());
165 for (Enumeration e=value.variable().hardConstraints().elements(); e.hasMoreElements(); ) {
166 Constraint constraint = (Constraint)e.nextElement();
167 if (!contains(constraint)) continue;
168 if (revise(constraint, value)) return true;
169 }
170 return false;
171 }
172
173 public boolean revise(Constraint constraint, Value value) {
174 for (Enumeration e1 = constraint.variables().elements();e1.hasMoreElements();) {
175 Variable aVariable = (Variable)e1.nextElement();
176 if (aVariable.equals(value.variable())) continue;
177 if (!hasSupport(constraint, value, aVariable)) {
178 setNoGood(value, explanation(constraint, value, aVariable));
179 return true;
180 }
181 }
182 return false;
183 }
184
185 public HashSet explanation(Constraint constraint, Value value, Variable variable) {
186 HashSet expl = new HashSet();
187 for (Enumeration e=variable.values().elements();e.hasMoreElements();) {
188 Value aValue = (Value)e.nextElement();
189 if (constraint.isConsistent(aValue,value)) {
190 expl.addAll(noGood(aValue));
191 }
192 }
193 return expl;
194 }
195
196 public HashSet supports(Constraint constraint, Value value, Variable variable) {
197 HashSet sup = new HashSet();
198 for (Enumeration e=variable.values().elements();e.hasMoreElements();) {
199 Value aValue = (Value)e.nextElement();
200 if (!isGood(aValue)) continue;
201 if (!constraint.isConsistent(aValue,value)) continue;
202 sup.add(aValue);
203 }
204 return sup;
205 }
206
207 public boolean hasSupport(Constraint constraint, Value value, Variable variable) {
208 for (Enumeration e=variable.values().elements();e.hasMoreElements();) {
209 Value aValue = (Value)e.nextElement();
210 if (isGood(aValue) && constraint.isConsistent(aValue,value)) {
211 //sLogger.debug(" -- "+variable.getName()+" = "+aValue.getName()+" supports " + value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")");
212 return true;
213 }
214 }
215 //sLogger.debug(" -- value "+value.variable().getName()+" = " + value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")");
216 /*
217 for (Enumeration e=variable.values().elements();e.hasMoreElements();) {
218 Value aValue = (Value)e.nextElement();
219 if (constraint.isConsistent(aValue,value)) {
220 //sLogger.debug(" -- support "+aValue.getName()+" is not good: "+expl2str(noGood(aValue)));
221 }
222 }
223 */
224 return false;
225 }
226
227
228 /** Initialization. Enforce arc-consistency over the current (initial) solution. AC3 algorithm is used. */
229 public boolean init(Solver solver) {
230 boolean isOk = true;
231 iProgress = Progress.getInstance(getModel());
232 for (Enumeration e=getModel().constraints().elements();e.hasMoreElements();) {
233 Constraint constraint = (Constraint)e.nextElement();
234 sLogger.debug("Constraint "+constraint.getName());
235 }
236 iProgress.save();
237 iProgress.setPhase("Initializing propagation:", getModel().variables().size());
238 for (Enumeration i1 = getModel().variables().elements(); i1.hasMoreElements(); ) {
239 Variable aVariable = (Variable)i1.nextElement();
240 supportValues(aVariable).clear();
241 goodValues(aVariable).clear();
242 }
243 Vector queue = new Vector();
244 for (Enumeration i1 = getModel().variables().elements(); i1.hasMoreElements(); ) {
245 Variable aVariable = (Variable)i1.nextElement();
246 for (Enumeration i2 = aVariable.values().elements(); i2.hasMoreElements(); ) {
247 Value aValue = (Value)i2.nextElement();
248 initNoGood(aValue, null);
249 goodValues(aVariable).add(aValue);
250 if (revise(aValue)) {
251 queue.add(aValue);
252 } else if (aVariable.getAssignment()!=null && !aValue.equals(aVariable.getAssignment())) {
253 HashSet noGood = new HashSet(); noGood.add(aVariable.getAssignment());
254 setNoGood(aValue, noGood);
255 queue.add(noGood);
256 }
257 }
258 iProgress.incProgress();
259 }
260 propagate(queue);
261 iProgress.restore();
262 return isOk;
263 }
264
265 /** support values of a variable */
266 private Set supportValues(Variable variable) {
267 Set[] ret = (Set[])variable.getExtra();
268 if (ret == null) {
269 ret = new HashSet[] { new HashSet(1000), new HashSet()};
270 variable.setExtra(ret);
271 }
272 return ret[0];
273 }
274
275 /** good values of a variable (values not removed from variables domain)*/
276 public Set goodValues(Variable variable) {
277 Set[] ret = (Set[])variable.getExtra();
278 if (ret == null) {
279 ret = new HashSet[] { new HashSet(1000), new HashSet()};
280 variable.setExtra(ret);
281 }
282 return ret[1];
283 }
284
285 /** notification that a nogood value becomes good or vice versa */
286 private void goodnessChanged(Value value) {
287 if (isGood(value)) {
288 goodValues(value.variable()).add(value);
289 }
290 else {
291 goodValues(value.variable()).remove(value);
292 }
293 }
294 /** removes support of a variable */
295 private void removeSupport(Variable variable, Value value) {
296 supportValues(variable).remove(value);
297 }
298 /** adds support of a variable */
299 private void addSupport(Variable variable, Value value) {
300 supportValues(variable).add(value);
301 }
302
303 /** variables explanation */
304 public Set noGood(Value value) {
305 return (Set)value.getExtra();
306 }
307 /** is variable good */
308 public boolean isGood(Value value) {
309 return (value.getExtra() == null);
310 }
311 /** sets value to be good */
312 protected void setGood(Value value) {
313 sLogger.debug(" -- set good "+value.variable().getName()+" = " + value.getName());
314 Set noGood = noGood(value);
315 if (noGood != null)
316 for (Iterator i = noGood.iterator(); i.hasNext();)
317 removeSupport(((Value)i.next()).variable(), value);
318 value.setExtra(null);
319 goodnessChanged(value);
320 }
321 /** sets values explanation (initialization) */
322 private void initNoGood(Value value, Set reason) {
323 value.setExtra(reason);
324 }
325
326 private static String expl2str(Set expl) {
327 StringBuffer sb = new StringBuffer("[");
328 for (Iterator i=expl.iterator();i.hasNext();) {
329 Value value = (Value)i.next();
330 sb.append(value.variable().getName()+"=" + value.getName());
331 if (i.hasNext()) sb.append(", ");
332 }
333 sb.append("]");
334 return sb.toString();
335 }
336
337 private static void checkExpl(Set expl) {
338 sLogger.debug(" -- checking explanation: "+expl2str(expl));
339 for (Iterator i=expl.iterator();i.hasNext();) {
340 Value value = (Value)i.next();
341 if (!value.equals(value.variable().getAssignment())) {
342 if (value.variable().getAssignment()==null)
343 sLogger.warn(" -- variable "+value.variable().getName()+" unassigned");
344 else
345 sLogger.warn(" -- variable "+value.variable().getName()+" assigned to a different value "+value.variable().getAssignment().getName());
346 }
347 }
348 }
349
350 private void printAssignments() {
351 sLogger.debug(" -- printing assignments: ");
352 for (Enumeration e=getModel().variables().elements();e.hasMoreElements();) {
353 Variable variable = (Variable)e.nextElement();
354 if (variable.getAssignment()!=null)
355 sLogger.debug(" -- "+variable.getName()+" = "+variable.getAssignment().getName());
356 }
357 }
358
359 /** sets value's explanation*/
360 public void setNoGood(Value value, Set reason) {
361 sLogger.debug(" -- set nogood "+value.variable().getName()+" = " + value.getName()+"(expl:"+expl2str(reason)+")");
362 if (value.equals(value.variable().getAssignment())) {
363 try {
364 throw new Exception("An assigned value "+value.variable().getName() + " = " + value.getName() + " become no good (noGood:" + reason + ")!!");
365 } catch (Exception e) {
366 sLogger.warn(e.getMessage(),e);
367 }
368 checkExpl(reason);
369 printAssignments();
370 }
371 Set noGood = noGood(value);
372 if (noGood != null)
373 for (Iterator i = noGood.iterator(); i.hasNext();)
374 removeSupport(((Value)i.next()).variable(), value);
375 value.setExtra(reason);
376 for (Iterator i = reason.iterator(); i.hasNext();) {
377 Value aValue = (Value)i.next();
378 addSupport(aValue.variable(), value);
379 }
380 goodnessChanged(value);
381 }
382 }