zbMATH — the first resource for mathematics

Algorithmic enhancements to the method of centers for linear programming problems. (English) Zbl 0753.90040
Summary: Interior point algorithms for solving linear programming problems are considered. The techniques are derived from a continuous version of Huard’s method of centers that yields a family of trajectories in the feasible region that all converge to an optimal solution. The tangential direction of these trajectories is the dual affine direction. Deficiencies in some of these trajectories are discussed, and the need to recenter is argued. Several new algorithms that use the dual affine direction and a recentering direction in a multidirection approach are then derived. The most promising of these algorithms is based on minimizing the cost function on a sequence of two-dimensional cross sections of the feasible region. Numerical results are presented.

90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI