[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Simplex vertex neighborhood
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] Simplex vertex neighborhood |
Date: |
Mon, 19 Aug 2013 11:14:36 -0500 (CDT) |
User-agent: |
Alpine 1.00 (DEB 882 2007-12-20) |
On Mon, 19 Aug 2013, sgerber wrote:
Thanks for all the helpful answers. One more clarifying question.
You mentioned:
It checks all extreme rays of a cone that includes the feasible region.
The number of rays is the dimension of the problem.
The cone you described is the intersection of the half spaces of the active
constraints. Does this mean that in your example one would have to
potentially check an exponential number of rays? This is not what the simplex
An exponential number of vertices.
algorithm does, right? The simplex algorithm only checks adjacent bases (at
most m*n), what do these geometrically correspond to? Just a subset of all
neighboring vertices?
The test for optimality requires testing up to n rays.
If the vertex is optimal, there might be no need consider other bases.
Performing minimum ratio tests for O(n)
variables might involve O(m*n) bases.
--
Michael address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword." -- Lily
- [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/15
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Matteo Fischetti DEI, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Matteo Fischetti DEI, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Kevin Hunter Kesling, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/17
- Re: [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/19
- Re: [Help-glpk] Simplex vertex neighborhood,
Michael Hennebry <=
- Re: [Help-glpk] Simplex vertex neighborhood, Matteo Fischetti DEI, 2013/08/19
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/20
- Re: [Help-glpk] Simplex vertex neighborhood, Andrew Makhorin, 2013/08/17