A BRANCH-AND-BOUND ALGORITHM FOR ALLOCATION PROBLEMS IN WHICH CONSTRAINT COEFFICIENTS DEPEND ON DECISION VARIABLES.
Abstract
A branch-and-bound algorithm is developed for a class of allocation problems in which some constraint coefficients depend on the values of certain of the decision variables. Were it not for these dependencies, the problems could be solved by linear programming. The algorithm is developed in terms of a strategic-deployment problem in which it is desired to find a least-cost transportation fleet, subject to constraints on men and/or materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft with the characteristic that the amount of goods deliverable by an aircraft on a particular route in a given time period (called aircraft productivity and measured in kilotons per aircraft per month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relations are first approximated by piecewise linear functions. A branch-and-bound algorithm for solving the resultant nonlinear problem is then presented; the algorithm solves a sequence of linear programming problems. The algorithm is illustrated by a sample problem, and comments concerning its practicality are made. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1968
- Accession Number
- AD0675409
Entities
People
- Donald Gross
- Richard M. Soland