Max-Linear Programming: Transformation From R to R

Abstract

Let a ⊕ b = max(a,b)and a ⊗ b = a+b for a,b ∈ R: = R∪(-∞) and extend the pair of operations to matrices and vectors in the same way as in linearalgebra. Max-linear programming is a problem of the form f^T⊗ x --> min(or max) subject to A ⊗ x ⊕ c = B ⊗ x ⊕ d. Max-linear programs with finite entries have been considered in the literature and solution
methods for both minimization and maximization problems have been developed. In this paper we consider max-linear programming problems with infinite entries and show that this problem can be transformed to the one with all input variables finite.