Computing bounds for the optimal value in linear programming

Consider a standard linear programming problem and suppose that there are bounds available for the decision variables such that those bounds are not violated at an optimal solution of the problem (but they may be violated at some other feasible solutions of the problem). Thus, these bounds may not appear explicitly in the problem, but rather they may have been derived from some prior knowledge about an optimal solution or from the explicit constraints of the problem. In this paper, the bounds on variables are used to compute bounds on the optimal value when the problem is being solved by the simplex method. The latter bounds may then be used as a termination criteria for the simples iterations for the purpose of finding a “sufficiently good” near optimal solution. The bounds proposed are such that the computational effort in evaluating them is insignificant compared to that involved in the simplex iterations. A numerical example is given to demonstrate their performance.