    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}