NSF CAREER AWARD FOR Santanu Dey: Non-traditional Cutting-Plane Algorithms for Mixed-Integer Programs

http://www.nsf.gov/awardsearch/showAward.do?AwardNumber=1149400

The research objective of this Faculty Early Career Development (CAREER) project is to improve the current generation of mixed-integer programming (MIP) solvers by devising new general-purpose cutting-plane methods. A great deal of useful information that could be used in deriving and selecting cutting-planes is often left unused by state-of-the-art MIP techniques. This project will investigate some of the following non-traditional paradigms for incorporating more information into cutting planes: (i) Use information from multiple constraints simultaneously to derive cutting planes, instead of using a single implied constraint. (ii) Design suitable cutting planes and then verify their validity before use, instead of deriving cutting planes without any control over their quality. (iii) Incorporate information from explicit enumeration of integer points to guide the choice of cutting planes and improve their strength. Since many mathematical challenges need to be overcome in order to tap the potential of these non-traditional paradigms, results from this project could significantly enhance the mathematical toolkit used by integer programmers for the generation and analysis of cutting planes.

If successful, this project will not only make theoretical advances in mathematical programming, but also lead to significant improvements in the performance of MIP solvers, leading to huge gains in a broad spectrum of applications of MIP models in areas such as health care, forestry, finance, supply-chain design, and chemical engineering. The key educational objective of this award is to develop an outside-classroom operations research puzzle competition to foster and enrich an environment for undergraduate research. Moreover a new graduate course will be designed with the aim of dissemination of research results directly to future practitioners and to bring students from different engineering communities together, thus providing opportunities for new research directions and collaborations.