Re: Re: LinearProgramming question (speed problem)
- To: mathgroup@smc.vnet.net
- Subject: [mg12059] Re: [mg12016] Re: LinearProgramming question (speed problem)
- From: David Withoff <withoff@wolfram.com>
- Date: Fri, 24 Apr 1998 01:52:29 -0400
> >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 : > http://plato.la.asu.edu/guide.html 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 (http://www.wolfram.com/support/Kernel/Symbols/System/LinearProgramming.html). Dave Withoff Wolfram Research