Linear Programming Tools for Integer Programming
{'Code': '05010200', 'Directorate': {'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'S. Kamal Abdali'}
This research is directed towards simplex-based tools for integer and           linear programming.  The principal application is integer programming,          but this work also provides an opportunity to study the simplex method          as a method for solving any linear program.                                                                                                                     This research makes use of LOPT, an existing C implementation of the            simplex method developed by the proposer.  Principal aspects of the             research are the following:                                                                                                                                       o   Developing effective data structures and reoptimization methods           for                                                                                   dealing with a sequence related but dynamically changing linear                 programming problems.                                                                                                                                       o   Studying methods for dealing with the large-scale degeneracy that         arises                                                                                in combinatorial applications.                                                                                                                              o   Further improvements in the basic elements of the LOPT                         implementation,                                                                  including developing C implementations of sparse factorization                 routines,                                                                        factorization update routines, and variations of these routines           that                                                                                  exploit the special structure of combinatorially defines                  problems.                                                                                                                                                       This work is being carried out, in part, in collaboration with Martin           Grotschel of the University of Augsburg.  A joint research project on           polyhedral methods for the max-cut problem is also underway together            with Francisco Barahona of the University of Waterloo.  This latter             work is not formally part of the current proposal, but is an important          parallel effort.  Both the collaboration with Grotschel and that with           Barahona will provide concrete integer programming instances central to         the present investigation.
{'FirstName': 'Robert', 'LastName': 'Bixby', 'EmailAddress': None, 'StartDate': '02/15/1989', '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': '2865', 'Text': 'NUMERIC, SYMBOLIC & GEO COMPUT'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8815914.xml'}