This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Linear programming
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-02-23 (21:19) From: Alessandro Baretta Subject: Re: [Caml-list] 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 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

```