001package org.cpsolver.ifs.extension;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.HashSet;
006import java.util.HashMap;
007import java.util.Iterator;
008import java.util.LinkedList;
009import java.util.List;
010import java.util.Map;
011import java.util.Queue;
012import java.util.Set;
013
014import org.cpsolver.ifs.assignment.Assignment;
015import org.cpsolver.ifs.assignment.context.AssignmentContext;
016import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
017import org.cpsolver.ifs.model.Constraint;
018import org.cpsolver.ifs.model.Value;
019import org.cpsolver.ifs.model.Variable;
020import org.cpsolver.ifs.solver.Solver;
021import org.cpsolver.ifs.util.DataProperties;
022import org.cpsolver.ifs.util.Progress;
023
024
025/**
026 * MAC propagation. <br>
027 * <br>
028 * During the arc consistency maintenance, when a value is deleted from a
029 * variable's domain, the reason (forming an explanation) can be computed and
030 * attached to the deleted value. Once a variable (say Vx with the assigned
031 * value vx) is unassigned during the search, all deleted values which contain a
032 * pair Vx = vx in their explanations need to be recomputed. Such value can be
033 * either still inconsistent with the current (partial) solution (a different
034 * explanation is attached to it in this case) or it can be returned back to its
035 * variable's domain. Arc consistency is maintained after each iteration step,
036 * i.e., the selected assignment is propagated into the not yet assigned
037 * variables. When a value vx is assigned to a variable Vx, an explanation Vx !=
038 * vx' &#8592; Vx = vx is attached to all values vx' of the variable Vx,
039 * different from vx. <br>
040 * <br>
041 * In the case of forward checking (only constraints going from assigned
042 * variables to unassigned variables are revised), computing explanations is
043 * rather easy. A value vx is deleted from the domain of the variable Vx only if
044 * there is a constraint which prohibits the assignment Vx=vx because of the
045 * existing assignments (e.g., Vy = vy, Vz = vz). An explanation for the
046 * deletion of this value vx is then Vx != vx &#8592; (Vy = vy &amp; ... Vz = vz),
047 * where Vy = vy &amp; ... Vz = vz are assignments contained in the prohibiting
048 * constraint. In case of arc consistency, a value vx is deleted from the domain
049 * of the variable Vx if there is a constraint which does not permit the
050 * assignment Vx = vx with other possible assignments of the other variables in
051 * the constraint. This means that there is no support value (or combination of
052 * values) for the value vx of the variable Vx in the constraint. An explanation
053 * is then a union of explanations of all possible support values for the
054 * assignment Vx = vx of this constraint which were deleted. The reason is that
055 * if one of these support values is returned to its variable's domain, this
056 * value vx may be returned as well (i.e., the reason for its deletion has
057 * vanished, a new reason needs to be computed). <br>
058 * <br>
059 * As for the implementation, we only need to enforce arc consistency of the
060 * initial solution and to extend unassign and assign methods. Procedure
061 * {@link MacPropagation#afterAssigned(Assignment, long, Value)} enforces arc consistency of
062 * the solution with the selected assignment variable = value and the procedure
063 * {@link MacPropagation#afterUnassigned(Assignment, long, Value)} "undoes" the assignment
064 * variable = value. It means that explanations of all values which were deleted
065 * and which contain assignment variable = value in their explanations need to
066 * be recomputed. This can be done via returning all these values into their
067 * variables' domains followed by arc consistency maintenance over their
068 * variables. <br>
069 * <br>
070 * Parameters:
071 * <table border='1' summary='Related Solver Parameters'>
072 * <tr>
073 * <th>Parameter</th>
074 * <th>Type</th>
075 * <th>Comment</th>
076 * </tr>
077 * <tr>
078 * <td>MacPropagation.JustForwardCheck</td>
079 * <td>{@link Boolean}</td>
080 * <td>If true, only forward checking instead of full arc consistency is
081 * maintained during the search.</td>
082 * </tr>
083 * </table>
084 * 
085 * @version IFS 1.3 (Iterative Forward Search)<br>
086 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
087 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
088 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
089 * <br>
090 *          This library is free software; you can redistribute it and/or modify
091 *          it under the terms of the GNU Lesser General Public License as
092 *          published by the Free Software Foundation; either version 3 of the
093 *          License, or (at your option) any later version. <br>
094 * <br>
095 *          This library is distributed in the hope that it will be useful, but
096 *          WITHOUT ANY WARRANTY; without even the implied warranty of
097 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
098 *          Lesser General Public License for more details. <br>
099 * <br>
100 *          You should have received a copy of the GNU Lesser General Public
101 *          License along with this library; if not see
102 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
103 * @param <V> Variable
104 * @param <T> Value
105 */
106public class MacPropagation<V extends Variable<V, T>, T extends Value<V, T>> extends ExtensionWithContext<V, T, MacPropagation<V, T>.NoGood> {
107    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacPropagation.class);
108    private boolean iJustForwardCheck = false;
109    private Progress iProgress;
110
111    /** List of constraints on which arc-consistency is to be maintained */
112    protected List<Constraint<V, T>> iConstraints = null;
113    /** Current iteration */
114    protected long iIteration = 0;
115
116    /** Constructor 
117     * @param solver current solver 
118     * @param properties solver configuration
119     **/
120    public MacPropagation(Solver<V, T> solver, DataProperties properties) {
121        super(solver, properties);
122        iJustForwardCheck = properties.getPropertyBoolean("MacPropagation.JustForwardCheck", false);
123    }
124
125    /** Adds a constraint on which arc-consistency is to be maintained 
126     * @param constraint a hard constraint
127     **/
128    public void addConstraint(Constraint<V, T> constraint) {
129        if (iConstraints == null)
130            iConstraints = new ArrayList<Constraint<V, T>>();
131        iConstraints.add(constraint);
132    }
133
134    /**
135     * Returns true, if arc-consistency is to be maintained on the given
136     * constraint
137     * @param constraint a constraint
138     * @return true if in the set
139     */
140    public boolean contains(Constraint<V, T> constraint) {
141        if (iConstraints == null)
142            return true;
143        return iConstraints.contains(constraint);
144    }
145
146    /**
147     * Before a value is unassigned: until the value is inconsistent with the
148     * current solution, an assignment from its explanation is picked and
149     * unassigned.
150     */
151    @Override
152    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
153        iIteration = iteration;
154        if (value == null)
155            return;
156        if (!isGood(assignment, value)) {
157            while (!isGood(assignment, value) && !noGood(assignment, value).isEmpty()) {
158                T noGoodValue = noGood(assignment, value).iterator().next();
159                assignment.unassign(iteration, noGoodValue.variable());
160            }
161        }
162        if (!isGood(assignment, value)) {
163            sLogger.warn("Going to assign a bad value " + value + " with empty no-good.");
164        }
165    }
166
167    /**
168     * After a value is assigned: explanations of other values of the value's
169     * variable are reset (to contain only the assigned value), propagation over
170     * the assigned variable takes place.
171     */
172    @Override
173    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
174        iIteration = iteration;
175        if (!isGood(assignment, value)) {
176            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(assignment, value) + ")");
177            setGood(assignment, value);
178        }
179
180        HashSet<T> noGood = new HashSet<T>(1);
181        noGood.add(value);
182        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
183            T anotherValue = i.next();
184            if (anotherValue.equals(value))
185                continue;
186            setNoGood(assignment, anotherValue, noGood);
187        }
188        propagate(assignment, value.variable());
189    }
190
191    /**
192     * After a value is unassigned: explanations of all values of unassigned
193     * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo
194     * over the unassigned variable takes place.
195     */
196    @Override
197    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
198        iIteration = iteration;
199        if (!isGood(assignment, value))
200            sLogger.error(value.variable().getName() + " = " + value.getName()
201                    + " -- not good value unassigned (noGood:" + noGood(assignment, value) + ")");
202        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
203            T anotherValue = i.next();
204            if (!isGood(assignment, anotherValue)) {
205                Set<T> noGood = anotherValue.conflicts(assignment);
206                if (noGood == null)
207                    setGood(assignment, anotherValue);
208                else
209                    setNoGood(assignment, anotherValue, noGood);
210            }
211        }
212        undoPropagate(assignment, value.variable());
213    }
214
215    /**
216     * Initialization. Enforce arc-consistency over the current (initial)
217     * solution. AC3 algorithm is used.
218     */
219
220    /** Propagation over the given variable. 
221     * @param assignment current assignment
222     * @param variable given variable
223     **/
224    protected void propagate(Assignment<V, T> assignment, V variable) {
225        Queue<V> queue = new LinkedList<V>();
226        if (assignment.getValue(variable) != null) {
227            for (Constraint<V, T> constraint : variable.hardConstraints()) {
228                if (contains(constraint))
229                    propagate(assignment, constraint, assignment.getValue(variable), queue);
230            }
231        } else {
232            for (Constraint<V, T> constraint : variable.hardConstraints()) {
233                if (contains(constraint))
234                    propagate(assignment, constraint, variable, queue);
235            }
236        }
237        if (!iJustForwardCheck && !queue.isEmpty())
238            propagate(assignment, queue);
239    }
240
241    /** Propagation over the queue of variables.
242     * @param assignment current assignment
243     * @param queue variable queue
244     **/
245    protected void propagate(Assignment<V, T> assignment, Queue<V> queue) {
246        while (!queue.isEmpty()) {
247            V aVariable = queue.poll();
248            for (Constraint<V, T> constraint : aVariable.hardConstraints()) {
249                if (contains(constraint))
250                    propagate(assignment, constraint, aVariable, queue);
251            }
252        }
253    }
254
255    /**
256     * Propagation undo over the given variable. All values having given
257     * variable in thair explanations needs to be recomputed. This is done in
258     * two phases: 1) values that contain this variable in explanation are
259     * returned back to domains (marked as good) 2) propagation over variables
260     * which contains a value that was marked as good takes place
261     * @param assignment current assignment
262     * @param variable given variable
263     */
264    public void undoPropagate(Assignment<V, T> assignment, V variable) {
265        Map<V, List<T>> undoVars = new HashMap<V, List<T>>();
266        while (!supportValues(assignment, variable).isEmpty()) {
267            T value = supportValues(assignment, variable).iterator().next();
268            Set<T> noGood = value.conflicts(assignment);
269            if (noGood == null) {
270                setGood(assignment, value);
271                List<T> values = undoVars.get(value.variable());
272                if (values == null) {
273                    values = new ArrayList<T>();
274                    undoVars.put(value.variable(), values);
275                }
276                values.add(value);
277            } else {
278                setNoGood(assignment, value, noGood);
279                if (noGood.isEmpty())
280                    (value.variable()).removeValue(iIteration, value);
281            }
282        }
283
284        Queue<V> queue = new LinkedList<V>();
285        for (V aVariable : undoVars.keySet()) {
286            List<T> values = undoVars.get(aVariable);
287            boolean add = false;
288            for (V x : aVariable.constraintVariables().keySet()) {
289                if (propagate(assignment, x, aVariable, values))
290                    add = true;
291            }
292            if (add)
293                queue.add(aVariable);
294        }
295        for (V x : variable.constraintVariables().keySet()) {
296            if (propagate(assignment, x, variable) && !queue.contains(variable))
297                queue.add(variable);
298        }
299        if (!iJustForwardCheck)
300            propagate(assignment, queue);
301    }
302
303    protected boolean propagate(Assignment<V, T> assignment, V aVariable, V anotherVariable, List<T> adepts) {
304        if (goodValues(assignment, aVariable).isEmpty())
305            return false;
306        boolean ret = false;
307        List<T> conflicts = null;
308        for (Constraint<V, T> constraint : anotherVariable.constraintVariables().get(aVariable)) {
309            for (T aValue : goodValues(assignment, aVariable)) {
310                if (conflicts == null)
311                    conflicts = conflictValues(constraint, aValue, adepts);
312                else
313                    conflicts = conflictValues(constraint, aValue, conflicts);
314                if (conflicts == null || conflicts.isEmpty())
315                    break;
316            }
317            if (conflicts != null && !conflicts.isEmpty())
318                for (T conflictValue : conflicts) {
319                    Set<T> reason = reason(assignment, constraint, aVariable, conflictValue);
320                    // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
321                    setNoGood(assignment, conflictValue, reason);
322                    adepts.remove(conflictValue);
323                    if (reason.isEmpty())
324                        (conflictValue.variable()).removeValue(iIteration, conflictValue);
325                    ret = true;
326                }
327        }
328        return ret;
329    }
330
331    protected boolean propagate(Assignment<V, T> assignment, V aVariable, V anotherVariable) {
332        if (goodValues(assignment, anotherVariable).isEmpty())
333            return false;
334        return propagate(assignment, aVariable, anotherVariable, new ArrayList<T>(goodValues(assignment, anotherVariable)));
335    }
336
337    /** support values of a variable */
338    @SuppressWarnings("unchecked")
339    private Set<T> supportValues(Assignment<V, T> assignment, V variable) {
340        Set<T>[] ret = getContext(assignment).getNoGood(variable);
341        if (ret == null) {
342            ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
343            getContext(assignment).setNoGood(variable, ret);
344        }
345        return ret[0];
346    }
347
348    /** good values of a variable (values not removed from variables domain) 
349     * @param assignment current assignment
350     * @param variable given variable
351     * @return set of good values 
352     **/
353    @SuppressWarnings("unchecked")
354    public Set<T> goodValues(Assignment<V, T> assignment, V variable) {
355        Set<T>[] ret = getContext(assignment).getNoGood(variable);
356        if (ret == null) {
357            ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
358            getContext(assignment).setNoGood(variable, ret);
359        }
360        return ret[1];
361    }
362
363    /** notification that a nogood value becomes good or vice versa */
364    private void goodnessChanged(Assignment<V, T> assignment, T value) {
365        if (isGood(assignment, value)) {
366            goodValues(assignment, value.variable()).add(value);
367        } else {
368            goodValues(assignment, value.variable()).remove(value);
369        }
370    }
371
372    /** removes support of a variable */
373    private void removeSupport(Assignment<V, T> assignment, V variable, T value) {
374        supportValues(assignment, variable).remove(value);
375    }
376
377    /** adds support of a variable */
378    private void addSupport(Assignment<V, T> assignment, V variable, T value) {
379        supportValues(assignment, variable).add(value);
380    }
381
382    /** variables explanation 
383     * @param assignment current assignment 
384     * @param value given value
385     * @return no-good for the value
386     **/
387    public Set<T> noGood(Assignment<V, T> assignment, T value) {
388        return getContext(assignment).getNoGood(value);
389    }
390
391    /** is variable good
392     * @param assignment current assignment
393     * @param value given value
394     * @return true if there is no no-good set for the value
395     **/
396    public boolean isGood(Assignment<V, T> assignment, T value) {
397        return getContext(assignment).getNoGood(value) == null;
398    }
399
400    /** sets value to be good 
401     * @param assignment current assignment
402     * @param value given value
403     **/
404    protected void setGood(Assignment<V, T> assignment, T value) {
405        Set<T> noGood = getContext(assignment).getNoGood(value);
406        if (noGood != null)
407            for (T v : noGood)
408                removeSupport(assignment, v.variable(), value);
409        getContext(assignment).setNoGood(value, null);
410        goodnessChanged(assignment, value);
411    }
412
413    /** sets values explanation (initialization) */
414    private void initNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
415        getContext(assignment).setNoGood(value, reason);
416    }
417
418    /** sets value's explanation 
419     * @param assignment current assignment
420     * @param value given value
421     * @param reason no-good set for the value
422     **/
423    public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
424        Set<T> noGood = noGood(assignment, value);
425        if (noGood != null)
426            for (T v : noGood)
427                removeSupport(assignment, v.variable(), value);
428        getContext(assignment).setNoGood(value, reason);
429        for (T aValue : reason)
430            addSupport(assignment, aValue.variable(), value);
431        goodnessChanged(assignment, value);
432    }
433
434    /** propagation over a constraint */
435    private void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T anAssignedValue, Queue<V> queue) {
436        Set<T> reason = new HashSet<T>(1);
437        reason.add(anAssignedValue);
438        Collection<T> conflicts = conflictValues(assignment, constraint, anAssignedValue);
439        if (conflicts != null && !conflicts.isEmpty())
440            for (T conflictValue : conflicts) {
441                // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
442                setNoGood(assignment, conflictValue, reason);
443                if (!queue.contains(conflictValue.variable()))
444                    queue.add(conflictValue.variable());
445            }
446    }
447
448    /** propagation over a constraint */
449    private void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable, Queue<V> queue) {
450        if (goodValues(assignment, aVariable).isEmpty())
451            return;
452        List<T> conflicts = conflictValues(assignment, constraint, aVariable);
453
454        if (conflicts != null && !conflicts.isEmpty()) {
455            for (T conflictValue : conflicts) {
456                if (!queue.contains(conflictValue.variable()))
457                    queue.add(conflictValue.variable());
458                Set<T> reason = reason(assignment, constraint, aVariable, conflictValue);
459                // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
460                setNoGood(assignment, conflictValue, reason);
461                if (reason.isEmpty())
462                    (conflictValue.variable()).removeValue(iIteration, conflictValue);
463            }
464        }
465    }
466
467    private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, T aValue) {
468        List<T> ret = new ArrayList<T>();
469
470        for (V variable : constraint.variables()) {
471            if (variable.equals(aValue.variable()))
472                continue;
473            if (assignment.getValue(variable) != null)
474                continue;
475
476            for (T value : goodValues(assignment, variable))
477                if (!constraint.isConsistent(aValue, value))
478                    ret.add(value);
479        }
480        return ret;
481    }
482
483    private List<T> conflictValues(Constraint<V, T> constraint, T aValue, List<T> values) {
484        List<T> ret = new ArrayList<T>(values.size());
485        for (T value : values)
486            if (!constraint.isConsistent(aValue, value))
487                ret.add(value);
488        return ret;
489    }
490
491    private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable) {
492        List<T> conflicts = null;
493        for (T aValue : goodValues(assignment, aVariable)) {
494            if (conflicts == null)
495                conflicts = conflictValues(assignment, constraint, aValue);
496            else
497                conflicts = conflictValues(constraint, aValue, conflicts);
498            if (conflicts == null || conflicts.isEmpty())
499                return null;
500        }
501        return conflicts;
502    }
503
504    private Set<T> reason(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable, T aValue) {
505        Set<T> ret = new HashSet<T>();
506
507        for (Iterator<T> i = aVariable.values(assignment).iterator(); i.hasNext();) {
508            T value = i.next();
509            if (constraint.isConsistent(aValue, value)) {
510                if (noGood(assignment, value) == null)
511                    sLogger.error("Something went wrong: value " + value + " cannot participate in a reason.");
512                else
513                    ret.addAll(noGood(assignment, value));
514            }
515        }
516        return ret;
517    }
518    
519    @Override
520    public NoGood createAssignmentContext(Assignment<V, T> assignment) {
521        return new NoGood(assignment);
522    }
523
524    /**
525     * Assignment context
526     */
527    public class NoGood implements AssignmentContext {
528        private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>();
529        private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>();
530        
531        public NoGood(Assignment<V, T> assignment) {
532            iProgress = Progress.getInstance(getModel());
533            iProgress.save();
534            iProgress.setPhase("Initializing propagation:", 3 * getModel().variables().size());
535            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
536                V aVariable = i.next();
537                supportValues(assignment, aVariable).clear();
538                goodValues(assignment, aVariable).clear();
539            }
540            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
541                V aVariable = i.next();
542                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
543                    T aValue = j.next();
544                    Set<T> noGood = aValue.conflicts(assignment);
545                    initNoGood(assignment, aValue, noGood);
546                    if (noGood == null) {
547                        goodValues(assignment, aVariable).add(aValue);
548                    } else {
549                    }
550                }
551                iProgress.incProgress();
552            }
553            Queue<V> queue = new LinkedList<V>();
554            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
555                V aVariable = i.next();
556                for (Constraint<V, T> constraint : aVariable.hardConstraints()) {
557                    propagate(assignment, constraint, aVariable, queue);
558                }
559                iProgress.incProgress();
560            }
561            if (!iJustForwardCheck)
562                propagate(assignment, queue);
563            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
564                V aVariable = i.next();
565                List<T> values2delete = new ArrayList<T>();
566                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
567                    T aValue = j.next();
568                    if (!isGood(assignment, aValue) && noGood(assignment, aValue).isEmpty()) {
569                        values2delete.add(aValue);
570                    }
571                }
572                for (T val : values2delete)
573                    aVariable.removeValue(0, val);
574                if (aVariable.values(assignment).isEmpty()) {
575                    sLogger.error(aVariable.getName() + " has empty domain!");
576                }
577                iProgress.incProgress();
578            }
579            iProgress.restore();
580        }
581        
582        public Set<T>[] getNoGood(V variable) {
583            return iNoGood.get(variable);
584        }
585        
586        public void setNoGood(V variable, Set<T>[] noGood) {
587            if (noGood == null)
588                iNoGood.remove(variable);
589            else
590                iNoGood.put(variable, noGood);
591        }
592        
593        public Set<T> getNoGood(T value) {
594            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
595            if (ng == null) return null;
596            return ng.get(value);
597        }
598        
599        public void setNoGood(T value, Set<T> noGood) {
600            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
601            if (ng == null) {
602                ng = new HashMap<T, Set<T>>();
603                iNoGoodVal.put(value.variable(), ng);
604            }
605            if (noGood == null)
606                ng.remove(value);
607            else
608                ng.put(value, noGood);
609        }
610        
611    }
612
613}