|
|
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?
|
|
