MathGroup Archive 1998

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

Search the Archive

Re: Re: LinearProgramming question (speed problem)

> >Can anyone help on how to use LinearProgramming for not-so-small
> >problems?
> >
> >I have a program with about 80 variables and about 120 constraints,
> >everything real.  This just sits for more than a day on every machine
> >I have tried it on.  (I have run Mathematica 2.2.2 on a PowerMac 8000,
> >and Mathematica 3.0 on a fast mainframe here.)
> >
> >The next smaller version, with 64 variables and 90 constraints, takes
> >just a few minutes on the mainframe.
> >
> >These are pretty small linear programs, so is there some memory limit I
> >need to raise, or a faster version of the LinearProgramming command?
> >
> If I were you, I would download a third party lp program like lp_solve
> and use Mathematica to produce the problem. Call the the lp program
> with Run[], if it works on your machine. I have used this to solve
> problems with "zillions" of variables using CPLEX ,  Mathematica
> providing the manipulation environment to create these problems,
> displaying the solution, etc. Have a look at :
> to choose your lp program.

Other suggestions are to try rearranging the constraints, or to try
changing the precision of the input.  It is likely that simply changing
the order of the constraints will fix the problem.

This is not a generic speed or memory problem.  The algorithm is
probably stuck, probably jumping back and forth between degenerate
solutions.  This sort of endless cycling is a common problem in linear
programming algorithms.  (If my memory is correct, I believe this issue
is mentioned briefly in Numerical Recipes, which also suggests
permuting the variables as a solution.)  I did a LinearProgramming
example just now on a modest 100 MHz Pentium machine and got an answer
in 45 seconds.  If your calculation doesn't finish in about that much
time, the algorithm is probably stuck.

There is also a discussion of this in the Wolfram Research web site

Dave Withoff
Wolfram Research

  • Prev by Date: Sqrt Problems
  • Next by Date: Re: BesselJZeros strangeness
  • Prev by thread: Re: LinearProgramming question (speed problem)
  • Next by thread: Front End Message