Premium
A mofified gub algorithm for solving linear minimax problems
Author(s) -
Kuno Takahito,
Mori Kouji,
Konno Hiroshi
Publication year - 1989
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198906)36:3<311::aid-nav3220360308>3.0.co;2-l
Subject(s) - linear programming , simplex algorithm , mathematics , minimax , mathematical optimization , simplex , algorithm , revised simplex method , variable (mathematics) , linear fractional programming , set (abstract data type) , function (biology) , minification , value (mathematics) , computer science , combinatorics , mathematical analysis , statistics , evolutionary biology , biology , programming language
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. We devised a technique which reduces the number of arithmetic operations by exploiting this special structure. Computational results are also presented, which indicates that our method is more efficient than the ordinary revised simplex method.