Package org.jacop.constraints.binpacking

Class 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.8

    • 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

      • 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 class Constraint
        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)

      • 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 interface SatisfiedPresent
        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 class Constraint
        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 interface Stateful
        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 class Constraint

      • 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)