[Coin-lpsolver] LP - complexity

[Matthew Saltzman]

On Mon, 25 Apr 2005 svoboda at fi.muni.cz wrote:

> Hello,
>
> I've been using CLP. I hope I'm right if I suppose that CLP is based on 
> simplex method designed by G. Dantzig. In general, the worst-case time 
> complexity for simplex method is exponetial. Fortunately, if using spare 
> matrices, we can get (average) polynomial complexity. May I ask anybody to 
> get a proof for this hypothesis?

Sparse matrices are not a requirement for proving polynomial 
complexity--matrix inversion is no worse than O(n^3) anyway.  The real 
issue for the simplex method is the number of iterations, not the 
complexity of an iteration.

There is a discussion in Vanderbei's book (LP Foundations and Extensions, 
Kluwer, 2001) on simplex method complexity which cites several sources 
for average complexity analysis of the simplex method.

>
> Moreover, I found a ref. to polynomial algorithm:
>
> Karmarkar, N. "A New Polynomial-Time Algorithm for Linear Programming."
> 	Combinatorica 4, 373-395, 1984.
>
> Is there any relationship between Karmarkar's alg. (based on Interior point 
> methods) and CLP?

ClpPredictorCorrector implements a Newton-barrier style interior point 
algorithm (a relative of Karmarkar's original algorithm).  The comments 
refer to the implementation as "crude", so caveat user.

Most Newton barrier implementations do not guarantee polynomial worst-case 
performace because implementing the guarantee can affect practical 
performance.  For a good analysis of interior-point methods, see Steve 
Wright's book (Primal-Dual Interior Point Methods, SIAM Press, 1997).

>
>
> With regards
>
> David Svoboda
> _______________________________________________
> Coin-lpsolver mailing list
> Coin-lpsolver at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>

-- 
 		Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs