org.cpsolver.ifs.extension

Class MacRevised<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object

org.cpsolver.ifs.extension.Extension<V,T>

org.cpsolver.ifs.assignment.context.ExtensionWithContext<V,T,MacRevised.NoGood>

org.cpsolver.ifs.extension.MacRevised<V,T>

Type Parameters:

V - Variable

T - Value

All Implemented Interfaces:

CanHoldContext, HasAssignmentContext<V,T,MacRevised.NoGood>, ModelListener<V,T>

public class MacRevised<V extends Variable<V,T>,T extends Value<V,T>>
extends ExtensionWithContext<V,T,MacRevised.NoGood>

Another implementation of MAC propagation.

Version:

IFS 1.3 (Iterative Forward Search)
Copyright (C) 2006 - 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

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 3 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 see http://www.gnu.org/licenses/.

Author:

Tomáš Müller

See Also:

MacPropagation

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	MacRevised.NoGood Assignment context

Field Summary

Fields

Modifier and Type	Field and Description
protected List<Constraint<V,T>>	iConstraints List of constraints on which arc-consistency is to be maintained
protected long	iIteration Current iteration

Fields inherited from interface org.cpsolver.ifs.assignment.context.CanHoldContext

sMaxSize

Constructor Summary

Constructors

Constructor and Description
MacRevised(Solver<V,T> solver, DataProperties properties) Constructor

Method Summary

Modifier and Type	Method and Description
void	addConstraint(Constraint<V,T> constraint) Adds a constraint on which arc-consistency is to be maintained
void	afterAssigned(Assignment<V,T> assignment, long iteration, T 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(Assignment<V,T> assignment, long iteration, T value) After a value is unassigned: explanations of all values of unassigned variable are recomputed (Value.conflicts(Assignment)), propagation undo over the unassigned variable takes place.
void	beforeAssigned(Assignment<V,T> assignment, long iteration, T 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<V,T> constraint) Returns true, if arc-consistency is to be maintained on the given constraint
MacRevised.NoGood	createAssignmentContext(Assignment<V,T> assignment) Create a new assignment context for the given assignment.
boolean	init(Solver<V,T> solver) Initialization.

Methods inherited from class org.cpsolver.ifs.assignment.context.ExtensionWithContext

getAssignmentContextReference, getContext, getContext, setAssignmentContextReference, unregister

Methods inherited from class org.cpsolver.ifs.extension.Extension

beforeUnassigned, constraintAdded, constraintRemoved, getModel, getProperties, getSolver, isRegistered, register, variableAdded, variableRemoved

Methods inherited from class java.lang.Object

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

Field Detail

iConstraints

protected List<Constraint<V extends Variable<V,T>,T extends Value<V,T>>> iConstraints

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

iIteration

protected long iIteration

Current iteration

Constructor Detail

MacRevised

public MacRevised(Solver<V,T> solver,
                  DataProperties properties)

Constructor

Parameters:

solver - current solver

properties - solver configuration

Method Detail

addConstraint

public void addConstraint(Constraint<V,T> constraint)

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

Parameters:

constraint - a hard constraint to be added

contains

public boolean contains(Constraint<V,T> constraint)

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

Parameters:

constraint - a constraint

Returns:

true if the constraint is in the set

beforeAssigned

public void beforeAssigned(Assignment<V,T> assignment,
                           long iteration,
                           T 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<V extends Variable<V,T>,T extends Value<V,T>>

Overrides:

beforeAssigned in class Extension<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

assignment - current assignment

iteration - current iteration

value - value to be assigned

afterAssigned

public void afterAssigned(Assignment<V,T> assignment,
                          long iteration,
                          T 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<V extends Variable<V,T>,T extends Value<V,T>>

Overrides:

afterAssigned in class Extension<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

assignment - current assignment

iteration - current iteration

value - value to be assigned

afterUnassigned

public void afterUnassigned(Assignment<V,T> assignment,
                            long iteration,
                            T value)

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

Specified by:

afterUnassigned in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>

Overrides:

afterUnassigned in class Extension<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

assignment - current assignment

iteration - current iteration

value - value to be unassigned

init

public boolean init(Solver<V,T> solver)

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

Specified by:

init in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>

Overrides:

init in class ExtensionWithContext<V extends Variable<V,T>,T extends Value<V,T>,MacRevised.NoGood>

Parameters:

solver - IFS solver

Returns:

true if successfully initialized

createAssignmentContext

public MacRevised.NoGood createAssignmentContext(Assignment<V,T> assignment)

Description copied from interface: HasAssignmentContext

Create a new assignment context for the given assignment. If there are already some variables assigned in the value, the method should make sure that the context is appropriately initialized.

Parameters:

assignment - an assignment for which there needs to be an assignment context

Returns:

a new instance of the assignment context, filled according to the given assignment