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
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.9
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
private int
private final SimpleHashSet
<IntVar> private boolean
private static final AtomicInteger
final BinItem[]
It keeps together a list of variables which define bin for item i and their weigts.private final SimpleHashSet
<IntVar> (package private) static long
(package private) boolean
final IntVar[]
It specifies a list of variables which define bin load.private int
private int
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
ConstructorsConstructorDescriptionBinpacking
(List<? extends IntVar> bin, List<? extends IntVar> load, int[] w) It constructs the binpacking constraint for the supplied variable.Binpacking
(List<? extends IntVar> bin, 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.Binpacking
(IntVar[] bin, IntVar[] load, int[] w, int minBin, boolean LBpruning) -
Method Summary
Modifier and TypeMethodDescriptionvoid
consistency
(Store store) It is a (most probably incomplete) consistency function which removes the values from variables domains.int
private int
getNumberBins
(BinItem[] item) void
It imposes the constraint in a given store.private void
lbBins
(int[] x, int C, int nb) (package private) void
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
It checks if the constraint is satisfied.private int
sum
(int[] x) 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, imposeDecomposition, increaseWeight, intArrayToString, long2int, 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 Details
-
idNumber
-
item
It keeps together a list of variables which define bin for item i and their weigts. -
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
-
binQueue
-
itemMap
-
binMap
-
LBpruning
boolean LBpruning -
LBpruningStamp
-
LBnumber
static long LBnumber
-
-
Constructor Details
-
Binpacking
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
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
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
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
-
-
Method Details
-
impose
Description copied from class:Constraint
It imposes the constraint in a given store.- Overrides:
impose
in classConstraint
- Parameters:
store
- the constraint store to which the constraint is imposed to.
-
consistency
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
-
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
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
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)
-