Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: non-discrete knapsack
Replies: 22   Last Post: Dec 24, 2010 6:47 PM

 Messages: [ Previous | Next ]
 analyst41@hotmail.com Posts: 139 Registered: 4/27/05
Re: non-discrete 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 weight-capacity 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 one-dimensional 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)

Date Subject Author
10/23/10 analyst41@hotmail.com
10/24/10 Paul
10/24/10 RGVickson@shaw.ca
10/24/10 Paul
10/25/10 analyst41@hotmail.com
10/26/10 Paul
10/26/10 analyst41@hotmail.com
10/27/10 Paul
10/27/10 RGVickson@shaw.ca
10/28/10 Paul
10/28/10 analyst41@hotmail.com
10/28/10 Paul
10/28/10 analyst41@hotmail.com
10/28/10 Paul
10/27/10 analyst41@hotmail.com
11/3/10 Paul
11/10/10 Paul
11/13/10 analyst41@hotmail.com
12/13/10 analyst41@hotmail.com
12/14/10 Paul
12/24/10 analyst41@hotmail.com