Portal de Periódicos da CAPES

The Ellipsoid Method Generates Dual Variables

1985; Institute for Operations Research and the Management Sciences; Volume: 10; Issue: 4 Linguagem: Inglês

10.1287/moor.10.4.688

1526-5471

Bruce P. Burrell, Michael J. Todd,

Computational Geometry and Mesh Generation

We show that the ellipsoid algorithm applied to a system of linear inequalities can be implemented in such a way that at each iteration there is a short proof of the containment of the feasible region in the current ellipsoid. Moreover, the data describing each ellipsoid also generate dual variables that provide bounds on the linear functions appearing in the inequalities.