Many scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the optimality of the final design. Mixed-integer nonlinear programming (MINLP) optimization problems combine the difficulty of optimizing over discrete variable sets with the challenges of handling nonlinear functions. MINLP is one of the most flexible modeling paradigms available, and an expanding body of researchers and practitioners, including computer scientists, engineers, economists, statisticians, and operations managers, are interested in solving large-scale MINLPs. Unfortunately, the wealth of applications that can be accurately modeled by using MINLP is not yet matched by the capability of available algorithms and software. This research will address the mismatch between natural optimization models and available robust optimization solvers, developing and delivering powerful new solvers for mixed-integer nonlinear programs.

The research thrusts are in three main categories. In the first thrust, the investigators study the structure of fundamental MINLP models, developing preprocessing techniques and strong valid inequalities. The second thrust, search, leverages the results of the structural analyses to design search and partitioning strategies for algorithms. The third thrust, implementation, focuses on implementing the resulting algorithmic frameworks efficiently on modern computational resources. The project has the transformative goal of making MINLP into an area in which researchers and practitioners can access robust tools and methods capable of solving a wide range of important, commonly occurring decision support problems.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
0830035
Program Officer
Balasubramanian Kalyanasundaram
Project Start
Project End
Budget Start
2009-01-01
Budget End
2012-12-31
Support Year
Fiscal Year
2008
Total Cost
$100,003
Indirect Cost
Name
University of Chicago
Department
Type
DUNS #
City
Chicago
State
IL
Country
United States
Zip Code
60637