mknapsack: Multiple 0-1 Knapsack Problem

In adagio: Discrete and Global Optimization Routines

Multiple 0-1 Knapsack Problem

Description

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

Usage

mknapsack(w, p, cap)

Arguments

w	vector of (positive) weights.
p	vector of (positive) profits.
cap	vector of capacities of different knapsacks.

Details

Solves the 0-1 multiple knapsack problem for a set of 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) <= cap(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 multiple knapsack problem is reformulated as a linear program and solved with the help of package lpSolve.

This function can be used for the single knapsack problem as well, but the 'dynamic programming' version in the knapsack function is faster (but: allows only integer values).

The solution found is most often not unique and may not be the most compact one. In the future, we will attempt to 'compactify' through backtracking. The number of backtracks will be returned in list element bs.

Value

A list with components, 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

Contrary to earlier versions, the sequence of profits and weights has been interchanged: first the weights, then profits.

The compiled version was transferred to the knapsack package on R-Forge (see project 'optimist').

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.

See Also

Other packages implementing knapsack routines.

Examples

## Example 1: single knapsack
w <- c( 2,  20, 20, 30, 40, 30, 60, 10)
p <- c(15, 100, 90, 60, 40, 15, 10,  1)
cap <- 102
(is <- mknapsack(w, p, cap))
which(is$ksack == 1)
# [1] 1 2 3 4 6 , capacity 102 and total profit 280

## Example 2: multiple knapsack
w <- c( 40,  60, 30, 40, 20, 5)
p <- c(110, 150, 70, 80, 30, 5)
cap <- c(85, 65)
is <- mknapsack(w, p, cap)
# kps 1: 1,4;  kps 2: 2,6;  value: 345

## 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)
cap <- c(103, 156)
is <- mknapsack(w, p, cap)
# kps 1: 3,4,5;  kps 2: 1,6,9; value: 452 

## Not run: 
# How to Cut Your Planks with R
# R-bloggers, Rasmus Baath, 2016-06-12
#
# This is application of multiple knapsacks to cutting planks into pieces.

planks_we_have <- c(120, 137, 220, 420, 480)
planks_we_want <- c(19, 19, 19, 19, 79, 79, 79, 103, 103,
                    103, 135, 135, 135, 135, 160)
s <- mknapsack(planks_we_want, planks_we_want + 1, planks_we_have)
s$ksack
##  [1] 5 5 5 5 3 5 5 4 1 5 4 5 3 2 4

# Solution w/o backtracking
# bin 1 :  103                          | Rest:  17
# bin 2 :  135                          | Rest:   2
# bin 3 :   79 +  135                   | Rest:   6
# bin 4 :  103 +  135 + 160             | Rest:  22
# bin 5 : 4*19 + 2*79 + 103 + 135       | Rest:   8
#
# Solution with reversing the bins (bigger ones first)
# bin 1 :  103                          | Rest:   4
# bin 2 :  2*19 +    79                 | Rest:  20
# bin 3 :   79  +   135                 | Rest:   6
# bin 4 : 2*19  +    79 + 135 + 160     | Rest:   8
# bin 5 : 2*103 + 2*135                 | Rest:  17
#
# Solution with backtracking (compactification)
# sol = c(1, 4, 4, 1, 1, 3, 4, 5, 5, 5, 5, 4, 2, 3, 4)
# bin 1 : 2*19 +   79                   | Rest:   3
# bin 2 :  135                          | Rest:   2
# bin 3 :   79 +  135                   | Rest:   6
# bin 4 : 2*19 +   79 + 135 + 160       | Rest:   8
# bin 5 : 3*103 + 135                   | Rest:  36

## End(Not run)

adagio documentation built on Oct. 26, 2023, 5:08 p.m.