Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 analyst41@hotmail.com Posts: 107 Registered: 4/27/05
Re: non-discrete knapsack
Posted: Oct 28, 2010 5:29 PM

On Oct 28, 3:05 pm, Paul <paul_ru...@att.net> wrote:
> On Oct 28, 12:54 pm, "analys...@hotmail.com" <analys...@hotmail.com>
> wrote:
>
>
>
>
>

> > On Oct 28, 10:55 am, Paul <paul_ru...@att.net> wrote:
>
> > > On Oct 27, 12:13 pm, Ray Vickson <RGVick...@shaw.ca> wrote:
>
> > > > The OP is correct: here is a LINGO11 file for his problem (of course,
> > > > manual solution via simplex would be straightforward):

>
> > > >   MODEL:
> > > >    [1] MAX= 2 * X + 3 * Y ;
> > > >    [INEQ] 4 * X + 5 * Y <= 23 ;
> > > >    [EQ] X + Y = 5 ;
> > > >   END

>
> > > >   Global optimal solution found.
> > > >   Objective value:                              13.00000
> > > >   Infeasibilities:                              0.000000
> > > >   Total solver iterations:                             2

>
> > > >                        Variable           Value        Reduced Cost
> > > >                               X        2.000000            0.000000
> > > >                               Y        3.000000            0.000000

>
> > > >                             Row    Slack or Surplus      Dual Price
> > > >                               1        13.00000            1.000000
> > > >                            INEQ        0.000000            1.000000
> > > >                              EQ        0.000000           -2.000000

>
> > > > The point (x,y) = (2,3) is, indeed, the unique optimal solution. (The
> > > > point (0,23/5) does not satisfy the equality constraint). So, the OP's
> > > > question is a valid one, but it also seems to violate _standard
> > > > methods_ in mathematical progamming! Right now I can't see where the
> > > > problem lies.

>
> > > > R.G. Vickson
>
> > > My bad.  Apologies to the OP.  I read the second constraint as an
> > > inequality (<=).  Remind me to use a bigger font in my browser.  :-(

>
> > > You're right, though, that this seems to contradict well known
> > > results.  I'll have to take a closer look too.

>
> > > /Paul- Hide quoted text -
>
> > > - Show quoted text -
>
> > could it be because the inequality has two dimensions and the equality
> > constraint has reduced the dimensions of the problem?

>
> At least part of the problem is that the relaxation of the second
> constraint is incorrect.  Given that it is an equality, you need to
> relax it by penalizing the absolute value of its deviation in the
> objective (or the squared difference).  You probably don't want a
> quadratic objective if you are looking for a simple algorithm, and the
> absolute value function cannot be used directly.  The usual LP kludge
> to get rid of the absolute value leads you to something like this:
>
> Max 2x+3y + lambda(s + t)
>  st
>
>  4x + 5y <= 23
> x + y + s - t = 5
>  x,y,s,t >= 0
>
> But now you're back with two constraints, so we haven't really
> accomplished anything.  (For the record, though, if lambda > 2 the
> optimal solution to this problem is indeed x = 2, y = 3; so Ray and I
> can sleep securely tonight.)
>
> I'll have to rethink the approach I originally had in mind to see if
> it works any better than the penalty function.
>
> /Paul- Hide quoted text -
>
> - Show quoted text -

What if we made the equality the main constraint and put the
inequality in the Lagrangean?

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