Journal of Applied Mathematics & Bioinformatics

An Algorithm for Binary Linear Programming

• [ Download ]
• Times downloaded: 11343

• Abstract

  A polynomial time algorithm, which is a modification of the simplex algorithm for Linear Programming (LP), is presented for solving Binary Linear Programming (BLP) problems. It is an n-step process where n is the number of binary variables of the problem. Conditions for existence, uniqueness, termination, and optimality are discussed. Three numerical examples are presented to explain the details and features of the algorithm. The algorithm generates two matrices. One of them is based on the minimum ratio concept of the Simplex method. It creates a Ratio Test Matrix from the ratio of corresponding elements of b vector and all column vectors. The other matrix, called Correlation Matrix, is generated from pseudo inverse estimates of the primal and dual variables. These two matrices provide an array of Column Selection Logic to assign binary values for variables corresponding to the matrix columns.