Linear Multiple-Choice Knapsack Problems (LMCKP)

[Bob Bulfin]

Hi All,

I need a little help here. Consider the following linear
multiple-choice knapsack problem (LMCKP):

Max sum(i=1,m,j=1,n(i)) c(i,j)x(i,j)
st
sum(i=1,m,j=1,n(i)) a(i,j)x(i,j) <= b
sum(j=1,n(i)) x(i,j) <= 1 i=1,m
x(i,j) >= 0 i=1,m,j=1,n(i)

In Sinha & Zoltners, they state that, wlog, assume
a(i,j) >=0, c(i.j) >=0. If not, transformations can
put it in this form. Then they give an algorithm to
solve the problem with non-negative coefficients.

I know it is true for knapsack problems, if both
a and c are <0, let x=1-x; if c<0, a>0, set x=0
if c>0, a<0, set x=1.

The first 2 work for LMCKP, but I don't believe the
last one does. Seems it depends not only on ratios
in its own set, but also on ratios in other sets
and the value of b.

Am I missing an obvious transformation here. Anyone
know how to solve LMCKP with negative a(i,j)?

Thanks,

Bob

[Lutz Tautenhahn]

Hi Bob,
you are right:
If for all i, j c(i,j)>0 and a(i,j)<0, then
all x(i,j) should be set to 1, which would
violate the condition

sum(j=1,n(i)) x(i,j)<= 1 i=1,m

But there's a way to get rid of the negative
a values:
Assume there is an a(i,j)<0, c(i,j)>0
Then in the optimum solution there will be
sum(j=1,n(i)) x(i,j) = 1
(If there was sum(j=1,n(i)) x(i,j) = 0 then the
solution could be improved by setting x(i,j)=1)
Let be d(i)=Min{0, a(i,1), ..., a(i,n(i))} i=1,m
then you could transform
sum(i=1,m,j=1,n(i)) a(i,j)x(i,j) <= b
into
sum(i=1,m,j=1,n(i)) (a(i,j)+d(i))x(i,j) <= b+sum(i=1,m) d(i)
which has only non-negative coefficients.

Btw, it seems you have forgotten the constraint
x = {0, 1}
in your model. As you posed the problem, its a common LP.

Regards,
Lutz Tautenhahn

"Bob Bulfin" <bul...@eng.auburn.edu> schrieb im Newsbeitrag
news:3B78482A...@eng.auburn.edu...

[Lutz Tautenhahn]

This looks better:

sum(i=1,m,j=1,n(i)) (a(i,j)-d(i))x(i,j) <= b-sum(i=1,m) d(i)

Lutz.