Source code

001package org.cpsolver.ifs.extension;
002
003import java.util.ArrayList;
004import java.util.HashMap;
005import java.util.HashSet;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010
011import org.cpsolver.ifs.assignment.Assignment;
012import org.cpsolver.ifs.assignment.context.AssignmentContext;
013import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
014import org.cpsolver.ifs.model.Constraint;
015import org.cpsolver.ifs.model.Value;
016import org.cpsolver.ifs.model.Variable;
017import org.cpsolver.ifs.solver.Solver;
018import org.cpsolver.ifs.util.DataProperties;
019import org.cpsolver.ifs.util.Progress;
020
021
022/**
023 * Another implementation of MAC propagation.
024 * 
025 * @see MacPropagation
026 * 
027 * @author  Tomáš Müller
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
045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
046 * @param <V> Variable
047 * @param <T> Value
048 */
049
050public class MacRevised<V extends Variable<V, T>, T extends Value<V, T>> extends ExtensionWithContext<V, T, MacRevised<V, T>.NoGood> {
051    private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(MacRevised.class);
052    private boolean iDbt = false;
053    private Progress iProgress;
054
055    /** List of constraints on which arc-consistency is to be maintained */
056    protected List<Constraint<V, T>> iConstraints = null;
057    /** Current iteration */
058    protected long iIteration = 0;
059
060    /** Constructor 
061     * @param solver current solver
062     * @param properties solver configuration
063     **/
064    public MacRevised(Solver<V, T> solver, DataProperties properties) {
065        super(solver, properties);
066        iDbt = properties.getPropertyBoolean("MacRevised.Dbt", false);
067    }
068
069    /** Adds a constraint on which arc-consistency is to be maintained 
070     * @param constraint a hard constraint to be added
071     **/
072    public void addConstraint(Constraint<V, T> constraint) {
073        if (iConstraints == null)
074            iConstraints = new ArrayList<Constraint<V, T>>();
075        iConstraints.add(constraint);
076    }
077
078    /**
079     * Returns true, if arc-consistency is to be maintained on the given
080     * constraint
081     * @param constraint a constraint
082     * @return true if the constraint is in the set
083     */
084    public boolean contains(Constraint<V, T> constraint) {
085        if (iConstraints == null)
086            return true;
087        return iConstraints.contains(constraint);
088    }
089
090    /**
091     * Before a value is unassigned: until the value is inconsistent with the
092     * current solution, an assignment from its explanation is picked and
093     * unassigned.
094     */
095    @Override
096    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
097        if (value == null)
098            return;
099        sLogger.debug("Before assign " + value.variable().getName() + " = " + value.getName());
100        iIteration = iteration;
101        NoGood context = getContext(assignment);
102        while (!context.isGood(value) && !context.noGood(value).isEmpty()) {
103            if (iDbt)
104                sLogger.warn("Going to assign a no-good value " + value + " (noGood:" + context.noGood(value) + ").");
105            T noGoodValue = context.noGood(value).iterator().next();
106            assignment.unassign(iteration, noGoodValue.variable());
107        }
108        if (!context.isGood(value)) {
109            sLogger.warn("Going to assign a bad value " + value + " with empty no-good.");
110        }
111    }
112
113    /**
114     * After a value is assigned: explanations of other values of the value's
115     * variable are reset (to contain only the assigned value), propagation over
116     * the assigned variable takes place.
117     */
118    @Override
119    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
120        sLogger.debug("After assign " + value.variable().getName() + " = " + value.getName());
121        iIteration = iteration;
122        NoGood context = getContext(assignment);
123        if (!context.isGood(value)) {
124            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + context.noGood(value) + ")");
125            context.setGood(value);
126        }
127
128        Set<T> noGood = new HashSet<T>(1);
129        noGood.add(value);
130        List<T> queue = new ArrayList<T>();
131        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
132            T anotherValue = i.next();
133            if (anotherValue.equals(value) || !context.isGood(anotherValue))
134                continue;
135            context.setNoGood(anotherValue, noGood);
136            queue.add(anotherValue);
137        }
138        context.propagate(assignment, queue);
139    }
140
141    /**
142     * After a value is unassigned: explanations of all values of unassigned
143     * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo
144     * over the unassigned variable takes place.
145     */
146    @Override
147    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
148        sLogger.debug("After unassign " + value.variable().getName() + " = " + value.getName());
149        iIteration = iteration;
150        NoGood context = getContext(assignment);
151        if (!context.isGood(value))
152            sLogger.error(value.variable().getName() + " = " + value.getName() + " -- not good value unassigned (noGood:" + context.noGood(value) + ")");
153
154        List<T> back = new ArrayList<T>(context.supportValues(value.variable()));
155        for (T aValue : back) {
156            T current = assignment.getValue(aValue.variable());
157            if (current != null) {
158                Set<T> noGood = new HashSet<T>(1);
159                noGood.add(current);
160                context.setNoGood(aValue, noGood);
161            } else
162                context.setGood(aValue);
163        }
164
165        List<T> queue = new ArrayList<T>();
166        for (T aValue : back) {
167            if (!context.isGood(aValue) || context.revise(assignment, aValue))
168                queue.add(aValue);
169        }
170
171        context.propagate(assignment, queue);
172    }
173
174    /**
175     * Initialization. Enforce arc-consistency over the current (initial)
176     * solution. AC3 algorithm is used.
177     */
178    @Override
179    public boolean init(Solver<V, T> solver) {
180        return true;
181    }
182
183    private String expl2str(Set<T> expl) {
184        StringBuffer sb = new StringBuffer("[");
185        for (Iterator<T> i = expl.iterator(); i.hasNext();) {
186            T value = i.next();
187            sb.append(value.variable().getName() + "=" + value.getName());
188            if (i.hasNext())
189                sb.append(", ");
190        }
191        sb.append("]");
192        return sb.toString();
193    }
194
195    private void checkExpl(Assignment<V, T> assignment, Set<T> expl) {
196        sLogger.debug("    -- checking explanation: " + expl2str(expl));
197        for (Iterator<T> i = expl.iterator(); i.hasNext();) {
198            T value = i.next();
199            T current = assignment.getValue(value.variable());
200            if (!value.equals(current)) {
201                if (current == null)
202                    sLogger.warn("      -- variable " + value.variable().getName() + " unassigned");
203                else
204                    sLogger.warn("      -- variable " + value.variable().getName() + " assigned to a different value " + current.getName());
205            }
206        }
207    }
208
209    private void printAssignments(Assignment<V, T> assignment) {
210        sLogger.debug("    -- printing assignments: ");
211        for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
212            V variable = i.next();
213            T value = assignment.getValue(variable);
214            if (value != null)
215                sLogger.debug("      -- " + variable.getName() + " = " + value.getName());
216        }
217    }
218
219    @Override
220    public NoGood createAssignmentContext(Assignment<V, T> assignment) {
221        return new NoGood(assignment);
222    }
223
224    /**
225     * Assignment context
226     */
227    public class NoGood implements AssignmentContext {
228        private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>();
229        private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>();
230        
231        public NoGood(Assignment<V, T> assignment) {
232            iProgress = Progress.getInstance(getModel());
233            iProgress.save();
234            iProgress.setPhase("Initializing propagation:", getModel().variables().size());
235            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
236                V aVariable = i.next();
237                supportValues(aVariable).clear();
238                goodValues(aVariable).clear();
239            }
240            List<T> queue = new ArrayList<T>();
241            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
242                V aVariable = i.next();
243                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
244                    T aValue = j.next();
245                    initNoGood(aValue, null);
246                    goodValues(aVariable).add(aValue);
247                    T current = assignment.getValue(aVariable);
248                    if (revise(assignment, aValue)) {
249                        queue.add(aValue);
250                    } else if (current != null && !aValue.equals(current)) {
251                        Set<T> noGood = new HashSet<T>();
252                        noGood.add(current);
253                        setNoGood(aValue, noGood);
254                        queue.add(aValue);
255                    }
256                }
257                iProgress.incProgress();
258            }
259            propagate(assignment, queue);
260            iProgress.restore();
261        }
262        
263        public Set<T>[] getNoGood(V variable) {
264            return iNoGood.get(variable);
265        }
266        
267        public void setNoGood(V variable, Set<T>[] noGood) {
268            if (noGood == null)
269                iNoGood.remove(variable);
270            else
271                iNoGood.put(variable, noGood);
272        }
273        
274        public Set<T> getNoGood(T value) {
275            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
276            if (ng == null) return null;
277            return ng.get(value);
278        }
279        
280        public void setNoGood(T value, Set<T> noGood) {
281            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
282            if (ng == null) {
283                ng = new HashMap<T, Set<T>>();
284                iNoGoodVal.put(value.variable(), ng);
285            }
286            if (noGood == null)
287                ng.remove(value);
288            else
289                ng.put(value, noGood);
290        }
291        
292        /** support values of a variable */
293        @SuppressWarnings("unchecked")
294        private Set<T> supportValues(V variable) {
295            Set<T>[] ret = getNoGood(variable);
296            if (ret == null) {
297                ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
298                setNoGood(variable, ret);
299            }
300            return ret[0];
301        }
302
303        /** good values of a variable (values not removed from variables domain) 
304         * @param variable given variable
305         * @return good values for the variable (i.e., values from the domain of the variable that have no no-good set)
306         **/
307        @SuppressWarnings("unchecked")
308        public Set<T> goodValues(V variable) {
309            Set<T>[] ret = getNoGood(variable);
310            if (ret == null) {
311                ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
312                setNoGood(variable, ret);
313            }
314            return ret[1];
315        }
316
317        /** notification that a no-good value becomes good or vice versa */
318        private void goodnessChanged(T value) {
319            if (isGood(value)) {
320                goodValues(value.variable()).add(value);
321            } else {
322                goodValues(value.variable()).remove(value);
323            }
324        }
325
326        /** removes support of a variable */
327        private void removeSupport(V variable, T value) {
328            supportValues(variable).remove(value);
329        }
330
331        /** adds support of a variable */
332        private void addSupport(V variable, T value) {
333            supportValues(variable).add(value);
334        }
335
336        /** variables explanation 
337         * @param value given value
338         * @return no-good set for the value 
339         **/
340        public Set<T> noGood(T value) {
341            return getNoGood(value);
342        }
343
344        /** is variable good 
345         * @param value given value
346         * @return true if good, i.e., the value has no no-good set 
347         **/
348        public boolean isGood(T value) {
349            return (getNoGood(value) == null);
350        }
351
352        /** sets value to be good 
353         * @param value given value
354         **/
355        protected void setGood(T value) {
356            sLogger.debug("    -- set good " + value.variable().getName() + " = " + value.getName());
357            Set<T> noGood = noGood(value);
358            if (noGood != null)
359                for (T v : noGood)
360                    removeSupport(v.variable(), value);
361            setNoGood(value, null);
362            goodnessChanged(value);
363        }
364
365        /** sets values explanation (initialization) */
366        private void initNoGood(T value, Set<T> reason) {
367            setNoGood(value, reason);
368        }
369        
370        public void propagate(Assignment<V, T> assignment, List<T> queue) {
371            int idx = 0;
372            while (queue.size() > idx) {
373                T value = queue.get(idx++);
374                sLogger.debug("  -- propagate " + value.variable().getName() + " = " + value.getName() + " (noGood:" + noGood(value) + ")");
375                if (goodValues(value.variable()).isEmpty()) {
376                    sLogger.info("Empty domain detected for variable " + value.variable().getName());
377                    continue;
378                }
379                for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
380                    if (!contains(constraint))
381                        continue;
382                    propagate(assignment, constraint, value, queue);
383                }
384            }
385        }
386
387        public void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T noGoodValue, List<T> queue) {
388            for (V aVariable : constraint.variables()) {
389                if (aVariable.equals(noGoodValue.variable()))
390                    continue;
391                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
392                    T aValue = j.next();
393                    if (isGood(aValue) && constraint.isConsistent(noGoodValue, aValue)
394                            && !hasSupport(assignment, constraint, aValue, noGoodValue.variable())) {
395                        setNoGood(aValue, explanation(assignment, constraint, aValue, noGoodValue.variable()));
396                        queue.add(aValue);
397                    }
398                }
399            }
400        }
401
402        public boolean revise(Assignment<V, T> assignment, T value) {
403            sLogger.debug("  -- revise " + value.variable().getName() + " = " + value.getName());
404            for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
405                if (!contains(constraint))
406                    continue;
407                if (revise(assignment, constraint, value))
408                    return true;
409            }
410            return false;
411        }
412
413        public boolean revise(Assignment<V, T> assignment, Constraint<V, T> constraint, T value) {
414            for (V aVariable : constraint.variables()) {
415                if (aVariable.equals(value.variable()))
416                    continue;
417                if (!hasSupport(assignment, constraint, value, aVariable)) {
418                    setNoGood(value, explanation(assignment, constraint, value, aVariable));
419                    return true;
420                }
421            }
422            return false;
423        }
424
425        public Set<T> explanation(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) {
426            Set<T> expl = new HashSet<T>();
427            for (T aValue : variable.values(assignment)) {
428                if (constraint.isConsistent(aValue, value)) {
429                    expl.addAll(noGood(aValue));
430                }
431            }
432            return expl;
433        }
434
435        public Set<T> supports(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) {
436            Set<T> sup = new HashSet<T>();
437            for (T aValue : variable.values(assignment)) {
438                if (!isGood(aValue))
439                    continue;
440                if (!constraint.isConsistent(aValue, value))
441                    continue;
442                sup.add(aValue);
443            }
444            return sup;
445        }
446
447        public boolean hasSupport(Assignment<V, T> assignment, Constraint<V, T> constraint, T value, V variable) {
448            for (T aValue : variable.values(assignment)) {
449                if (isGood(aValue) && constraint.isConsistent(aValue, value)) {
450                    // sLogger.debug("    -- "+variable.getName()+" = "+aValue.getName()+" supports "
451                    // +
452                    // value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")");
453                    return true;
454                }
455            }
456            // sLogger.debug("    -- value "+value.variable().getName()+" = " +
457            // value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")");
458            /*
459             * for (Enumeration e=variable.values().elements();e.hasMoreElements();)
460             * { T aValue = (T)e.nextElement(); if
461             * (constraint.isConsistent(aValue,value)) {
462             * //sLogger.debug("      -- support "
463             * +aValue.getName()+" is not good: "+expl2str(noGood(aValue))); } }
464             */
465            return false;
466        }
467        
468        /** sets value's explanation 
469         * @param assignment current assignment
470         * @param value a value
471         * @param reason no-good set for the value
472         **/
473        public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
474            sLogger.debug("    -- set nogood " + value.variable().getName() + " = " + value.getName() + "(expl:" + expl2str(reason) + ")");
475            if (value.equals(assignment.getValue(value.variable()))) {
476                try {
477                    throw new Exception("An assigned value " + value.variable().getName() + " = " + value.getName() + " become no good (noGood:" + reason + ")!!");
478                } catch (Exception e) {
479                    sLogger.warn(e.getMessage(), e);
480                }
481                checkExpl(assignment, reason);
482                printAssignments(assignment);
483            }
484            Set<T> noGood = noGood(value);
485            if (noGood != null)
486                for (T v : noGood)
487                    removeSupport(v.variable(), value);
488            setNoGood(value, reason);
489            for (T aValue : reason) {
490                addSupport(aValue.variable(), value);
491            }
492            goodnessChanged(value);
493        }
494    }
495}