help-glpk
[Top][All Lists]

## Re: [Help-glpk] Simplex vertex neighborhood

 From: Matteo Fischetti DEI Subject: Re: [Help-glpk] Simplex vertex neighborhood Date: Mon, 19 Aug 2013 19:12:44 +0200 User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8

Just a last comment: in case of (primal) degeneracy, a vertex x* can be optimal but a given associated basis B can still lead to negative reduced costs, i.e., B can be "nonoptimal". Indeed, the test on reduced costs is only a sufficient condition that can be violated by several bases B associated to an optimal vertex x*.
```
```
Under appropriate rules (Bland or lexicographic), however, you can prove that the simplex method will eventually find a basis B* still associated x* that satisfied the reduced- cost condition, i.e. an "optimal B*" always exists. But going from B to B* can require a huge n. of pivots, in a sense because you need to "implicitly consider" all the adjacent vertices.
```
Matteo

Il 19/08/2013 18:14, Michael Hennebry ha scritto:
```
```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.

```
```

--
Prof. Matteo Fischetti