Research Initiation:  Polyhedral Theory and Algorithms for  Two NP-Complete Problems
{'Code': '07010000', 'Directorate': {'LongName': 'Directorate For Engineering'}, 'Division': {'LongName': 'Div Of Electrical, Commun & Cyber Sys'}}
{'SignBlockName': 'Kevin I. Sewell'}
Precedence constraints arise frequently in discrete optimization                problems.  Polyhedral theory and computational experience both suggest          that integer programs defined largely by precedence constraints have            structure that can be exploited to develop good polyhedral-based                algorithms for their solution.  Two important integer programming               problems with precedence constraints are the precedence-constrained             knapsack problem and the plant location problem.  The PI will develop           new polyhedral results for these NP-complete problems so that together          with existing polyhedral results fast, efficient algorithms for their           solution can be implemented.  Special attention will be given to the            development of parallel algorithms.  Beyond providing operational               algorithms that can be used to solve actual applications of these two           problems, the work will extend the known theory of polyhedral                   combinatorics.
{'FirstName': 'E. Andrew', 'LastName': 'Boyd', 'EmailAddress': 'boyd@marvin.tamu.edu', 'StartDate': '07/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'William Marsh Rice University', 'CityName': 'Houston', 'ZipCode': '770051827', 'PhoneNumber': '7133484820', 'StreetAddress': '6100 MAIN ST', 'CountryName': 'United States', 'StateName': 'Texas', 'StateCode': 'TX'}
[{'Code': '1454', 'Text': 'SYSTEMS THEORY'}, {'Code': '5514', 'Text': 'OPERATIONS RESEARCH'}]
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8809053.xml'}