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

Class BinPacking

java.lang.Object
org.cicirello.search.problems.binpack.BinPacking
All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>
Direct Known Subclasses:
BinPacking.Triplet, BinPacking.UniformRandom
public class BinPacking extends Object implements IntegerCostOptimizationProblem<Permutation>
This class, and its nested classes, implements the Bin Packing problem. Although you won't instantiate this class directly (it doesn't have a public constructor), its methods can be used to compute the cost of solutions, or to map a Permutation to the details of the solution that it represents (i.e., which items are in which bins). This class also provides methods for getting the sizes of items, and other information about the instance. To generate instances of the Bin Packing problem, use the constructors of the nested subclasses.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    BinPacking.Triplet
    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).
    static final class 
    BinPacking.UniformRandom
    Generates instances of the Bin Packing problem with item sizes that are generated uniformly at random.

  • Method Summary

    Modifier and Type
    Method
    Description
    final int
    cost(Permutation candidate)
    Computes the cost of a candidate solution to the problem instance.
    final int
    getCapacity()
    Gets the bin capacity for the instance.
    final int
    getSize(int i)
    Gets the size of an item.
    final int
    minCost()
    A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    final int
    numItems()
    Gets the number of items in the instance.
    final BinPackingSolution
    permutationToBinPackingSolution(Permutation p)
    Determines the bin packing solution that corresponds to a given permutation, such that the solution is formed by applying a first-fit heuristic using the item ordering implied by the Permutation p.
    final int
    value(Permutation candidate)
    Computes the value of the candidate solution within the usual constraints and interpretation of the problem.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.cicirello.search.problems.IntegerCostOptimizationProblem

    costAsDouble, getSolutionCostPair, isMinCost

  • Method Details

    • getCapacity

      public final int getCapacity()
      Gets the bin capacity for the instance.
      Returns:
      the bin capacity

    • numItems

      public final int numItems()
      Gets the number of items in the instance.
      Returns:
      the number of items

    • getSize

      public final int getSize(int i)
      Gets the size of an item.
      Parameters:
      i - The index of the item.
      Returns:
      the size of item i
      Throws:
      IndexOutOfBoundsException - if i is either negative or greater than or equal to numItems()

    • cost

      public final int cost(Permutation candidate)
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.

      Computes the cost of the solution formed by applying a first-fit heuristic using the item ordering implied by the Permutation candidate. The optimal solution will have index of items for a bin grouped together in the permutation.

      Specified by:
      cost in interface IntegerCostOptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • value

      public final int value(Permutation candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface IntegerCostOptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.

    • minCost

      public final int minCost()
      Description copied from interface: IntegerCostOptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Integer.MIN_VALUE.
      Specified by:
      minCost in interface IntegerCostOptimizationProblem<Permutation>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.

    • permutationToBinPackingSolution

      public final BinPackingSolution permutationToBinPackingSolution(Permutation p)
      Determines the bin packing solution that corresponds to a given permutation, such that the solution is formed by applying a first-fit heuristic using the item ordering implied by the Permutation p.
      Parameters:
      p - A Permutation
      Returns:
      the solution that p represents.