Sparse Integer Programming

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Mixed-integer linear programming is a mathematical optimization framework that allows modeling discrete optimization problems that arise in various fields of engineering and business, such as chemical engineering, finance, forestry, health care, power systems, and supply-chain design. Most mixed-integer programming formulations that appear in these different areas of application involve very sparse constraint matrices. Many areas of scientific computing and optimization have been very successful in harnessing the effect of such sparsity of input data to improve the efficacy of algorithms. However, the use of sparsity of input data is a very under-explored direction of research in the context of mixed-integer linear programming algorithms. This award supports fundamental research for advancement of mixed-integer linear programming solver techniques for instances with sparse constraint matrices. Any improvement of the solvers obtained could result in significant gains to a large number of different applications. This project will support and train one PhD student who will be involved with all aspects of the research and dissemination of the results. The goal of this research is to systematically investigate the mathematical implications of sparse data matrices and to use this as a starting point for development of new and improved algorithms for solving mixed-integer linear programs that exploit sparsity in a holistic fashion. If successful, this project will be able to uncover formal mathematical explanation for various empirically observed behavior of mixed-integer linear programs, such as: Why does selection of sparse cutting-planes for mixed-integer linear programs with sparse constraint matrix work well in many cases? Why does feasibility pump, an important primal heuristic, work much better on average for mixed-integer linear programs with sparse constraint matrices? Why does the proportion of integral vertices to the total number of vertices of the linear programming relaxation of binary mixed-integer linear programs increase on an average as the formulations become more sparse? Using such insights, the research project will explore various avenues of improving mixed-integer linear programming solvers in order to better exploit sparsity, such as a new paradigm for sparse cut selection, increasing sparsity by use of extended formulations and combining new and different types of heuristics targeted towards better performance on sparse mixed-integer programming instances.