[Caml-list] Linear programming

[Caml-list] Linear programming

[Alessandro Baretta]

I am coding the algorithm for the cut-stock problem discussed in
http://www.informatik.uni-osnabrueck.de/papers_html/or_94/cutpaper.html

This algorithm iteratively uses discrete linear programming. 
I would like to avoid coding an LP or, worse yet, a DLP 
library in Ocaml.

Does anyone know if and where I could find a prepackaged LP 
library written in Ocaml or linkable with Ocaml? I have 
found the GNU Linear Programming Kit. Has anybody written a 
stubs library for it?

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

Re: [Caml-list] Linear programming

[Chris Hecker]

>Does anyone know if and where I could find a prepackaged LP library 
>written in Ocaml or linkable with Ocaml? I have found the GNU Linear 
>Programming Kit. Has anybody written a stubs library for it?

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.

Let me know,
Chris


-------------------
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

Re: [Caml-list] Linear programming

[Alessandro Baretta]

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