CAREER: Improving the Optimization and Re-Optimization of Mixed Integer Programs through the Study of Continuous Variables

This Faculty Early Career Development (CAREER) research proposes to develop new methodologies for the optimization and e-optimization of mixed integerprograms through the study of the particular nature of continuous variables. The premise is that continuous variables are an important source of difficulty in the solution of mixed integer programs that is often ignored. A better understanding of their specificity will yield improved methods for the optimization of mixed integer programs. The approach proposed consists in the development of a general theory for the lifting of continuous variables. This theory will be applied to enhance various standard branch-and-cut features (linear programming-based heuristic, cutting planes) and less traditional methods (primal algorithms). It will also be applied to the design of computationally efficient e-optimization techniques for mixed integer programs. Computational experiments will be carried out to validate the approaches on practical problems.

If successful, this project will result in the improvement of the capabilities and performance of the current mixed integer programming technologies. It will yield general-purpose software capable of solving time-consuming problems more efficiently and capable of solving intractable problems. The benefactors of these improvements are in virtually all sectors of the economy including finance, forestry, and manufacturing. It will yield software with built-in capabilities to perform efficient scenario-based analysis of optimal solutions. These improved features are essential in an environment where decision problems are considered more globally and where uncertainty is omni-present. Through its educational component, this research project will provide a reference accessible to practitioners about how, when general-purpose software fails, to solve problems with the most advanced mixed integer programming technologies.