A simplex algorithm for piecewise-linear programming. II: Finiteness, feasibility and degeneracy (Q1110457): Difference between revisions

[For part I see the author, Math. Program. 33, 204-233 (1985; Zbl 0579.90084).] In part I the simplex method for linear programming has been extended to permit the direct solution of convex separable piecewise-linear programming problems. This piecewise-linear simplex algorithm relies on three basic assumptions: nondegeneracy, existence of a basic feasible solution for starting the algorithm, and finiteness of the number of linearity intervals of the objective function. Part II shows how these assumptions can be weakened to make the effective use of the algorithm easier. Specifically, procedures for overcoming degeneracy are examined together with methods for constructing a basic feasible solution and for handling the case of an infinite number of linearity intervals.