A branch and bound algorithm for allocation problems in which constraint coefficients depend upon decision variables

Donald Gross and Richard M. Soland

Naval Research Logistics Quarterly, 1969, vol. 16, issue 2, 157-174

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/materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft which exhibit 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/aircraft/month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relationships 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.

Date: 1969
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800160202

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:16:y:1969:i:2:p:157-174

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().