There Are 10 Kinds of Problems in the World: Those That Are Binary and Those That Aren’t

Abstract

Binary integer programming is a class of algorithms that are used to solve problems where we have several yes/no decisions, along with some constraints on which decisions we can make and a value associated with each decision. A classic example is the knapsack problem, where we have to choose what to carry in the knapsack. For each possible item, we can carry it or not. We are also limited by space and weight, and some objects will have a higher value than others. This paper examines binary integer programming and a simple computer implementation of a technique for solving such problems, called the Multiphase Dual Algorithm, which was developed by Dr. Fred Glover in 1965. We also test the execution time of this program compared to an implementation of a branch-and-cut algorithm developed by COIN-OR. Results show that this Multiphase Dual program executes in about the same time as the branch-and-cut algorithm on small problems, but starts to become slower on large programs. This indicates that although the Multiphase Dual algorithm may not be the fastest possible algorithm, it can solve binary integer programming problems in a reasonable time. We conclude by discussing other parts of the algorithm whose implementation would increase its efficiency.