choco.integer.constraints
Class IntLinComb

java.lang.Object
  choco.AbstractEntity
      choco.AbstractConstraint
          choco.integer.constraints.AbstractIntConstraint
              choco.integer.constraints.AbstractLargeIntConstraint
                  choco.integer.constraints.IntLinComb

All Implemented Interfaces:

Constraint, Entity, IntConstraint, IntVarEventListener, VarEventListener, Propagator, java.lang.Cloneable, java.util.EventListener

Direct Known Subclasses:

PalmIntLinComb

public class IntLinComb
extends AbstractLargeIntConstraint

Implements a constraint Sigma (ai Xi) <=/>=/= C, with Xi variables, ai and C constants.

Field Summary

protected int[]	coeffs The coefficients of the linear equations.
protected int	cste The constant of the constraint.
static int	EQ Constant, to be assigned to op, representing linear equalities.
static int	GEQ Constant, to be assigned to op, representing linear inequalities.
protected int	nbPosVars Field representing the number of variables with positive coeffficients in the linear combination.
static int	NEQ Constant, to be assigned to op, representing linear disequalities.
protected int	op Field representing the type of linear constraint (equality, inequality, disequality).

Fields inherited from class choco.integer.constraints.AbstractLargeIntConstraint

cIndices, vars

Fields inherited from class choco.integer.constraints.AbstractIntConstraint

logger

Fields inherited from class choco.AbstractConstraint

active, constAwakeEvent, hook, priority

Fields inherited from class choco.AbstractEntity

problem

Constructor Summary

IntLinComb(IntDomainVar[] lvars, int[] lcoeffs, int nbPositive, int c, int linOperator)
Constructs the constraint with the specified variables and constant.

Method Summary

void	awakeOnInf(int idx) Propagation whenever the lower bound of a variable is modified.
void	awakeOnInst(int idx) Propagation whenever a variable is instantiated.
void	awakeOnRem(int idx, int x) Propagation whenever a value is removed from the variable domain.
void	awakeOnSup(int idx) Propagation whenever the upper bound of a variable is modified.
void	awakeOnVar(int idx) Generic propagation when a variable is modified.
java.lang.Object	clone() Builds a copy of this contraint.
protected int	computeLowerBound() Computes a lower bound estimate of a linear combination of variables.
protected int	computeUpperBound() Computes an upper bound estimate of a linear combination of variables.
protected void	filter(boolean startWithLB, int minNbRules) A strategy for chaotic iteration with two rules (LB and UB propagation).
protected boolean	filterOnImprovedLowerBound() Checks a new lower bound.
protected boolean	filterOnImprovedUpperBound() Checks a new upper bound.
protected boolean	hasConsistentLowerBound() Tests if the constraint is consistent with respect to the current state of domains.
protected boolean	hasConsistentUpperBound() Tests if the constraint is consistent with respect to the current state of domains.
void	init(int[] lcoeffs) Initializes the constraint by copying the coefficent array.
boolean	isConsistent() Tests if the constraint is consistent with respect to the current state of domains.
java.lang.Boolean	isEntailed() Checks if the constraint is entailed.
boolean	isEquivalentTo(Constraint compareTo) Checks if this constraint is equivalent to the argument constraint.
boolean	isSatisfied() Checks if the constraint is satisfied when all variables are instantiated.
AbstractConstraint	opposite() Computes the opposite of this constraint.
java.lang.String	pretty() Pretty print for this constraint.
void	propagate() Launchs the filtering algorithm.
protected boolean	propagateNewLowerBound(int mylb) Propagates the constraint sigma(ai Xi) + c <= 0 where mylb = sigma(ai inf(Xi)) + c.
protected boolean	propagateNewUpperBound(int myub) Propagates the constraint sigma(ai Xi) + c <= 0 where myub = sigma(ai sup(Xi)) + c.

Methods inherited from class choco.integer.constraints.AbstractLargeIntConstraint

assignIndices, getConstraintIdx, getIntVar, getNbVars, getVar, isCompletelyInstantiated, setConstraintIndex, setVar

Methods inherited from class choco.integer.constraints.AbstractIntConstraint

awakeOnBounds, awakeOnRemovals, getSelfIndex

Methods inherited from class choco.AbstractConstraint

addListener, awake, connectVar, constAwake, delete, fail, getEvent, getPlugIn, getPriority, getProblem, getVarIdxInOpposite, isActive, setActive, setEntailed, setPassive, setPlugIn, substituteVar

Methods inherited from class java.lang.Object

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

Methods inherited from interface choco.Propagator

awake, constAwake, delete, getEvent, getPlugIn, getPriority

Methods inherited from interface choco.prop.VarEventListener

addListener, isActive, setActive, setPassive

Methods inherited from interface choco.prop.VarEventListener

addListener, isActive, setActive, setPassive

Field Detail

EQ

public static final int EQ

Constant, to be assigned to op, representing linear equalities.

See Also:

Constant Field Values

GEQ

public static final int GEQ

Constant, to be assigned to op, representing linear inequalities.

See Also:

Constant Field Values

NEQ

public static final int NEQ

Constant, to be assigned to op, representing linear disequalities.

See Also:

Constant Field Values

op

protected final int op

Field representing the type of linear constraint (equality, inequality, disequality).

coeffs

protected int[] coeffs

The coefficients of the linear equations. The positive coefficents should be the first ones.

nbPosVars

protected final int nbPosVars

Field representing the number of variables with positive coeffficients in the linear combination.

cste

protected final int cste

The constant of the constraint.

Constructor Detail

IntLinComb

public IntLinComb(IntDomainVar[] lvars,
                  int[] lcoeffs,
                  int nbPositive,
                  int c,
                  int linOperator)

Constructs the constraint with the specified variables and constant. Use the Problem.createIntLinComb API instead of this constructor. This constructor assumes that there are no null coefficient and that the positive coefficients come before the negative ones.

Parameters:

lvars - the variables of the constraint

lcoeffs - the constant coefficients

nbPositive - number of positive coefficients

c - the constant value of the constraint (the value the linear expression must equal)

linOperator - the operator to use (equality, inequality...)

Method Detail

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException

Builds a copy of this contraint.

Specified by:

clone in interface Constraint

Overrides:

clone in class AbstractLargeIntConstraint

Returns:

a clone of this constraint

Throws:

java.lang.CloneNotSupportedException - if an error occurs during cloning

init

public void init(int[] lcoeffs)

Initializes the constraint by copying the coefficent array.

Parameters:

lcoeffs - the coefficients of the linear equation

propagate

public void propagate()
               throws ContradictionException

Launchs the filtering algorithm.

Specified by:

propagate in interface Propagator

Overrides:

propagate in class AbstractLargeIntConstraint

Throws:

ContradictionException - if a domain empties or a contradiction is infered

awakeOnVar

public void awakeOnVar(int idx)
                throws ContradictionException

Generic propagation when a variable is modified. Here no propagation.

Specified by:

awakeOnVar in interface VarEventListener

Specified by:

awakeOnVar in interface Propagator

Overrides:

awakeOnVar in class AbstractConstraint

Parameters:

idx - the index of the modified variable

Throws:

ContradictionException - if a domain empties or a contradiction is infered

awakeOnInf

public void awakeOnInf(int idx)
                throws ContradictionException

Propagation whenever the lower bound of a variable is modified.

Specified by:

awakeOnInf in interface IntVarEventListener

Overrides:

awakeOnInf in class AbstractIntConstraint

Parameters:

idx - the index of the modified variable

Throws:

ContradictionException - if a domain empties or a contradiction is infered

awakeOnSup

public void awakeOnSup(int idx)
                throws ContradictionException

Propagation whenever the upper bound of a variable is modified.

Specified by:

awakeOnSup in interface IntVarEventListener

Overrides:

awakeOnSup in class AbstractIntConstraint

Parameters:

idx - the index of the modified variable

Throws:

ContradictionException - if a domain empties or a contradiction is infered

awakeOnInst

public void awakeOnInst(int idx)
                 throws ContradictionException

Propagation whenever a variable is instantiated.

Specified by:

awakeOnInst in interface IntVarEventListener

Overrides:

awakeOnInst in class AbstractIntConstraint

Parameters:

idx - the index of the modified variable

Throws:

ContradictionException - if a domain empties or a contradiction is infered

awakeOnRem

public void awakeOnRem(int idx,
                       int x)
                throws ContradictionException

Propagation whenever a value is removed from the variable domain.

Specified by:

awakeOnRem in interface IntVarEventListener

Overrides:

awakeOnRem in class AbstractIntConstraint

Parameters:

idx - the index of the modified variable

x - the removed value

Throws:

ContradictionException - if a domain empties or a contradiction is infered

isEntailed

public java.lang.Boolean isEntailed()

Checks if the constraint is entailed.

Specified by:

isEntailed in interface Propagator

Overrides:

isEntailed in class AbstractConstraint

Returns:

Boolean.TRUE if the constraint is satisfied, Boolean.FALSE if it is violated, and null if the filtering algorithm cannot infer yet.

isSatisfied

public boolean isSatisfied()

Checks if the constraint is satisfied when all variables are instantiated.

Returns:

true if the constraint is satisfied

computeUpperBound

protected int computeUpperBound()

Computes an upper bound estimate of a linear combination of variables.

Returns:

the new upper bound value

computeLowerBound

protected int computeLowerBound()

Computes a lower bound estimate of a linear combination of variables.

Returns:

the new lower bound value

filter

protected void filter(boolean startWithLB,
                      int minNbRules)
               throws ContradictionException

A strategy for chaotic iteration with two rules (LB and UB propagation). The fix point is reached individually for each rule in one function call but this call may break the stability condition for the other rule (in which case the second rule infers new information from the fresh inferences made by the first rule). The algorithm oscilates between both rules until a global fix point is reached.

Parameters:

startWithLB - whether LB must be the first rule applied

minNbRules - minimum number of rules required to reach fix point.

Throws:

ContradictionException - if a domain empties or a contradiction is infered

filterOnImprovedLowerBound

protected boolean filterOnImprovedLowerBound()
                                      throws ContradictionException

Checks a new lower bound.

Returns:

true if filtering has been infered

Throws:

ContradictionException - if a domain empties or a contradiction is infered

filterOnImprovedUpperBound

protected boolean filterOnImprovedUpperBound()
                                      throws ContradictionException

Checks a new upper bound.

Returns:

true if filtering has been infered

Throws:

ContradictionException - if a domain empties or a contradiction is infered

propagateNewLowerBound

protected boolean propagateNewLowerBound(int mylb)
                                  throws ContradictionException

Propagates the constraint sigma(ai Xi) + c <= 0 where mylb = sigma(ai inf(Xi)) + c. Note: this does not reach saturation (fix point), but returns a boolean indicating whether it infered new information or not.

Parameters:

mylb - the computed lower bound

Returns:

true if filtering has been infered

Throws:

ContradictionException - if a domain empties or a contradiction is infered

propagateNewUpperBound

protected boolean propagateNewUpperBound(int myub)
                                  throws ContradictionException

Propagates the constraint sigma(ai Xi) + c <= 0 where myub = sigma(ai sup(Xi)) + c. Note: this does not reach saturation (fix point), but returns a boolean indicating whether it infered new information or not.

Parameters:

myub - the computed upper bound

Returns:

true if filtering has been infered

Throws:

ContradictionException - if a domain empties or a contradiction is infered

isConsistent

public boolean isConsistent()

Tests if the constraint is consistent with respect to the current state of domains.

Specified by:

isConsistent in interface Propagator

Overrides:

isConsistent in class AbstractIntConstraint

Returns:

true iff the constraint is bound consistent (weaker than arc consistent)

hasConsistentLowerBound

protected boolean hasConsistentLowerBound()

Tests if the constraint is consistent with respect to the current state of domains.

Returns:

true iff the constraint is bound consistent (weaker than arc consistent)

hasConsistentUpperBound

protected boolean hasConsistentUpperBound()

Tests if the constraint is consistent with respect to the current state of domains.

Returns:

true iff the constraint is bound consistent (weaker than arc consistent)

opposite

public AbstractConstraint opposite()

Computes the opposite of this constraint.

Specified by:

opposite in interface Constraint

Overrides:

opposite in class AbstractConstraint

Returns:

a constraint with the opposite semantic

isEquivalentTo

public boolean isEquivalentTo(Constraint compareTo)

Checks if this constraint is equivalent to the argument constraint.

Specified by:

isEquivalentTo in interface Constraint

Overrides:

isEquivalentTo in class AbstractConstraint

Parameters:

compareTo - the constraint to compare with the current one

Returns:

true if the two constraints have the same supports

pretty

public java.lang.String pretty()

Pretty print for this constraint. This method prints the complete equations.

Specified by:

pretty in interface Entity

Overrides:

pretty in class AbstractEntity

Returns:

a strring representation of the constraint