A New Reformulation Technique for Tightening Relaxations of Some Combinatorial Optimization Problems with Application tothe General Linear Complementarity Problem
{'Code': '07030000', 'Directorate': {'Abbreviation': 'ENG', 'LongName': 'Directorate For Engineering'}, 'Division': {'Abbreviation': 'CMMI', 'LongName': 'Div Of Civil, Mechanical, & Manufact Inn'}}
{'SignBlockName': None, 'PO_EMAI': None, 'PO_PHON': None}
This proposal deals with a novel reformulation technique for                    combinatorial problems which can be modelled as mixed zero-one                  programming problems.  The model may include polynomial terms without           products among continuous variables.  The research, however,                    concentrates on two important, general subclasses which arise in                numerous engineering, economic and industrial applications, namely,             the linear mixed-integer zero-one programming problem and the linear            complementarity problem (LCP).  The reformulation technique uses an             enumeration of variable factors to multiply constraints and create new          nonlinear constraints which are subsequently linearized by defining             new variables.  The motivation is to provide a tight linear                     programming relaxation which closely approximates the convex hull of            feasible solutions and hence admits a successful application of                 discrete optimization techniques.  It is conjectured that this                  technique indeed characterizes the convex hull of feasible solutions            for binary knapsack problems (we have verified this for two and three           dimensions), and therefore would be particularly beneficial for                 unstructured, sparse problems.  Various implementation schemes and              constraint generation procedures based on this reformulation are                proposed for investigation.  As a special test case, and also to study          a problem important in its own right, we propose an elaborate                   algorithm for the general LCP.  The algorithm includes the use of the           new reformulation technique as well as other specialized constructs             such as strengthened convexity cuts based on new viewpoints of the              problem.  A plan for research is proposed which will lay the                    groundwork for extending this research effort into developing                   effective algorithms for a rich variety of problems which exploit this          reformulation strategy.
{'FirstName': 'Hanif', 'LastName': 'Sherali', 'PI_MID_INIT': 'D', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Hanif D Sherali', 'EmailAddress': 'hanifs@vt.edu', 'NSF_ID': '000262031', 'StartDate': '03/15/1989', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Virginia Polytechnic Institute and State University', 'CityName': 'BLACKSBURG', 'ZipCode': '240603359', 'PhoneNumber': '5402315281', 'StreetAddress': '300 TURNER ST NW', 'StreetAddress2': 'STE 4200', 'CountryName': 'United States', 'StateName': 'Virginia', 'StateCode': 'VA', 'CONGRESSDISTRICT': '09', 'CONGRESS_DISTRICT_ORG': 'VA09', 'ORG_UEI_NUM': 'QDE5UHE5XD16', 'ORG_LGL_BUS_NAME': 'VIRGINIA POLYTECHNIC INSTITUTE & STATE UNIVERSITY', 'ORG_PRNT_UEI_NUM': 'M515A1DKXAN8'}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
{'Code': '5514', 'Text': 'OPERATIONS RESEARCH'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8807090.xml'}