Technical Note—A Langrangian Algorithm for the Multiple Choice Integer Program

In the Multiple Choice Integer Program, the binary variables are partitioned into generalized upper bounding sets (or special ordered sets). We solve this problem using a branch-and-bound scheme designed to take advantage of this structure. The basic procedure is enhanced by solving a Lagrangean problem as an approximation. Further, we use a variable reduction technique to eliminate many of the variables prior to problem solution. Computational experience is promising for randomly generated problems, scheduling problems, and budgeting problems tested.