From: Bob Silverman Subject: Re: karmarkar's method linear programming Date: Wed, 31 Jan 2001 15:56:18 GMT Newsgroups: sci.math Summary: Barrier (Karmarkar) methods of solving LP programs rapidly In article <20010130231805.18740.00000040@ng-fm1.aol.com>, ttopfun@aol.com (TTOP FUN) wrote: > anyone familiar with that solving method? Here is a rough outline of the method. Take a point in the interior. If you move directly toward the objective function (i.e. in the direction of its gradient) you will not, in general be moving toward the optima. But: Transform the problem as follows: Take a linear projective transform which maps the polytope to a (regular) simplex of dimension 1 more than the original polytope. This also maps the selected interior point to a new point. The map allows a degree of freedom, so we map the original point to the CENTER. Now, if you move in the direction of the gradient , you are moving toward the optimum. To see this: draw a triangle and an objective function. Select a point in the interior. Draw the orthogonal to the objective. You will see that you don't move toward the optimal vertex. Now do the same thing with an EQUILATERAL TRIANGLE with the point in the center.... The algorithm does a series of: transform, move in the direction of the optimum, transform back. Repeat. You have to be careful when you move the interior point so as not to go outside the polytope. There are a number of texts which discuss this and related "Interior Point" methods. -- Bob Silverman "You can lead a horse's ass to knowledge, but you can't make him think" Sent via Deja.com http://www.deja.com/ ============================================================================== From: borchers@rainbow.nmt.edu (Brian Borchers) Subject: Re: Karmarkar's method Date: Sat, 3 Feb 2001 22:13:03 +0000 (UTC) Newsgroups: sci.math.num-analysis,sci.op-research Note that I've added sci.op-research to the newsgroups line- this is a topic that is at least as appropriate in sci.op-research as it is in sci.math.num-analysis. Ron Bruck wrote: >So: in large LP problems, what's the fastest method in use today? Is >simplex still competitive? What's the modern concensus about >Karmarkar's contribution? The fastest method for a particular problem depends on the details of the problem, the details of the implementations of the simplex and interior point methods used, as well as the computer that is being used. This is why all of the major commercial software packages for LP now include both an interior point solver (in particular, primal-dual barrier methods are used) and simplex codes (primal, dual, and specialized network solvers) As a rule of thumb, simplex is typically the way to go for smaller problems, while interior point methods can be faster for very large problems, especially problems that are highly degenerate. Attempts have been made to specialize interior point methods for network problems, but network simplex still dominates in this area. Attempts have also been made to use interior point methods within branch and bound schemes for integer programming (not a very good idea as it turns out), and within cutting plane schemes for integer programming (where it does work reasonably well.) The simplex method certainly has lived on in these applications. Karmarkar was certainly the first to publish a paper in which an interior point method was shown to solve LP's in polynomial time. However, the interior point methods that are widely used today (primal-dual logarithmic barrier methods) are not that similar to Karmarkar's algorithm. Furthermore, barrier methods were originally developed for nonlinear programming in the 1960's (See the classic book by Fiacco and McCormick.) Why weren't barrier methods exploited for linear programming in the 1960's? Among other reasons: - Nobody (anywhere) knew anything about polynomial time algorithms or NP-completeness in the 1960's. It wasn't until the 1970's that these ideas became popular in computer science. It wasn't until the late 1970's and early 1980's that specialists in optimization became aware of these ideas. - Techniques for the efficient Cholesky factorization of sparse symmetric positive definite matrices weren't available in the 1960's. This technology is absolutely critical to the performance of interior point methods. It became available in the 1970's. (See George and Liu's book from 1979.) Note that sparse matrix techniques have also helped to improve the performance of implementations of the simplex method. - A significant technical problem with barrier methods (for both linear and nonlinear programming) is that as the solution approaches optimality, the systems of equations that are solved at each iteration typically become very badly conditioned. This problem was recognized back in the 1960's, and is one of the reasons that interest in barrier methods declined. It turns out that this ill conditioning is relatively benign in the case of the primal-dual barrier method for LP, although this wasn't realized until much later. - The computational advantages of interior point methods become apparent only as we start to solve fairly large problems. The computers available in the 1960's didn't have the speed and memory to solve such large problems. - The simplex method was the paradigm. People had spent their entire careers working on it, and didn't see any particular reason to change. Interior point methods were a scientific revolution that couldn't happen until all of the bits and pieces were available and until a new generation of researchers came along who were trained in the required areas of computer science (analysis of algorithms, computational complexity, etc.), numerical linear algebra, and optimization. Fortunately, interior point methods were so exciting in their potential that they were very quickly adopted by the optimization community. -- Brian Borchers borchers@nmt.edu Department of Mathematics http://www.nmt.edu/~borchers/ New Mexico Tech Phone: 505-835-5813 Socorro, NM 87801 FAX: 505-835-5366 [duplicate .sig deleted --djr] ============================================================================== From: borchers@rainbow.nmt.edu (Brian Borchers) Subject: Re: Karmarkar's method Date: Tue, 6 Feb 2001 05:15:52 +0000 (UTC) Newsgroups: sci.math.num-analysis,sci.op-research I wrote: >Attempts have been made to specialize interior point methods for >network problems, but network simplex still dominates in this >area. Mauricio Resende of AT&T labs has recently published some results in which his interior point code beats CPLEX netopt on some large network problems. However, this code hasn't been made generally available, and all the commercial packages still implement network simplex methods. see his papers at http://www.research.att.com/~mgcr -- Brian Borchers borchers@nmt.edu Department of Mathematics http://www.nmt.edu/~borchers/ New Mexico Tech Phone: 505-835-5813 Socorro, NM 87801 FAX: 505-835-5366 [duplicate .sig deleted --djr] ============================================================================== From: hwolkowi@orion2.math.uwaterloo.ca (Henry Wolkowicz) Subject: Re: Karmarkar's method Date: 7 Feb 2001 14:34:37 GMT Newsgroups: sci.math.num-analysis,sci.op-research I would just like to add a few comments to Brian Borchers' descriptions of interior point methods vs simplex type methods. The log-barrier methods were known in the 60's and the ill-conditioning problem (benign for LP) was also known, as mentioned. However, the 'fix' for this ill-conditioning, i.e. transforming the optimality conditions that are obtained from the log-barrier problem to one that looks like a perturbation of complementary slackness z_ig_i(x)= \mu for all i actually appears in the Fiacco-McCormick book of the 60's. (Their algorithm has since been proved to be polynomial time on convex problems.) This avoids the terrible ill-conditioning of the original log-barrier optimality conditions g_i(x) - \mu/z_i = 0 The Fiacco-McCormick code SUMT was actually well-known in certain 'circles' and used successfully for many years even though log-barrier problems lost favour in other 'circles', i.e. SUMT was popular in the engineering community and never lost favour. (But it did not have any of the efficiency of modern codes as mentioned by Brian. In Fiacco's words: 'It was a sledgehammer'.) However, the simplex method should not be ruled out, as mentioned by Brian. In fact, the latest test results of Bob Bixby (on the netlib test set and also on other industry problems that he has collected - see 19th IFIP proceedings) show, surprisingly, that the dual simplex method is tops. This is most probably due to the fact that so many of the problems originate from combinatorial problems, e.g. from run cutting for airline crew scheduling. -------------------------------------- In article <95hvpa$mbs$1@newshost.nmt.edu>, Brian Borchers wrote: [quote of Feb 3 2001 post deleted --djr] -- Prof. Henry Wolkowicz |Email hwolkowicz@uwaterloo.ca Univ. of Waterloo |URL http://orion.math.uwaterloo.ca/~hwolkowi Dept of Comb and Opt |Tel (519) 888-4567, x5589 Waterloo, Ont. CANADA N2L 3G1 |Fax (519) 725-5441 ============================================================================== From: hwolkowi@orion2.math.uwaterloo.ca (Henry Wolkowicz) Subject: Re: Karmarkar's method Date: 7 Feb 2001 14:37:01 GMT Newsgroups: sci.math.num-analysis,sci.op-research I do not think that the ellipsoid method is an interior-point method (though I may be wrong). In fact, it is the reverse. Points are found to try and attempt to solve primal-dual feasibility. These points are never feasible until the end, i.e. once a feasible solution is found then it is known it is optimal. Here feasible means primal-dual feasible as well as the reverse of weak duality relationship. In article <3A7DAD34.3AA110BF@my-dejanews.com>, Roger Schlafly wrote: >Timothy Chow wrote: >> In article <95hvpa$mbs$1@newshost.nmt.edu>, >> Brian Borchers wrote: >> >Karmarkar was certainly the first to publish a paper in which an >> >interior point method was shown to solve LP's in polynomial time. >> Doesn't the term "interior point method" include the ellipsoid method? > >Yes, but the ellipsoid method was only of theoretical interest >and not very practical. -- Prof. Henry Wolkowicz |Email hwolkowicz@uwaterloo.ca Univ. of Waterloo |URL http://orion.math.uwaterloo.ca/~hwolkowi Dept of Comb and Opt |Tel (519) 888-4567, x5589 Waterloo, Ont. CANADA N2L 3G1 |Fax (519) 725-5441 ============================================================================== From: edadk@my-deja.com Subject: Re: Karmarkar's method Date: Thu, 08 Feb 2001 06:48:14 GMT Newsgroups: sci.math.num-analysis Hi, Search for the thread "Linear optimization" in the OR news group sci.op-research Here is a citation from Irv Lustig in that thread: "If you look at which method wins most often, we find that: Barrier wins 163 times Dual simplex wins 66 times Primal simplex wins 40 times" Barrier is same as Karmarkar method. Karmarkar method is by now an outdated term. Regards, Erling In article , Ronald Bruck wrote: > In another thread, on sci.math, someone asked "What's Karmarkar's > method?" I know that (so don't answer!), but it caused me to wonder > what the leading software method/package is today. > > There was a lot of controversy at the time Karmarkar patented (ugh!) his > method, and AT&T kept the details closely sequestered. Thus at first > there was doubt (and a portion of the NA community seemed to deny the > method COULD be better than simplex, "because we already tried that"). > > But I haven't followed the details since then. I deduce (from the large > and growing interior-point literature) that this WAS a better mousetrap. > In the almost twenty years since then, surely people can now estimate > how MUCH better. > > So: in large LP problems, what's the fastest method in use today? Is > simplex still competitive? What's the modern concensus about > Karmarkar's contribution? > > --Ron Bruck > > -- > Due to University fiscal constraints, .sigs may not be exceed one > line. > Sent via Deja.com http://www.deja.com/