Zero/one decision problems with multiple resource constraints: algorithms and applications

Two complex resource allocation problems motivate the algorithms and applications discussed in this dissertation. The Public Broadcasting Service (PBS), a cooperative of television stations with independent budgets, must decide which programs to purchase from various producers and at what cost to its member stations. The airports of America must decide how to allocate limited takeoff and landing slots to competing airlines. Both problems are recognized as zero/one decision problems with multiple resource constraints. A computer aided allocation mechanism is proposed as an alternative to the currently practiced decision procedures. Bid information, solicited in an auction phase, provides values to parameterize a mathematical model. An optimization phase is then used to generate the best solution for the given information. The integer programming algorithms required to solve the particular models suggested are explored in detail. A best bound enumeration strategy which uses a surrogate knapsack relaxation is developd. Computer storage requirements are curtailed by using a new greedy heuristic for general integer programming problems. The PBS model has a structure closely related to certain fixed charge problems. This allows the use of necessary conditions for the existence of a solution of capacitated transportation problems to test the feasibility of candidate solution vectors. In the SLOT model feasibility testing is a trivial matter of maintaining running row sums. The bound provided by the knapsack relaxation is further enhanced with the addition of a set of generalized choice constraints. An efficient polynomial algorithm and proof of optimality are given for the linear relaxation of this problem. A procedure for generating a set of generalized choice constraints from any set of logical constraints is also given. The viability of the approach developed and the effects of parameter variation are computationally tested in both PBS and SLOT contexts. Some further computational results for project selection, set covering, and multiple knapsack problems are reported. A broad class of mixed integer linear programming problems is defined (e.g., capital expenditure and network design problems) and a suitable relaxation for a similar approach is developed. Finally, several new directions for research in algorithmic development and application are proposed.