Algebraic Linear Programming

The algebraic approach to network-flow problems discussed by Burkard and Zimmermann (Burkard, R. E., U. Zimmermann. 1977. Weakly admissible transformations for solving algebraic assignment and transportation problems. Balinski and Padperg, eds. Report 1977-8, Mathematische Institut der Universitat Zu Koln (1977). To appear in Math. Prog. Stud.) is generalized to linearly-constrained problems. The aim is to choose a real nonnegative n-vector N that minimizes c(x) subject to finitely many linear equations with positive right-hand sides where the range S of c(·) is totally ordered and c satisfies other algebraic assumptions. This structure includes lexicographic linear programs in which c(x) = Cx where C is a matrix with n lenieographically-nonnegative columns and S is totally ordered by the lexicographic order. This problem in turn includes ordinary and bottleneck linear programs. A primal-dual method is given for solving these “algebraic” linear programs.