Module org.maxicp

Package org.maxicp.util.algo

Class BinPacking

java.lang.Object

org.maxicp.util.algo.BinPacking

public class BinPacking
extends Object

This class provides algorithms for the Bin Packing.

Author:

pschaus

Constructor Summary

Constructors

Constructor	Description
BinPacking()

Method Summary

Modifier and Type	Method	Description
static int[]	firstFitDecreasing(int[] weights, int capacity)	Computes the bin index for each item using the First-Fit Decreasing heuristic.
static int	labbeLB(int[] w, int c)	Lower-Bound introduced in: "Capacitated vehicle routing on trees."

Methods inherited from class java.lang.Object

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

Constructor Details

BinPacking

public BinPacking()

Method Details

firstFitDecreasing

public static int[] firstFitDecreasing(int[] weights,
 int capacity)

Computes the bin index for each item using the First-Fit Decreasing heuristic. The number of bins used is Arrays.stream(result).max().orElse(0) + 1.

Parameters:

weights - an array of item weights

capacity - the capacity of each bin

Returns:

an array where result[i] represents the bin index of item i

Throws:

IllegalArgumentException - if any item weight is negative or exceeds the bin capacity

labbeLB

public static int labbeLB(int[] w,
 int c)

Lower-Bound introduced in: "Capacitated vehicle routing on trees." Labbe Martine, Gilbert Laporte, and Helene Mercure. Operations Research 39.4 (1991): 616-622.

Parameters:

w - an array of decreasing positive weights

c - the capacity

Returns:

the computed lower bound