[Date Index] [Thread Index] [Author Index]

Re: How big a problem can ConstrainedMax handle?

• To: mathgroup at smc.vnet.net
• Subject: [mg31426] Re: How big a problem can ConstrainedMax handle?
• From: "Borut L" <borut at email.si>
• Date: Sat, 3 Nov 2001 18:25:03 -0500 (EST)
• References: <9rodc2$psp$1@smc.vnet.net> <9rqvjm$jis$1@smc.vnet.net> <9s0h7g$n66$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

"David Eppstein" <eppstein at ics.uci.edu> wrote in message
news:9s0h7g$n66$1 at smc.vnet.net...
> In article <9rqvjm$jis$1 at smc.vnet.net>, "Borut L" <borut at email.si> wrote:
>
> > My experience is that the ConstrainedMax is very handy and stylish, not
> > having to type in the constraints in a conventional tableau form. The
> > problem is basically number crunching in my opinion, so I used SIMPLX
> > (simplex) algorithm from Numerical Recipes, being very satisfied with
its
> > limitness and high speed.
>
> Ok, but I specifically want an exact rational result, so numerical
routines
> are no good unless they are reimplemented in exact rationals.
>
> Anyway, I've heard from the Mathematica folks that ConstrainedMax is a
> primal simplex using a dense representation, so may not be optimal for my
> problem (sparse and with many more constraints than variables).  But in
the
> absense of better alternatives I'm likely to try it anyway.
> --
> David Eppstein       UC Irvine Dept. of Information & Computer Science
> eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/


I recommend Mathematica if you want a rational result.

Simplex algorithm is the method of choice because finding an optimal
feasible vector in linear programming is a tough problem and the simplex
does it in an easy way.
I think every LP implementation uses it.

Hey, btw: I've seen an article about LP and simplex method in an old
Mathematica Journal. It was well written and nicely visualized (simplex
cell). You can find it through volume indices.