The Multi-dimensional Knapsack Problem

(MKP) over n decision variables xj = 1 is object j is chosen and = 0 otherwise, can be formulated:

max a n

j = 1rjxj (maximize total return)

s.t. a n

j = 1aijxj … bi i = 1,

c, m (capacities i)

xj binary j = 1,

c, n

(a) Develop and justify an expression for the length of a binary encoding for an instance in terms of the dimensions and parameters of the model.

(b) Explain why the (BKP) instance in Exercise 14-1 is an instance of (MKP).

(c) State the threshold version 1MKPÚ2 of (MKP) for given threshold v, and establish that it belongs to complexity class NP.

(d) The threshold version 1BKPÚ2 of the Binary Knapsack Problem treated in Exercise 14-2 is known to be NPComplete.

Use that fact along with part

(c) to establish that 1MKPÚ2 is also NP-Complete. Be sure to fully detail the required reduction among instances of the two problems.

(e) Explain what the result of

(d) implies for the prospects of finding a polynomial time (binary encoding) algorithm for either 1MKPÚ2 or the full optimization version (MKP), and why.