net.sf.cpsolver.ifs.extension
Class MacPropagation

java.lang.Object
  net.sf.cpsolver.ifs.extension.Extension
      net.sf.cpsolver.ifs.extension.MacPropagation

All Implemented Interfaces:

ModelListener

Direct Known Subclasses:

DbtPropagation

public class MacPropagation
extends Extension

MAC propagation.

During the arc consistency maintenance, when a value is deleted from a variable’s domain, the reason (forming an explanation) can be computed and attached to the deleted value. Once a variable (say Vx with the assigned value vx) is unassigned during the search, all deleted values which contain a pair Vx = vx in their explanations need to be recomputed. Such value can be either still inconsistent with the current (partial) solution (a different explanation is attached to it in this case) or it can be returned back to its variable's domain. Arc consistency is maintained after each iteration step, i.e., the selected assignment is propagated into the not yet assigned variables. When a value vx is assigned to a variable Vx, an explanation Vx != vx' ← Vx = vx is attached to all values vx' of the variable Vx, different from vx.

In the case of forward checking (only constraints going from assigned variables to unassigned variables are revised), computing explanations is rather easy. A value vx is deleted from the domain of the variable Vx only if there is a constraint which prohibits the assignment Vx=vx because of the existing assignments (e.g., Vy = vy, … Vz = vz). An explanation for the deletion of this value vx is then Vx != vx ← (Vy = vy & ... Vz = vz), where Vy = vy & ... Vz = vz are assignments contained in the prohibiting constraint. In case of arc consistency, a value vx is deleted from the domain of the variable Vx if there is a constraint which does not permit the assignment Vx = vx with other possible assignments of the other variables in the constraint. This means that there is no support value (or combination of values) for the value vx of the variable Vx in the constraint. An explanation is then a union of explanations of all possible support values for the assignment Vx = vx of this constraint which were deleted. The reason is that if one of these support values is returned to its variable's domain, this value vx may be returned as well (i.e., the reason for its deletion has vanished, a new reason needs to be computed).

As for the implementation, we only need to enforce arc consistency of the initial solution and to extend unassign and assign methods. Procedure afterAssigned(long, Value) enforces arc consistency of the solution with the selected assignment variable = value and the procedure afterUnassigned(long, Value) "undoes" the assignment variable = value. It means that explanations of all values which were deleted and which contain assignment variable = value in their explanations need to be recomputed. This can be done via returning all these values into their variables’ domains followed by arc consistency maintenance over their variables.

Parameters:

Parameter	Type	Comment
MacPropagation.JustForwardCheck	Boolean	If true, only forward checking instead of full arc consistency is maintained during the search.

Version:

IFS 1.1 (Iterative Forward Search)
Copyright (C) 2006 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Field Summary

protected Vector	iConstraints List of constraints on which arc-consistency is to be maintained
protected long	iIteration Current iteration

Constructor Summary

MacPropagation(Solver solver, DataProperties properties)
Constructor

Method Summary

void	addConstraint(Constraint constraint) Adds a constraint on which arc-consistency is to be maintained
void	afterAssigned(long iteration, Value value) After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value), propagation over the assigned variable takes place.
void	afterUnassigned(long iteration, Value value) After a value is unassigned: explanations of all values of unassigned variable are recomputed (Value.conflicts()), propagation undo over the unassigned variable takes place.
void	beforeAssigned(long iteration, Value value) Before a value is unassigned: until the value is inconsistent with the current solution, an assignment from its explanation is picked and unassigned.
boolean	contains(Constraint constraint) Returns true, if arc-consistency is to be maintained on the given constraint
Set	goodValues(Variable variable) good values of a variable (values not removed from variables domain)
boolean	init(Solver solver) Initialization.
boolean	isGood(Value value) is variable good
Set	noGood(Value value) variables explanation
protected void	propagate(Queue queue) Propagation over the queue of variables.
protected void	propagate(Variable variable) Propagation over the given variable.
protected boolean	propagate(Variable aVariable, Variable anotherVariable)
protected boolean	propagate(Variable aVariable, Variable anotherVariable, Vector adepts)
protected void	setGood(Value value) sets value to be good
void	setNoGood(Value value, Set reason) sets value's explanation
void	undoPropagate(Variable variable) Propagation undo over the given variable.

Methods inherited from class net.sf.cpsolver.ifs.extension.Extension

beforeUnassigned, constraintAdded, constraintRemoved, getModel, getProperties, getSolver, isRegistered, register, unregister, useValueExtra, useVariableExtra, variableAdded, variableRemoved

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

iConstraints

protected Vector iConstraints

List of constraints on which arc-consistency is to be maintained

iIteration

protected long iIteration

Current iteration

Constructor Detail

MacPropagation

public MacPropagation(Solver solver,
                      DataProperties properties)

Constructor

Method Detail

addConstraint

public void addConstraint(Constraint constraint)

Adds a constraint on which arc-consistency is to be maintained

contains

public boolean contains(Constraint constraint)

Returns true, if arc-consistency is to be maintained on the given constraint

beforeAssigned

public void beforeAssigned(long iteration,
                           Value value)

Before a value is unassigned: until the value is inconsistent with the current solution, an assignment from its explanation is picked and unassigned.

Specified by:

beforeAssigned in interface ModelListener

Overrides:

beforeAssigned in class Extension

Parameters:

iteration - current iteration

value - value to be assigned

afterAssigned

public void afterAssigned(long iteration,
                          Value value)

After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value), propagation over the assigned variable takes place.

Specified by:

afterAssigned in interface ModelListener

Overrides:

afterAssigned in class Extension

Parameters:

iteration - current iteration

value - value to be assigned

afterUnassigned

public void afterUnassigned(long iteration,
                            Value value)

After a value is unassigned: explanations of all values of unassigned variable are recomputed (Value.conflicts()), propagation undo over the unassigned variable takes place.

Specified by:

afterUnassigned in interface ModelListener

Overrides:

afterUnassigned in class Extension

Parameters:

iteration - current iteration

value - value to be unassigned

init

public boolean init(Solver solver)

Initialization. Enforce arc-consistency over the current (initial) solution. AC3 algorithm is used.

Specified by:

init in interface ModelListener

Overrides:

init in class Extension

Parameters:

solver - IFS solver

propagate

protected void propagate(Variable variable)

Propagation over the given variable.

propagate

protected void propagate(Queue queue)

Propagation over the queue of variables.

undoPropagate

public void undoPropagate(Variable variable)

Propagation undo over the given variable. All values having given variable in thair explanations needs to be recomputed. This is done in two phases: 1) values that contain this variable in explanation are returned back to domains (marked as good) 2) propagation over variables which contains a value that was marked as good takes place

propagate

protected boolean propagate(Variable aVariable,
                            Variable anotherVariable,
                            Vector adepts)

propagate

protected boolean propagate(Variable aVariable,
                            Variable anotherVariable)

goodValues

public Set goodValues(Variable variable)

good values of a variable (values not removed from variables domain)

noGood

public Set noGood(Value value)

variables explanation

isGood

public boolean isGood(Value value)

is variable good

setGood

protected void setGood(Value value)

sets value to be good

setNoGood

public void setNoGood(Value value,
                      Set reason)

sets value's explanation