An Additive Algorithm for the Multiple Choice Integer Program.
Abstract
The problem dealt with in this report is the Multiple Choice Integer Program (MCIP), a special case of the integer linear programming problem with binary variables. In this problem the variables are partitioned (using the classical definition of 'partition'). Exactly one variable in each partitioning set has the value one in any feasible solution and all other variables have the value zero. The problem also allows any additional constraints that can be expressed as linear inequalities. The objective is to choose elements from these sets so as to minimize cost. Chapter 2 discusses the history of this problem and solution techniques developed for it and similar problems such as the classical assignment problem, the generalized assignment problem, the multiple choice problem, the generalized upper bounding problem and the multiple choice knapsack problem. Chapter 3 presents discussion of additive type algorithms and the algorithm proposed in this report. It also includes definitions and notations. Applications of this algorithm follow in Chapter 4 with worked examples for three problems: a scheduling problem, an assembly line balancing problem and a distribution problem. In Chapter 5 it is proven that the algorithm will correctly solve any problem of this type in finite time. In Chapter 6 Geoffrion's surrogate constraints are revised to take advantage of the additional structure in this problem. Three possible formulations of surrogate constraint LP's are presented. By taking advantage of the special structure of the MCIP, the size of the LP's relative to those used for general binary programming is greatly reduced. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1980
- Accession Number
- ADA092691
Entities
People
- James Carl Bean
Organizations
- Stanford University