[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] What is the complexity of GLPK?
From: |
Haroldo Santos |
Subject: |
Re: [Help-glpk] What is the complexity of GLPK? |
Date: |
Tue, 3 Aug 2010 22:47:38 -0300 |
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