Robust reduction of a class of large-scale linear programs (Q2784411)

New tests are derived for discovering redundant constraints and variables in large-scale linear programs which include box constraints and have nonnegative objective and matrix coefficients. Each test requires the solution of a linear programming problem with one inequality constraint and lower and upper bounds on the variables. In order to detect redundant constraints and variables, respectively, it is suggested to apply tests of this type to the primal and the dual program consecutively and to repeat this primal-dual procedure, possibly several times in succession, after the superfluous information has been removed. The tests for constraint reduction are mentioned to likewise apply to integer and mixed-integer problems. An extension of these to general linear programs is discussed. Numerical examples demonstrate the efficiency of the tests, where two iterations were performed for the primal-dual procedure and, alternatively, for the row reducing tests only. Finally, variants of all tests are provided for the case that the data of the program are known only within some given range.