ZERO/ONE DECISION PROBLEMS WITH MULTIPLE RESOURCE CONSTRAINTS: ALGORITHMS AND APPLICATIONS.

Persistent Link:
http://hdl.handle.net/10150/187881
Title:
ZERO/ONE DECISION PROBLEMS WITH MULTIPLE RESOURCE CONSTRAINTS: ALGORITHMS AND APPLICATIONS.
Author:
RASSENTI, STEPHEN.
Issue Date:
1982
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
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.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Resource allocation -- Decision making -- Mathematical models.; Algorithms -- Decision making.; Airports -- Management -- Mathematical models.; Public television -- Management -- Mathematical models.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Systems and Industrial Engineering; Graduate College
Degree Grantor:
University of Arizona

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleZERO/ONE DECISION PROBLEMS WITH MULTIPLE RESOURCE CONSTRAINTS: ALGORITHMS AND APPLICATIONS.en_US
dc.creatorRASSENTI, STEPHEN.en_US
dc.contributor.authorRASSENTI, STEPHEN.en_US
dc.date.issued1982en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractTwo 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.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectResource allocation -- Decision making -- Mathematical models.en_US
dc.subjectAlgorithms -- Decision making.en_US
dc.subjectAirports -- Management -- Mathematical models.en_US
dc.subjectPublic television -- Management -- Mathematical models.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.identifier.proquest8217461en_US
dc.identifier.oclc681972991en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.