A Note on Branch and Bound Algorithm for Integer Linear Programming
Syed Inayatullah *
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
Wajiha Riaz
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
Hafsa Athar Jafree
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
Tanveer Ahmed Siddiqi
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
Muhammad Imtiaz
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
Saba Naz
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
Syed Ahmad Hassan
Department of Mathematics, University of Karachi, Karachi, 75270, Pakistan.
*Author to whom correspondence should be addressed.
Abstract
In branch and bound algorithm for integer linear programming the usual approach is incorporating dual simplex method to achieve feasibility for each sub-problem. Although one can also employ the phase 1 simplex method but the simplicity and easy implementation of the dual simplex method bounds the users to use it. In this paper a new technique for handling sub-problems in branch and bound method has been presented, which is an efficient alternative of dual simplex method.
Keywords: Integer programming, branch and bound method, dual simplex algorithm, two-phase simplex method