Re: [Caml-list] Linear programming

[Alessandro Baretta <alex@baretta.com>]

Chris Hecker wrote:

> Is this for large scale production work with big sparse matrices, or 
> small dense problems?  I have an implementation of Lemke's algorithm I 
> wrote for solving dense Linear Complementarity Problems.  You can easily
> transform an LP into and LCP and solve it, but this isn't the most 
> efficient way.  So, if this is for "toy" problems (n < 100) then it'd 
> work fine on modern machines, but it won't work for you if you want 
> something totally optimal for huge systems, etc.  You're welcome to use 
> the code if you'd like.  Most paths are pretty well tested (it's called 
> every frame in my game).  It depends on my crappy linear algebra library 
> as well.

I'm not familiar with LCP, yet I'd say I can't afford the 
cost of translating from my binary linear programming 
problems to LCP, whatever it costs. Anyhow, here is some 
data concerning the actual use of the code. The algorithm 
for the cut stock problem uses iteratively a binary LP 
solver to build successive "generations" of partial 
solutions. The LP solver is called approximately log_2 (n) 
times. If a generation has size m, the size of the LP 
problem is about 0.5m^2, and each generation is a little 
over half the size of the former. The cardinality of the 
first generation can reach into the hundreds of elements, up 
to, say, a thousand. This would imply an associated integer 
LP problem of at most about a half million variables, with 
the size of successive calls decreasing approximately by a 
factor of 4.

This sounds pretty heavy to me, especially considering that 
the algorithm I'm coding is only a heuristic algorithm, with 
  no guarantee of optimality--finding the exact solution to 
the cuts stock problems is NP-hard.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners