[Camllist] Linear programming

Alessandro Baretta

Chris Hecker
 Alessandro Baretta

Chris Hecker
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20030223 (21:19) 
From:  Alessandro Baretta <alex@b...> 
Subject:  Re: [Camllist] Linear programming 
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 optimalityfinding the exact solution to the cuts stock problems is NPhard. Alex  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners