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

这项教师早期职业发展(Career)研究建议通过对连续变量的特殊性质的研究，为混合整数计划的优化和e-优化开发新的方法。前提是在混合整数规划的求解中，连续变量是一个重要的困难来源，而这一点往往被忽视。更好地了解它们的特殊性将产生优化混合整数程序的改进方法。所提出的方法包括发展一种提升连续变量的一般理论。这一理论将被应用于增强各种标准的分支和切割特征(基于线性规划的启发式、割平面)和非传统方法(原始算法)。它还将用于设计计算效率高的混合整数规划的e-优化技术。将进行计算实验以验证所提出的方法在实际问题上的有效性。如果成功，该项目将改善目前混合整数编程技术的能力和性能。它将产生通用软件，能够更有效地解决耗时的问题，并能够解决棘手的问题。这些改善的受益者几乎是所有经济部门，包括金融、林业和制造业。它将产生具有内置功能的软件，以执行高效的基于场景的最佳解决方案分析。在决策问题被更全球化地考虑并且不确定性无处不在的环境中，这些改进的功能是必不可少的。通过其教育部分，这一研究项目将为从业人员提供一个参考，告诉他们当通用软件出现故障时，如何利用最先进的混合整数编程技术来解决问题。

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.