[Couenne] Computational Complexity of Couenne
Pietro Belotti
pbelott at clemson.edu
Wed Jun 13 23:23:00 EDT 2012
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
More information about the Couenne
mailing list