From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA07257; Sun, 23 Feb 2003 22:19:15 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA07512 for ; Sun, 23 Feb 2003 22:19:14 +0100 (MET) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from athlon.baretta.com (host13-4.pool62211.interbusiness.it [62.211.4.13] (may be forged)) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h1NLJDT10275 for ; Sun, 23 Feb 2003 22:19:13 +0100 (MET) Received: from baretta.com (localhost.localdomain [127.0.0.1]) by athlon.baretta.com (Postfix) with ESMTP id 19EEB2739B; Sun, 23 Feb 2003 22:23:24 +0100 (CET) Message-ID: <3E593BCC.304@baretta.com> Date: Sun, 23 Feb 2003 22:23:24 +0100 From: Alessandro Baretta Organization: Baretta srl -- www.baretta.com User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.1) Gecko/20020826 X-Accept-Language: it, en MIME-Version: 1.0 To: Chris Hecker Cc: Ocaml Subject: Re: [Caml-list] Linear programming References: <4.3.2.7.2.20030223121117.02c6ae80@localhost> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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