A new relaxation and quick bounds for linear programming problem

Farhad Djannaty, Bewar Beshayi

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.
Full Text: PDF

How to Cite this Article

Farhad Djannaty, Bewar Beshayi, A new relaxation and quick bounds for linear programming problem, J. Math. Comput. Sci., 6 (2016), 894-906

Copyright © 2016 Farhad Djannaty, Bewar Beshayi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.