MIXED INTEGER PROGRAMMING ALGORITHMS FOR SITE SELECTION AND OTHER FIXED CHARGE PROBLEMS HAVING CAPACITY CONSTRAINTS.
Abstract
Algorithms for solving site-selection and similar fixed charge problems with upper bound constraints are presented. The basic approach is to formulate the problem as a mixed integer program and to solve these programs by decomposing them into a master integer program and a series of subproblems which are linear programs. To reduce the number of vertices to be examined to manageable proportions, the bound-and-scan algorithm by F. S. Hillier was adapted to the fixed charge problem. Algorithms are presented for four classes of problems: (1) Fixed charge problem with linear variable costs and a fixed charge for each variable at non-zero level. (2) Problem 1 with separable concave or convex variable costs. (3) A warehouse location problem in which variable costs and constraints are of the transportation type. A fixed charge is associated with each warehouse opened. (4) The fixed charge transportation problem in which a fixed charge is associated with each route rather than with each warehouse. Computational results for Problems 1, 2, and 4 are presented. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 30, 1967
- Accession Number
- AD0663097
Entities
People
- Paul Gray
Organizations
- Stanford University