CAREER: Foundational Aspects of Discrete Optimization: Theory and Algorithms

Johns Hopkins University, Baltimore MD

Investigators

Abstract

This Faculty Early Career Development (CAREER) grant aims to break new ground in the fundamentals of discrete optimization. Discrete optimization provides solution methods for solving large-scale decision making problems where a combination of discrete choices (e.g., should this power generator be on or off?) and non-discrete choices (e.g., what concentration of a chemical is to be maintained in a chemical process) have to be made to optimize a given objective (such as minimize costs, or environmental impact of a process, or maximize profits). These solution methods are widely applied in a diverse suite of scientific, technological and logistical problems, and are grounded in mathematical theory that has been built in the last 50-60 years. However, these techniques are showing signs of stagnation in the face of some of the complex, large scale problems of today?s modern applications. Significantly new ideas at the foundational level are required to keep pace. This grant aims to meet this challenge by making breakthroughs in the mathematical theory, and leverage that theory to forge more efficient tools for discrete optimization. Part of the relevant mathematics is suitable for introducing motivated high-school students and undergraduates to this research. It hopes to showcase the beauty and enormous applicability of mathematics to solve important problems, and attract students to pursue careers in scientific, technological, engineering and mathematical fields. The technical breakthrough will be achieved in three aspects of mixed-integer optimization: (i) cutting planes, (ii) duality theory and, (iii) linear programming components of the branch-and-cut paradigm in mixed-integer optimization solvers. A part of the effort will be focussed on translating techniques developed for linear problems to the nonlinear setting. Techniques from convex geometry, geometry of numbers, functional analysis, algebraic topology and real algebraic geometry will be employed in tackling (i), (ii) and (iii). Many of these connections are recent insights made in the last 5-6 years and have proved extremely useful in resolving decades-long open questions in the field of mixed-integer optimization. There is a lot of hope that such rapid progress can be continued by deeper investigation of the connection between these areas of mathematics and mixed-integer optimization. In the process, fresh dialogue can be facilitated between mathematicians and engineers through this research. The overall technical contribution will be towards developing the theoretical foundations of linear and nonlinear mixed-integer optimization, and provide radically new ideas for cut generation and branching in solvers.