
Re: nondiscrete knapsack
Posted:
Oct 26, 2010 8:09 PM


On Oct 26, 3:27 pm, Paul <paul_ru...@att.net> wrote: > On Oct 25, 7:17 pm, "analys...@hotmail.com" <analys...@hotmail.com> > wrote: > > > > > > > On Oct 24, 2:30 pm, Ray Vickson <RGVick...@shaw.ca> wrote: > > > > On Oct 23, 5:24 am, "analys...@hotmail.com" <analys...@hotmail.com> > > > wrote: > > > > > The knapsack without integer constraints can be solved very easily: > > > > > max sum over j v(j).x(j) > > > > > such that > > > > > sum over j w(j).x(j) <= B > > > > > 0 <= x(j) <= b(j) > > > > > (Sort in order of value/weight and allocate to the upper bound or > > > > until the weightcapacity is reached). > > > > > If we now add a second constraint > > > > > sum over j x(j) = C > > > > > It is still an LP and can be solved. > > > > > But is there a simpler way to get the solution without running the > > > > problem through an LP solver? > > > > > Thanks. > > > > As an alternative to Paul's suggestion, you could put the other > > > constraint up into the objective via a Lagrange multiplier u, then > > > have an ordinary knapsack problem with parameter u in its solution. > > > You can do a onedimensional search over u to find the appropriate u. > > > > F(u) = max_{x} sum_{j} v(j) * x(j) + u*[ C  sum_{j} x(j) ] > > > s.t. > > > sum_{j} w(j) * x(j) <= B, > > > 0 <= x(j) <= b(j) for j = 1,...,n. > > > > The overall solution is obtained from min_{u} F(u). Alternatively, > > > search over u until sum x(j;u) = C. > > > > R.G. Vickson Hide quoted text  > > > >  Show quoted text  > > > Thanks both. > > > I see a problem with this approach. > > > If you look at > > > Max 2x + 3y > > > st > > > 4x +5y <=23 > > x + y = 5 > > x,y>=0 > > > The unique optimum occurs at x = 2, y=3. > > > The Lagrangean formulation cannot "see" this point: > > > Max 2x+3y + lamda(5  x y) > > > st > > > 4x + 5y <= 23 > > x,y, >= 0 > > > For any value of lamda, this is an Lp with only three extreme points > > > (0,0) > > (23/4,0) > > ( 0,23/5) > > > So all the optima will occur at one of these points and no value of > > lamda can guide you to (2,3). > > > Am I missing something here? > > (2, 3) is not optimal in the original LP; (0, 23/5) is. (2, 3) is > optimal if you restrict x and y to integer values; but you indicated > you were solving a continuous knapsack (with an extra constraint). > > /Paul Hide quoted text  > >  Show quoted text 
only solving a continuous case.
(2,3) optimizes
Max 2x + 3y st 4x +5y <=23 x + y = 5 x,y>=0
(2,3) will never be found by the Lagrangean relaxation for any value of lamda
Max 2x+3y + lamda(5  x y)
st
4x + 5y <= 23 x,y, >= 0
Since, for each value of lamda the objective is linear and will optimize at one of
(0,0) (23/4,0) ( 0,23/5)

