Re: [Help-glpk] Computation Complexity of lpx_integer

[glpk xypron]

Hello Paul,

if NP != P you cannot expect polynomial time complexity using branch and bound.

The number of nodes in exhaustive search of a binary tree for n decision 
variables is 2^^(n+1)-1. The worst case time needed for the implemented Simplex 
is exponential in problem size, too.

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Wed, 25 Jun 2008 11:22:43 +0800 (SGT)
> Von: RC Loh <address@hidden>
> An: address@hidden
> Betreff: [Help-glpk] Computation Complexity of lpx_integer

> Hi,
> I know that the "lpx_integer" and the "lpx_intopt" routines are using the
> branch-and-bound method. Does anyone knows the computation complexity of
> both of the routines? Are they exponential?
> Thank you.
> Rdgs,
> Paul
> 
> 
>       Get your preferred Email name!
> Now you can @ymail.com and @rocketmail.com
> http://mail.promotions.yahoo.com/newdomains/sg/

-- 
Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten 
Browser-Versionen downloaden: http://www.gmx.net/de/go/browser