| NSF Org: |
DMS Division Of Mathematical Sciences |
| Recipient: |
|
| Initial Amendment Date: | July 28, 2019 |
| Latest Amendment Date: | April 23, 2020 |
| Award Number: | 1913294 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Yuliya Gorb
ygorb@nsf.gov (703)292-2113 DMS Division Of Mathematical Sciences MPS Directorate for Mathematical and Physical Sciences |
| Start Date: | August 1, 2019 |
| End Date: | July 31, 2020 (Estimated) |
| Total Intended Award Amount: | $100,000.00 |
| Total Awarded Amount to Date: | $44,573.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
201 SIKES HALL CLEMSON SC US 29634-0001 (864)656-2424 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
230 Kappa St. Suite 200 Clemson SC US 29634-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | COMPUTATIONAL MATHEMATICS |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.049 |
ABSTRACT
Mathematical optimization problems arise in many applications in diverse fields in science and engineering. A large portion of these problems require discrete decisions to be made, where some of the unknowns are restricted to take only integer values. There continues to be a pressing need to further improve the performance of the state-of-the-art for solving mixed integer problems, especially when the unknowns in the problem are constrained through nonlinear relationships. This research project develops new mathematics for optimizing mixed integer problems. The overall impact will be visible through the implementation of new and sophisticated algorithms for solving these problems. An auxiliary algorithm will be developed to aid our main algorithm and it will also be applicable to optimization in decision theory, game theory, and cryptography. The algorithms will be empirically tested on benchmark problems, and used to solve an application in oil and gas industry and a fundamental problem in statistical learning that is widely-used for predictive analytics. Research from this project will be integrated into classroom through the development of a new graduate course that teaches algebraic and combinatorial methods in discrete optimization. The award will provide support for graduate student training through research.
The primary research objective of this project in computational mathematics is to derive novel polyhedral relaxations for the feasible regions of mixed integer problems (MIPs) through an innovative interpretation of discrete feasible regions arising from ordered sets of integral vectors under some monomial ordering. The research activities involve developing a rich body of knowledge about cutting planes, valid inequalities, and polyhedral relaxations for MIPs, approximation algorithms for MIPs, and using discretization methods to efficiently approximate MIPs with polynomial constraints. Thus, this project will establish new connections between computational algebra, combinatorics, and mathematical optimization. One of our methods for generating cutting planes using a monomial order generalizes and strengthens the cutting planes derived from the well-known split disjunctions. The theory we develop does not depend explicitly on the algebraic representation of the feasible set, therefore making it applicable to all classes of MIP and presenting a very different approach than many of the existing studies that explicitly depend on the linearity of the constraints.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
Please report errors in award information by writing to: awardsearch@nsf.gov.
