Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems.binpack

Class BinPacking.Triplet

java.lang.Object
org.cicirello.search.problems.binpack.BinPacking
org.cicirello.search.problems.binpack.BinPacking.Triplet
All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>
Enclosing class:
BinPacking
public static final class BinPacking.Triplet extends BinPacking
Generates instances of the Bin Packing problem where the optimal solution is comprised of all full triplet bins (each bin in optimal solution has exactly 3 items that fills the bin to capacity). The cost of the optimal solution to each such instance is one third the number of items.

The bin capacity for the instances generated by this method is 1000. When generating the instance, each triplet is generated as follows. The size of one item is uniform at random from the interval [380, 490]. The second item's size is generated uniformly at random from [250, s/2), where s is 1000 - size of the first item. The third item for the triplet has size 1000 - s - t, where s and t are the sizes of the first two items.

The triplets, as defined above, are as described in: "A Hybrid Grouping Genetic Algorithm for Bin Packing" by Emanuel Falkenauer.

  • Constructor Details

    • Triplet

      public Triplet(int numItemTriplets)
      Generates a triplet instance of the Bin Packing Problem.
      Parameters:
      numItemTriplets - The number of triplets. The number of items in the instance will equal 3 * numItemTriplets.
      Throws:
      NegativeArraySizeException - if numItemTriplets is negative.

    • Triplet

      public Triplet(int numItemTriplets, long seed)
      Generates a triplet instance of the Bin Packing Problem.
      Parameters:
      numItemTriplets - The number of triplets. The number of items in the instance will equal 3 * numItemTriplets.
      seed - The seed for the random number generator to enable reproducible problem instances.
      Throws:
      NegativeArraySizeException - if numItemTriplets is negative.