Multiple Choice Programming (A Procedure for Linear Programming with Zero-One Variables)

A new procedure for mixed integer programming is presented. It is applicable where the integer variables must be either zero or one, and where the integer variables are divided into sets such that the variables in each set sum to unity. Numerous practical applications fit this formulation. A justification for the algorithm is given, but proof of convergence is not known. The procedure has solved all test problems so far, and this computational experience is discussed along with some applications.