[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] Linear Programming Relaxation

**From**: |
David Bremner |

**Subject**: |
Re: [Help-glpk] Linear Programming Relaxation |

**Date**: |
Wed, 25 Nov 2009 08:54:12 -0400 |

**User-agent**: |
EMIKO/1.14.1 (Choanoflagellata) FLIM/1.14.9 (Goj ō) APEL/10.7 EasyPG/1.0.0 Emacs/23.1 (i486-pc-linux-gnu) MULE/6.0 (HANACHIRUSATO) |

RC Loh wrote:
>*Just to confirm on question (2). I understand that GLPK also uses*
>*Interior Point method. Isn't the Interior Point method a polynomial*
>*time method?*
Yes it is, but for linear programming, not for integer or mixed
integer programming.
>*So with the Linear Programming Relaxation, the GLPK still does not*
>*runs in polynomial time?*
A MIP solver needs to solve a whole search tree where each node is an
LP relaxation, and in general the number of LP relaxations solved is
not bounded by a polynomial in the input size. There are many books
where this is explained; I happen to know "A First Course in
Combinatorial Optimization" by Jon Lee, see Chapters 6 and 7.
David

**[Help-glpk] Linear Programming Relaxation**, *RC Loh*, `2009/11/24`
**Re: [Help-glpk] Linear Programming Relaxation**, *Andrew Makhorin*, `2009/11/24`
**Re: [Help-glpk] Linear Programming Relaxation**, *RC Loh*, `2009/11/25`
**Re: [Help-glpk] Linear Programming Relaxation**,
*David Bremner* **<=**
**Re: [Help-glpk] Linear Programming Relaxation**, *RC Loh*, `2009/11/25`
**Re: [Help-glpk] Linear Programming Relaxation**, *Andrew Makhorin*, `2009/11/25`
**Re: [Help-glpk] Linear Programming Relaxation**, *RC Loh*, `2009/11/26`
**Re: [Help-glpk] Linear Programming Relaxation**, *Andrew Makhorin*, `2009/11/27`
**Re: [Help-glpk] Linear Programming Relaxation**, *RC Loh*, `2009/11/29`
**Re: [Help-glpk] Linear Programming Relaxation**, *Michael Hennebry*, `2009/11/29`
**Re: [Help-glpk] Linear Programming Relaxation**, *Andrew Makhorin*, `2009/11/29`
**Re: [Help-glpk] Linear Programming Relaxation**, *RC Loh*, `2009/11/30`
**Re: [Help-glpk] Linear Programming Relaxation**, *Ali Baharev*, `2009/11/30`
**Re: [Help-glpk] Linear Programming Relaxation**, *Andrew Makhorin*, `2009/11/30`