A modified GUB algorithm for solving linear minimax problems

This article is concerned with the minimization of the maximal value of a set of linear functions subject to linear constraints. It is well known that this problem can be transformed into a standard linear programming problem by introducing an additional variable. In case index sets of nonzero coefficients of the variables contained in each function are mutually exclusive, the constraints of the associated LP problem exhibit the almost-GUB structure. A technique was devised which reduced the number of arithmetic operations by exploiting this special structure. Computational results are also presented, which indicates that the present method is more efficient than the ordinary revised simplex method.