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 <[EMAIL PROTECTED]> > An: [email protected] > 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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
