Summary Of Branch And Bound Algorithm For BIP (0,1) Using LP Relaxation

Abstract

In this paper we contemplate the Binary integer programming problems and presents a summary of the techniques of finding an optimal solution, using the Branchand-Bound algorithm highlighting some critical features and new trend in published articles not yet commonly found in most text books. A generic algorithm is presented and illustrated by solving a knapsack problem.

Keywords: Linear programming, Binary Integer programming, Relaxation, Branch and Bound, Variable selection, Partitioning, fathoming, Depth-first search, Fixing Variable

Journal of the Nigerian Association of Mathematical Physics, Volume 19 (November, 2011), pp 475 – 482