Package org.jacop.constraints.binpacking
Class Binpacking
- java.lang.Object
-
- org.jacop.constraints.DecomposedConstraint<Constraint>
-
- org.jacop.constraints.Constraint
-
- org.jacop.constraints.binpacking.Binpacking
-
- All Implemented Interfaces:
SatisfiedPresent
,Stateful
,UsesQueueVariable
public class Binpacking extends Constraint implements UsesQueueVariable, Stateful, SatisfiedPresent
Binpacking constraint implements bin packing problem. It ensures that items are packed into bins while respecting cpacity constraints of each bin.This implementation is based on paper "A Constraint for Bin Packing" by Paul Shaw, CP 2004.
This constraint is not idempotent (does not compute fix-point) and, in case when another computation for fix-point is needed, it adds itself to the constraint queue.
- Version:
- 4.7
-
-
Field Summary
Fields Modifier and Type Field Description private int
alphaP
private int
betaP
private java.util.Map<IntVar,java.lang.Integer>
binMap
private SimpleHashSet<IntVar>
binQueue
private boolean
firstConsistencyCheck
private static java.util.concurrent.atomic.AtomicInteger
idNumber
BinItem[]
item
It keeps together a list of variables which define bin for item i and their weigts.private java.util.Map<IntVar,java.lang.Integer>
itemMap
private SimpleHashSet<IntVar>
itemQueue
(package private) static long
LBnumber
IntVar[]
load
It specifies a list of variables which define bin load.private int
minBinNumber
private int
sizeAllItems
-
Fields inherited from class org.jacop.constraints.Constraint
atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace
-
Fields inherited from class org.jacop.constraints.DecomposedConstraint
queueIndex
-
-
Constructor Summary
Constructors Constructor Description Binpacking(java.util.List<? extends IntVar> bin, java.util.List<? extends IntVar> load, int[] w)
It constructs the binpacking constraint for the supplied variable.Binpacking(java.util.List<? extends IntVar> bin, java.util.List<? extends IntVar> load, int[] w, int minBin)
It constructs the binpacking constraint for the supplied variable.Binpacking(IntVar[] bin, IntVar[] load, int[] w)
It constructs the binpacking constraint for the supplied variable.Binpacking(IntVar[] bin, IntVar[] load, int[] w, int minBin)
It constructs the binpacking constraint for the supplied variable.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
consistency(Store store)
It is a (most probably incomplete) consistency function which removes the values from variables domains.int
getDefaultConsistencyPruningEvent()
private int
getNumberBins(BinItem[] item)
private void
lbBins(int[] x, int C, int nb)
(package private) void
lbNumberBins()
private int[]
merge(int[] a, int aLength, int[] b)
private boolean
no_sum(int[] x, int alpha, int beta)
void
queueVariable(int level, Var var)
This is a function called to indicate which variable in a scope of constraint has changed.void
removeLevel(int level)
This function is called in case of the backtrack, so a constraint can clear the queue of changed variables which is no longer valid.boolean
satisfied()
It checks if the constraint is satisfied.private int
sum(int[] x)
java.lang.String
toString()
It produces a string representation of a constraint state.-
Methods inherited from class org.jacop.constraints.Constraint
afc, arguments, cleanAfterFailure, decompose, getConsistencyPruningEvent, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, impose, imposeDecomposition, increaseWeight, intArrayToString, numberArgs, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, updateAFC, watchedVariableGrounded
-
Methods inherited from class org.jacop.constraints.DecomposedConstraint
auxiliaryVariables, checkInput, checkInput, checkInputForDuplication, checkInputForDuplicationSkipSingletons, checkInputForNullness, checkInputForNullness, checkInputForNullness, derivative, getDubletonsSkipSingletons, imposeDecomposition
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface org.jacop.api.Stateful
isStateful
-
-
-
-
Field Detail
-
idNumber
private static final java.util.concurrent.atomic.AtomicInteger idNumber
-
item
public final BinItem[] item
It keeps together a list of variables which define bin for item i and their weigts.
-
load
public final IntVar[] load
It specifies a list of variables which define bin load.
-
firstConsistencyCheck
private boolean firstConsistencyCheck
-
minBinNumber
private int minBinNumber
-
sizeAllItems
private int sizeAllItems
-
alphaP
private int alphaP
-
betaP
private int betaP
-
itemQueue
private final SimpleHashSet<IntVar> itemQueue
-
binQueue
private final SimpleHashSet<IntVar> binQueue
-
itemMap
private final java.util.Map<IntVar,java.lang.Integer> itemMap
-
binMap
private final java.util.Map<IntVar,java.lang.Integer> binMap
-
LBnumber
static long LBnumber
-
-
Constructor Detail
-
Binpacking
public Binpacking(IntVar[] bin, IntVar[] load, int[] w)
It constructs the binpacking constraint for the supplied variable.- Parameters:
bin
- which are constrained to define bin for item i.load
- which are constrained to define load for bin i.w
- which define size ofitem i.
-
Binpacking
public Binpacking(java.util.List<? extends IntVar> bin, java.util.List<? extends IntVar> load, int[] w)
It constructs the binpacking constraint for the supplied variable.- Parameters:
bin
- which are constrained to define bin for item i.load
- which are constrained to define load for bin i.w
- which define size ofitem i.
-
Binpacking
public Binpacking(IntVar[] bin, IntVar[] load, int[] w, int minBin)
It constructs the binpacking constraint for the supplied variable.- Parameters:
bin
- which are constrained to define bin for item i.load
- which are constrained to define load for bin i.w
- which define size ofitem i.minBin
- minimal index of a bin; ovewrite the value provided by minimal index of variable bin
-
Binpacking
public Binpacking(java.util.List<? extends IntVar> bin, java.util.List<? extends IntVar> load, int[] w, int minBin)
It constructs the binpacking constraint for the supplied variable.- Parameters:
bin
- which are constrained to define bin for item i.load
- which are constrained to define load for bin i.w
- which define size ofitem i.minBin
- minimal index of a bin; ovewrite the value provided by minimal index of variable bin
-
-
Method Detail
-
consistency
public void consistency(Store store)
Description copied from class:Constraint
It is a (most probably incomplete) consistency function which removes the values from variables domains. Only values which do not have any support in a solution space are removed.- Specified by:
consistency
in classConstraint
- Parameters:
store
- constraint store within which the constraint consistency is being checked.
-
lbNumberBins
void lbNumberBins()
-
getNumberBins
private int getNumberBins(BinItem[] item)
-
merge
private int[] merge(int[] a, int aLength, int[] b)
-
getDefaultConsistencyPruningEvent
public int getDefaultConsistencyPruningEvent()
- Specified by:
getDefaultConsistencyPruningEvent
in classConstraint
-
satisfied
public boolean satisfied()
Description copied from interface:SatisfiedPresent
It checks if the constraint is satisfied. It can return false even if constraint is satisfied but not all variables in its scope are grounded. It needs to return true if all variables in its scope are grounded and constraint is satisfied.Implementations of this interface for constraints that are not PrimitiveConstraint may require constraint imposition and consistency check as a requirement to work correctly.
- Specified by:
satisfied
in interfaceSatisfiedPresent
- Returns:
- true if constraint is possible to verify that it is satisfied.
-
queueVariable
public void queueVariable(int level, Var var)
Description copied from class:Constraint
This is a function called to indicate which variable in a scope of constraint has changed. It also indicates a store level at which the change has occurred.- Overrides:
queueVariable
in classConstraint
- Parameters:
level
- the level of the store at which the change has occurred.var
- variable which has changed.
-
removeLevel
public void removeLevel(int level)
Description copied from interface:Stateful
This function is called in case of the backtrack, so a constraint can clear the queue of changed variables which is no longer valid. This function is called *before* all timestamps, variables, mutablevariables have reverted to their previous value.- Specified by:
removeLevel
in interfaceStateful
- Parameters:
level
- the level which is being removed.
-
toString
public java.lang.String toString()
Description copied from class:Constraint
It produces a string representation of a constraint state.- Overrides:
toString
in classConstraint
-
no_sum
private boolean no_sum(int[] x, int alpha, int beta)
-
sum
private int sum(int[] x)
-
lbBins
private void lbBins(int[] x, int C, int nb)
-
-