mknapsack: Multiple 0-1 Knapsack Problem In adagio: Discrete and Global Optimization Routines

Description

Solves the 0-1 (binary) multiple knapsack problem.

Usage

 `1` ```mknapsack(p, w, k, bck = -1) ```

Arguments

 `p` integer vector of profits. `w` integer vector of weights. `k` integer vector of capacities of the knapsacks. `bck` maximal number of backtrackings allowed; default: -1.

Details

Solves the 0-1 multiple knapsack problem for integer profits and weights

A multiple 0-1 knapsack problem can be formulated as:

``` maximize vstar = p(1)*(x(1,1) + ... + x(m,1)) + ... ... + p(n)*(x(1,n) + ... + x(m,n)) subject to w(1)*x(i,1) + ... + w(n)*x(i,n) <= k(i) for i=1,...,m x(1,j) + ... + x(m,j) <= 1 for j=1,...,n x(i,j) = 0 or 1 for i=1,...,m , j=1,...,n , ```

The input problem description must satisfy the following conditions:

• `vs=-1` if n < 2 or m < 1

• `vs=-2` if some p(j) , w(j) or k(i) are not positive

• `vs=-3` if a knapsack cannot contain any item

• `vs=-4` if an item cannot fit into any knapsack

• `vs=-5` if knapsack m contains all the items

• `vs=-7` if array k is not correctly sorted

• `vs=-8` [should not happen]

Value

A list with compomnents, `ksack` the knapsack numbers the items are assigned to, `value` the total value/profit of the solution found, and `bs` the number of backtracks used.

Note

With some care, this function can be used for the bounded and unbounded single knapsack problem as well.

Author(s)

The Fortran source code is adapted from the free NSCW Library of Mathematical Subroutines.

The wrapping code has been written by yours package maintainer,
HwB email: <[email protected]>

References

Kellerer, H., U. Pferschy, and D. Pisinger (2004). Knapsack Problems. Springer-Verlag, Berlin Heidelberg.

Martello, S., and P. Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Ltd.

Other packages implementing knapsack routines.

Examples

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32``` ```## Example 1: single knapsack p <- c(15, 100, 90, 60, 40, 15, 10, 1) w <- c( 2, 20, 20, 30, 40, 30, 60, 10) cap <- 102 (is <- mknapsack(p, w, cap)) which(is\$ksack == 1) # [1] 1 2 3 4 6 , capacity 102 and total profit 280 ## Example 2: multiple knapsack p <- c(110, 150, 70, 80, 30, 5) w <- c( 40, 60, 30, 40, 20, 5) k <- c(65, 85) is <- mknapsack(p, w, k) # kps 1: 2,6; kps 2: 1,4; value: 345; backtracks: 14 ## Example 3: multiple knapsack p <- c(78, 35, 89, 36, 94, 75, 74, 79, 80, 16) w <- c(18, 9, 23, 20, 59, 61, 70, 75, 76, 30) k <- c(103, 156) is <- mknapsack(p, w, k) # kps 1: 1,3,6; kps 2: 4,5,9; value: 452; backtracks: 4 ## Example 4: subset sum p <- seq(2, 44, by = 2)^2 w <- p is <- mknapsack(p, w, 2012) sum((2 * which(is\$ksack == 1))^2) ## Example 5: maximize number of items w <- seq(2, 44, by = 2)^2 p <- numeric(22) + 1 is <- mknapsack(p, w, 2012) ```

Example output

```\$ksack
[1] 1 1 1 1 0 1 0 0

\$value
[1] 280

\$btracks
[1] 0

[1] 1 2 3 4 6
[1] 2012
```

adagio documentation built on May 29, 2017, 10:29 p.m.