A new relaxation and quick bounds for linear programming problem

Abstract

In this paper a new relaxation is proposed for linear programming problem. Based on this relaxation very quick bounds are found for the problem and the associated integer programming restriction which can be used in a tree search algorithm to find the optimal IP solution. Some cost allocation strategies are described to allocate the column cost among nonzero entries of the column which leads to different bounds for the problem. A number of linear programming problems are randomly generated and computational results are presented.