Re: [Help-glpk] What is the complexity of GLPK?

[Haroldo Santos]

Binary Programming is NP-hard.

So, unless your problem is nicely structured (e.g. some network flow
problems), the worst case complexity is exponential.

2010/8/3 xiaomi <address@hidden>:
> Is it polynomial or exponential? If I use binary conditions, will it
> change? Because when I use binary condition, it runs much slower to get
> the final optimal solution (from 3 seconds to 20 hours).
>
> Thanks.
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
>



-- 
=============================================================
Haroldo Gambini Santos
Computing Department - Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: http://www.iceb.ufop.br/decom/prof/haroldo/

"Computer science is no more about computers than astronomy
is about telescopes." Edsger Dijkstra