[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Computation Complexity of lpx_integer

From: glpk xypron
Subject: Re: [Help-glpk] Computation Complexity of lpx_integer
Date: Thu, 26 Jun 2008 20:30:46 +0200

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


-------- 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 and

Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten 
Browser-Versionen downloaden:

reply via email to

[Prev in Thread] Current Thread [Next in Thread]