# gbp: a bin packing problem solver.

#### Guang Yang

#### 2016-11-19

# Overview

Basic infrastructure and several algorithms for 1d - 4d bin packing problem. This package provides a set of c-level classes and solvers for 1d - 4d bin packing problem, and an r-level solver for 4d bin packing problem, which is a wrapper over the c-level 4d bin packing problem solver.

The 4d bin packing problem solver aims to solve bin packing problem, a.k.a container loading problem, with an additional constraint on weight. Given a set of rectangular-shaped items, and a set of rectangular-shaped bins with weight limit, the solver looks for an orthogonal packing solution such that minimizes the number of bins and maximize volume utilization. Each rectangular-shaped item i = 1, .. , n is characterized by length l_i, depth d_i, height h_i, and weight w_i, and each rectangular-shaped bin j = 1, .. , m is specified similarly by length l_j, depth d_j, height h_j, and weight limit w_j. The item can be rotated into any orthogonal direction, and no further restrictions implied.

# An introduction example

    library(gbp)

Imagine yourself as a store manager, and your customers are placing orders on your inventory catalog. The orders should be specified in a data.table, where each order is uniquely identified by the order id (oid), and each order includes one or more products which each uniquely identified by stock keeping unit (sku) with specific length (l), depth (d), height (h) and weight (w). The orders are expected to be packed into one or more boxes, a.k.a, bins. The available bin types are specified in a data.table, where each type of bin is uniquely indentified by a bin id (id) with specific length (l), depth (d), height (h) and weight limit (w). The objective is packing each order into the smallest number of bins, and then smallest bins to achieve highest utlization rate, subject to the three dimensional none overlap contraints and weight limit constraint.

    #- bpp_solver: input: order list in data.table `it` and bin list in data.table `bn`

    #- it
    #  it item <data.table>
    #  - oid order id <integer>
    #  - sku items id <character>
    #  - l it length which scale will be placed along x-coordinate <numeric>
    #  - d it depth  which scale will be placed along y-coordinate <numeric>
    #  - h it height which scale will be placed along z-coordinate <numeric>
    #  - w it weight which scale will be placed along w-coordinate <numeric>
    # l d h are subject to rotate, while w is on a separate single dimension
    it <- data.table::data.table(
      oid = c(1428571L, 1428571L, 1428571L, 1428572L, 1428572L, 1428572L, 1428572L, 1428572L),
      sku = c("A0A0A0", "A0A0A1", "A0A0A1", "A0A0A0", "A0A0A1", "A0A0A1", "A0A0A2", "A0A0A3"),
      l   = c(2.140000, 7.240000, 7.240000, 2.140000, 7.240000, 7.240000, 6.000000, 4.000000),
      d   = c(3.580000, 7.240000, 7.240000, 3.580000, 7.240000, 7.240000, 6.000000, 4.000000),
      h   = c(4.760000, 2.580000, 2.580000, 4.760000, 2.580000, 2.580000, 6.000000, 4.000000),
      w   = c(243.0000, 110.0000, 110.0000, 243.0000, 110.0000, 110.0000, 235.0000, 258.0000)
    )

    knitr::kable(it)

oid | sku | l | d | h | w
--- | --- | --- | --- | --- | ---
1428571 | A0A0A0 | 2.14 | 3.58 | 4.76 | 243
1428571 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110
1428571 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110
1428572 | A0A0A0 | 2.14 | 3.58 | 4.76 | 243
1428572 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110
1428572 | A0A0A1 | 7.24 | 7.24 | 2.58 | 110
1428572 | A0A0A2 | 6.00 | 6.00 | 6.00 | 235
1428572 | A0A0A3 | 4.00 | 4.00 | 4.00 | 258

    #- bn
    #  bn bins <data.table>
    #  - id bn id <character>
    #  - l: bn length limit along x-coordinate <numeric>
    #  - d: bn depth  limit along y-coordinate <numeric>
    #  - h: bn height limit along z-coordinate <numeric>
    #  - w: bn weight limit along w - a separate single dimension <numeric>
    #  - l, d, h will be sorted to have l >= d >= h within solver
    # bin must be ordered by preference such that the first bin is most preferred one.

    bn <- data.table::data.table(
      id = c("K0001", "K0002", "K0003", "K0004", "K0005"),
      l  = c(06.0000, 10.0000, 09.0000, 10.0000, 22.0000),
      d  = c(06.0000, 08.0000, 08.0000, 10.0000, 14.0000),
      h  = c(06.0000, 06.0000, 07.0000, 10.0000, 09.0000),
      w  = c(600.000, 600.000, 800.000, 800.000, 800.000)
    )

    knitr::kable(bn)

id | l | d | h | w
--- | --- | --- | --- | ---
K0001 | 6 | 6 | 6 | 600
K0002 | 10 | 8 | 6 | 600
K0003 | 9 | 8 | 7 | 800
K0004 | 10 | 10 | 10 | 800
K0005 | 22 | 14 | 9 | 800

# gbp package design

## R-level class, solver and viewer

### solver

The function gbp::bpp_solver(it, bn) aims to pack each order into the smallest number of bins, and then smallest bins to achieve highest utlization rate, subject to the three dimensional none overlap contraints and weight limit constraint.

    #- bpp_solver: output: packing solution

    #- sn
    #  sn bpp_solution packing solution <list>
    #  - it item <data.table>
    #    - oid: order id <integer>
    #    - sku: stock keeping unit as it id <character>
    #    - tid: ticket id - an unique id within oid <integer>
    #    - otid: order id x ticket id - an unique indentifier indicate it with same tid can be packed into one bin <character>
    #    - bid: bn id <integer>
    #    - x, y, z it position in bid bin <numeric>
    #    - l, d, h it scale along x, y, z <numeric>
    #    - w it weight <numeric>
    #  - bn bins <data.table>
    #    - id bn id <character>
    #    - l bn length limit along x-coordinate <numeric>
    #    - d bn depth  limit along y-coordinate <numeric>
    #    - h bn height limit along z-coordinate <numeric>
    #    - w bn weight limit along w - a separate single dimension <numeric>
    sn <- gbp::bpp_solver(it = it, bn = bn)

    ## bpp_solver_dpp: processing order id: 1428571 on index: 0 - 2 ..
    ## bpp_solver_dpp: processing order id: 1428572 on index: 3 - 7 ..

    sn$it

    ##        oid tid      otid   bid    sku    x    y    z    l    d    h   w
    ## 1: 1428571   1 1428571X1 K0002 A0A0A0 7.24 0.00 0.00 2.14 3.58 4.76 243
    ## 2: 1428571   1 1428571X1 K0002 A0A0A1 0.00 0.00 2.58 7.24 7.24 2.58 110
    ## 3: 1428571   1 1428571X1 K0002 A0A0A1 0.00 0.00 0.00 7.24 7.24 2.58 110
    ## 4: 1428572   2 1428572X2 K0001 A0A0A0 0.00 0.00 0.00 3.58 2.14 4.76 243
    ## 5: 1428572   1 1428572X1 K0004 A0A0A1 0.00 0.00 2.58 7.24 2.58 7.24 110
    ## 6: 1428572   1 1428572X1 K0004 A0A0A1 0.00 0.00 0.00 7.24 7.24 2.58 110
    ## 7: 1428572   1 1428572X1 K0004 A0A0A2 0.00 2.58 2.58 6.00 6.00 6.00 235
    ## 8: 1428572   1 1428572X1 K0004 A0A0A3 6.00 2.58 2.58 4.00 4.00 4.00 258

    sn$bn

    ##       id  l  d  h   w
    ## 1: K0001  6  6  6 600
    ## 2: K0002 10  8  6 600
    ## 3: K0003  9  8  7 800
    ## 4: K0004 10 10 10 800
    ## 5: K0005 22 14  9 800

The packing solution is revealed in the data.table sn[[“it”]]. The packing solution table includes 12 columns: the order id (oid), the stock keeping unit (sku), the ticket id (tid) which identify items should be packed into the same bin, the order ticket id (otid) which is a unique identifier accross all orders, the bin id (bid) which identify the bin type associated with the ticket, the coordinates within the bin x, y, z, and the item’s length (l), depth (d), height (h) and weight (w). The solution can be viewed using gbp::bpp_viewer(sn).

### viewer

    #- bpp_viewer: a packing solution viewer
    #   requires rgl, run in r-console will create interactive 3d views in rgl window
    # bpp_viewer(sn)

The function bpp_solver is fast. I applied a simpler version of bpp_solver when designing and optimizing the set of boxes used in Jet.com’s warehouses. Back then, Jet.com receives 15,000 - 20,000 orders everyday, and 1 - 100 items in each order. The bpp_solver can pack all orders in 2 minutes - 5 minutes. The solution quality is also high. We formulated a mixed integer linear programming algorithm to find global optimial solution, using the bpp_solver solution as initial search point. We observed that bpp_solver solution is often equivalent or very close to the global optimial solution - often within 1% - 2% of utilization rate difference. One particular case to note is that the utilization rate difference could be as high as 4% - 5% when bpp_solver solution requires exact 2 bins. This is a consequence of the greedy algorithm. At last, the bpp_solver is 300x faster than the mixed integer linear programming.

## C-level class, solver and viewer

The design flow of c-level classes, solvers and viewers are straightforward. The gbp1d, gbp2d, gbp3d, and gbp4d are classes defined at each dimension, an instance of such class holds a feasible bin packing solution in corresponding dimension. The gbp1d_solver_dpp, gbp2d_solver_dpp, gbp3d_solver_dpp, and gbp4d_solver_dpp are solvers designed to solve corresponding problem, and return an instance of corresponding class. The gbp2d_checkr, gbp3d_checkr, and gbp4d_checkr are checkers designed to verify a solution is feasible. And, the gbp2d_viewer, gbp3d_viewer, and gbp4d_viewer are viewers designed to visualize a solution.

### gbp4d

The 4d scenairo contains two classes gbp4d and gbp4q, and two solvers gbp4d_solver_dpp and gbp4d_solver_dpp_filt.

The two solvers implement an extreme point based best fit first recursive algorithm. At each step an item is fit into all pontential positions with all possible orientation, and a fit schema is scored by entropy of the extreme points segmented residual space. The fit schema with lowest entropy score will be selected for recursive calls. The recursive is a limited rescursive fit on last few high profitable items, number of recursive call is gradually increasing toward the end of fit sequence. The idea is that last few items often small, moving them around can help finding feasible solutions.

#### single bin

The function gbp4d_solver_dpp(p, ldhw, m) aims to solve four dimensional bin packing (three dimensional none overlapping with weight limit) with repect to packing into a single bin. The inputs are the profit vector p which is a numeric vector defines the item’s packing sequence, highest profit first pack, the item’s characterization matrix (ldhw) which is a 4 x N numeric matrix with each column corresponding to an item’s length, depth, height and weight, and the bin’s characterization vector (m) which is a 4 x 1 numeric vector corresponding to bin’s length, depth, height and weight limit. The objective is fit as much item volume as possible into the bin. The solution resturned is an instance of gbp4d class.

##### solver

    #- gbp4d

    #- ldhw: item l, d, h, w in matrix
    ldhw <- t(as.matrix(it[oid == 1428572L, .(l, d, h, w)]))
    ldhw

    ##     [,1]   [,2]   [,3] [,4] [,5]
    ## l   2.14   7.24   7.24    6    4
    ## d   3.58   7.24   7.24    6    4
    ## h   4.76   2.58   2.58    6    4
    ## w 243.00 110.00 110.00  235  258

    #- m: bin l, d, h in matrix
    m <- t(as.matrix(bn[ , .(l, d, h, w)])) # multple bin
    m

    ##   [,1] [,2] [,3] [,4] [,5]
    ## l    6   10    9   10   22
    ## d    6    8    8   10   14
    ## h    6    6    7   10    9
    ## w  600  600  800  800  800

    #- p: item fit sequence w.r.t bin
    p <- gbp4d_solver_dpp_prep_create_p(ldhw, m[, 4L]) # single bin
    p

    ##      [,1]
    ## [1,]    0
    ## [2,]    3
    ## [3,]    4
    ## [4,]    2
    ## [5,]    1

    #- sn
    sn4d <- gbp4d_solver_dpp(p, ldhw, m[, 4L])

    sn4d$it # matrix of items x, y, z, w (weight bn is holding when fit it into bn), l, d, h, w (weight of it itself) (x, y, z, w set into -1 when item not fit into bin)

    ##        [,1]   [,2]   [,3]   [,4]   [,5]
    ## [1,]  -1.00   0.00   0.00   0.00   6.00
    ## [2,]  -1.00   0.00   0.00   2.58   2.58
    ## [3,]  -1.00   2.58   0.00   2.58   2.58
    ## [4,]  -1.00 110.00   0.00 220.00 455.00
    ## [5,]   2.14   7.24   7.24   6.00   4.00
    ## [6,]   4.76   2.58   7.24   6.00   4.00
    ## [7,]   3.58   7.24   2.58   6.00   4.00
    ## [8,] 243.00 110.00 110.00 235.00 258.00

    sn4d$k  # indicator of which items are fitted into bin

    ##      [,1]
    ## [1,]    0
    ## [2,]    1
    ## [3,]    1
    ## [4,]    1
    ## [5,]    1

    sn4d$bn # matrix of bins l, d, h, w (weight limit)

    ##      [,1]
    ## [1,]   10
    ## [2,]   10
    ## [3,]   10
    ## [4,]  800

    sn4d$o  # volume of items fitted into bin

    ## [1] 550.4748

    sn4d$ok # indicator of whether all items are fitted into bin

    ## [1] FALSE

##### checkr

    gbp4d_checkr(sn4d) #- check: no overlap in 3d volume and no over weight limit

    ## [1] TRUE

##### viewer

    # gbp4d_viewer(sn4d)

#### multiple bins

The function gbp4d_solver_dpp_filt(ldhw, m) aims to solve four dimensional bin packing (three dimensional none overlapping with weight limit) with repect to packing into a multiple bins. The input bin’s characterization vector (m) is a 4 x M numeric vector with each column corresponding to one bin’s length, depth, height and weight limit. The objective is fit as much item volume as possible into the bin, and select the bin with smaller index when two bin’s can fit the same volume. The solution resturned is an instance of gbp4q class.

##### solver

    #- gbp4q

    sn4q <- gbp4d_solver_dpp_filt(ldhw, m) # multiple bins, no fit sequence p
    # p is determined w.r.t each bin using algorithm in gbp4d_solver_dpp_prep_create_p

    sn4q$it # matrix of items x, y, z, w (weight bn is holding when fit it into bn), l, d, h, w (weight of it itself) (x, y, z, w set into -1 when item not fit into bin)

    ##        [,1]   [,2]   [,3]   [,4]   [,5]
    ## [1,]  -1.00   0.00   0.00   0.00   6.00
    ## [2,]  -1.00   0.00   0.00   2.58   2.58
    ## [3,]  -1.00   2.58   0.00   2.58   2.58
    ## [4,]  -1.00 110.00   0.00 220.00 455.00
    ## [5,]   2.14   7.24   7.24   6.00   4.00
    ## [6,]   4.76   2.58   7.24   6.00   4.00
    ## [7,]   3.58   7.24   2.58   6.00   4.00
    ## [8,] 243.00 110.00 110.00 235.00 258.00

    sn4q$k  # indicator of which items are fitted into bin

    ##      [,1]
    ## [1,]    0
    ## [2,]    1
    ## [3,]    1
    ## [4,]    1
    ## [5,]    1

    sn4q$bn # matrix of bins l, d, h, w (weight limit)

    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,]    6   10    9   10   22
    ## [2,]    6    8    8   10   14
    ## [3,]    6    6    7   10    9
    ## [4,]  600  600  800  800  800

    sn4q$f  # indicator of which bin is selected

    ##      [,1]
    ## [1,]    0
    ## [2,]    0
    ## [3,]    0
    ## [4,]    1
    ## [5,]    0

    sn4q$o  # volume of items fitted into bin

    ## [1] 550.4748

    sn4q$ok # indicator of whether all items are fitted into bin

    ## [1] FALSE

##### checkr

    gbp4q_checkr(sn4q) #- check: no overlap in 3d volume and no over weight limit

    ## [1] TRUE

##### viewer

    # gbp4q_viewer(sn4q)

## gbp3d

The 3d scenairo contains two classes gbp3d and gbp3q, and two solvers gbp3d_solver_dpp and gbp3d_solver_dpp_filt.

#### single bin

The function gbp3d_solver_dpp(p, ldh, m) aims to solve three dimensional bin packing with repect to packing into a single bin. The inputs are the profit vector p which is a numeric vector defines the item’s packing sequence, highest profit first pack, the item’s characterization matrix (ldh) which is a 3 x N numeric matrix with each column corresponding to an item’s length, depth, and height, and the bin’s characterization vector (m) which is a 3 x 1 numeric vector corresponding to bin’s length, depth, and height. The objective is fit as much item volume as possible into the bin, and the solution resturned is an instance of gbp3d class.

##### solver

    #- gbp3d

    sn3d <- gbp3d_solver_dpp(p, ldhw[1L:3L, ], m[, 4L])

    sn3d$it # matrix of items x, y, z, l, d, h (x, y, z set into -1 when item not fit into bin)

    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,] 6.00 0.00 0.00 0.00 6.00
    ## [2,] 6.58 0.00 0.00 2.58 2.58
    ## [3,] 2.58 2.58 0.00 2.58 2.58
    ## [4,] 3.58 7.24 7.24 6.00 4.00
    ## [5,] 2.14 2.58 7.24 6.00 4.00
    ## [6,] 4.76 7.24 2.58 6.00 4.00

    sn3d$k  # indicator of which items are fitted into bin

    ##      [,1]
    ## [1,]    1
    ## [2,]    1
    ## [3,]    1
    ## [4,]    1
    ## [5,]    1

    sn3d$bn # matrix of bins l, d, h

    ##      [,1]
    ## [1,]   10
    ## [2,]   10
    ## [3,]   10
    ## [4,]  800

    sn3d$o  # volume of items fitted into bin

    ## [1] 586.9421

    sn3d$ok # indicator of whether all items are fitted into bin

    ## [1] TRUE

#### checkr

    gbp3d_checkr(sn3d) #- check: no overlap in 3d volume

    ## [1] TRUE

#### viewer

    # gbp3d_viewer(sn3d)

#### multiple bins

The function gbp3d_solver_dpp_filt(ldh, m) aims to solve three dimensional bin packing with repect to packing into a multiple bins. The input bin’s characterization vector (m) is a 3 x M numeric vector with each column corresponding to one bin’s length, depth, and height. The objective is fit as much item volume as possible into the bin, and select the bin with smaller index when two bin’s can fit the same volume. The solution resturned is an instance of gbp3q class.

##### solver

    #- gbp3q

    sn3q <- gbp3d_solver_dpp_filt(ldhw[1L:3L, ], m) # multiple bins, no fit sequence p
    # p is determined w.r.t each bin using algorithm in gbp3d_solver_dpp_prep_create_p

    sn3q$it # matrix of items x, y, z, l, d, h (x, y, z set into -1 when item not fit into bin)

    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,] 6.00 0.00 0.00 0.00 6.00
    ## [2,] 2.58 0.00 0.00 2.58 4.72
    ## [3,] 2.58 2.58 0.00 2.58 2.58
    ## [4,] 3.58 7.24 7.24 6.00 4.00
    ## [5,] 2.14 2.58 7.24 6.00 4.00
    ## [6,] 4.76 7.24 2.58 6.00 4.00

    sn3q$k  # indicator of which items are fitted into bin

    ##      [,1]
    ## [1,]    1
    ## [2,]    1
    ## [3,]    1
    ## [4,]    1
    ## [5,]    1

    sn3q$bn # matrix of bins l, d, h

    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,]    6   10    9   10   22
    ## [2,]    6    8    8   10   14
    ## [3,]    6    6    7   10    9
    ## [4,]  600  600  800  800  800

    sn3q$f  # indicator of which bin is selected

    ##      [,1]
    ## [1,]    0
    ## [2,]    0
    ## [3,]    0
    ## [4,]    1
    ## [5,]    0

    sn3q$o  # volume of items fitted into bin

    ## [1] 586.9421

    sn3q$ok # indicator of whether all items are fitted into bin

    ## [1] TRUE

##### checkr

    gbp3q_checkr(sn3q) #- check: no overlap in 3d volume

    ## [1] TRUE

##### viewer

    # gbp3q_viewer(sn3q)

### gbp2d

The 2d scenairo contains two classes gbp2d and gbp2q, and two solvers gbp2d_solver_dpp and gbp2d_solver_dpp_filt.

#### single bin

The function gbp2d_solver_dpp(p, ld, m) aims to solve two dimensional bin packing with repect to packing into a single bin. The inputs are the profit vector p which is a numeric vector defines the item’s packing sequence, highest profit first pack, the item’s characterization matrix (ld) which is a 2 x N numeric matrix with each column corresponding to an item’s length and depth, and the bin’s characterization vector (m) which is a 2 x 1 numeric vector corresponding to bin’s length and depth. The objective is fit as much item volume as possible into the bin, and the solution resturned is an instance of gbp2d class.

##### solver

    #- gbp2d

    sn2d <- gbp2d_solver_dpp(p, ldhw[1L:2L, ], m[, 4L])

    sn2d$it # matrix of items x, y, l, d (x, y set into -1 when item not fit into bin)

    ##      [,1]  [,2] [,3] [,4] [,5]
    ## [1,] 7.24 -1.00 0.00   -1   -1
    ## [2,] 0.00 -1.00 0.00   -1   -1
    ## [3,] 2.14  7.24 7.24    6    4
    ## [4,] 3.58  7.24 7.24    6    4

    sn2d$k  # indicator of which items are fitted into bin

    ##      [,1]
    ## [1,]    1
    ## [2,]    0
    ## [3,]    1
    ## [4,]    0
    ## [5,]    0

    sn2d$bn # matrix of bins l, d

    ##      [,1]
    ## [1,]   10
    ## [2,]   10
    ## [3,]   10
    ## [4,]  800

    sn2d$o  # volume of items fitted into bin

    ## [1] 60.0788

    sn2d$ok # indicator of whether all items are fitted into bin

    ## [1] FALSE

##### checkr

    gbp2d_checkr(sn2d) #- check: no overlap in 2d area

    ## [1] TRUE

##### viewer

    # gbp2d_viewer(sn2d) #- view on XZ surface and set Y into 1 to give stereo perception

#### multiple bins

The function gbp2d_solver_dpp_filt(ld, m) aims to solve two dimensional bin packing with repect to packing into a multiple bins. The input bin’s characterization vector (m) is a 2 x M numeric vector with each column corresponding to one bin’s length and depth. The objective is fit as much item volume as possible into the bin, and select the bin with smaller index when two bin’s can fit the same volume. The solution resturned is an instance of gbp2q class.

##### solver

    #- gbp2q

    sn2q <- gbp2d_solver_dpp_filt(ldhw[1L:2L, ], m) # multiple bins, no fit sequence p
    # p is determined w.r.t each bin using algorithm in gbp2d_solver_dpp_prep_create_p

    sn2q$it # matrix of items x, y, l, d (x, y set into -1 when item not fit into bin)

    ##       [,1] [,2] [,3]  [,4]  [,5]
    ## [1,] 18.48 7.24 0.00 14.48 14.48
    ## [2,]  6.00 0.00 0.00  0.00  6.00
    ## [3,]  2.14 7.24 7.24  6.00  4.00
    ## [4,]  3.58 7.24 7.24  6.00  4.00

    sn2q$k  # indicator of which items are fitted into bin

    ##      [,1]
    ## [1,]    1
    ## [2,]    1
    ## [3,]    1
    ## [4,]    1
    ## [5,]    1

    sn2q$bn # matrix of bins l, d

    ##      [,1] [,2] [,3] [,4] [,5]
    ## [1,]    6   10    9   10   22
    ## [2,]    6    8    8   10   14
    ## [3,]    6    6    7   10    9
    ## [4,]  600  600  800  800  800

    sn2q$f  # indicator of which bin is selected

    ##      [,1]
    ## [1,]    0
    ## [2,]    0
    ## [3,]    0
    ## [4,]    0
    ## [5,]    1

    sn2q$o  # volume of items fitted into bin

    ## [1] 164.4964

    sn2q$ok # indicator of whether all items are fitted into bin

    ## [1] TRUE

##### checkr

    gbp2q_checkr(sn2q) #- check: no overlap in 2d area

    ## [1] TRUE

##### viewer

    # gbp2q_viewer(sn2q)

### gbp1d

The 1d scenairo contains a single solver gbp1d_solver_dpp, which aims to solve one dimensional bin packing problem, a.k.a Knapsack problem. In mathematical, gbp1d_solver_dpp(p, w, c) will: maximize \(\sum_{j=1}^{n} p_j x_j\), subject to \(\sum_{j=1}^{n} w_j x_j \leq c, x_j \in \{0, 1\}, j = 1, ...., n\), where p is a numeric vector of each item’s profit, w is an integer vector of each item’s weight, c is an integer scalar of the total weight limit.

The function gbp1d_solver_dpp(p, w, c) implements a dynamic programming solution, and return an instance of gbp1d class. A gbp1d class instance would have 6 member fields: the profit vector p, the weight vector w, the weight constraint c, the selection vector k which is a boolean vector indicates whether or not an item is selected in the solution, the objective value o which is the sum of the weight of the items selected, and the boolean indicator ok indicates whether or not all items are selected.

    #- gbp1d

    v <- apply(ldhw[1L:3L, ], 2L, prod)

    sn1d <- gbp1d_solver_dpp(p = v, w = ldhw[4L, ], c = 714.28)

    sn1d$p # vector of items profit

    ##           [,1]
    ## [1,]  36.46731
    ## [2,] 135.23741
    ## [3,] 135.23741
    ## [4,] 216.00000
    ## [5,]  64.00000

    sn1d$w # vector of items weight

    ##      [,1]
    ## [1,]  243
    ## [2,]  110
    ## [3,]  110
    ## [4,]  235
    ## [5,]  258

    sn1d$c # weight limit constraint

    ## [1] 714

    sn1d$k  # indicator of which items are selected

    ##      [,1]
    ## [1,]    0
    ## [2,]    1
    ## [3,]    1
    ## [4,]    1
    ## [5,]    1

    sn1d$o  # weight of items selected

    ## [1] 550.4748

    sn1d$ok # indicator of whether all items are selected

    ## [1] FALSE

# Some practical examples

## gbp: a bin packing problem solver

A shiny application that demonstrates how to use gbp function bpp_solver in fulfilling the order packing process in business operations.