[Couenne] Computational Complexity of Couenne

[Pietro Belotti]

Imtiaz,

mixed integer nonlinear programming (MINLP) problems, which Couenne 
targets, are NP-hard. Even very special subclasses of MINLP, such as 
quadratic optimization problems, are NP-hard.

Couenne is a spatial branch and bound, as you mention, and as such its 
worst-case complexity is exponential in the number of variables, both 
integer and continuous.

Pietro

--
Pietro Belotti
Dept. of Mathematical Sciences
Clemson University
email: pbelott at clemson.edu
phone: 864-656-6765
web:   http://myweb.clemson.edu/~pbelott

On Tue, 12 Jun 2012, imtiazah at ece.ubc.ca wrote:

>
> Dear Sir,
> Is there any documentation on the (analytically) analysis of
> computational complexity of Couenne?
> Or, can you kindly refer me to any paper/research article which describes
> the computational complexity of spatial branch and bound method?
> Thank you,
> Best Regards,
> Imtiaz
>
> _______________________________________________
> Couenne mailing list
> Couenne at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/couenne