Scalable Methods for Solving Stochastic Mixed-Integer Programs

科学、工程、经济分析和公共部门应用中的许多决策问题都涉及离散决策和未来结果的不确定性。 随机混合整数规划是一个重要的数学建模框架，它允许系统地处理涉及大量离散的是非决策的优化问题中的不确定性。如果成功，这项工作将成为通用软件的基础，可用于发电规划，军事行动，供应链规划和森林火灾响应等领域的各种规划问题。解决这些问题的方法的可用性将使决策者能够在面对不确定性时制定更稳健的计划，从而改善结果并更有效地利用稀缺资源。通过将不确定性条件下的优化建模融入到各学科的课程中，鼓励采用这些技术。本项目将融合现代凸优化、混合整数规划和随机规划的算法思想，获得求解随机混合整数规划的强大工具。 将设计新的算法，获得收敛结果，并制作软件。 该方法的一个重要组成部分是变量分裂分解结合拉格朗日松弛。 在这种方法中获得强下界需要优化拉格朗日对偶，这是一个具有挑战性的数学问题，最大化高维，非光滑，凹函数，其中评估函数及其子梯度的成本很高。研究小组将研究凸优化技术的翻译，这些技术最近在数据分析应用中被证明是成功的，以解决这个拉格朗日对偶。研究小组还将研究使用整数规划技术来获得收敛到最优解，包括强分支和伪成本，切割平面和原始算法。

Many decision problems in science, engineering, economic analysis, and public-sector applications involve both discrete decisions and uncertainty about future outcomes. Stochastic mixed-integer programming is an important mathematical modeling framework that allows for the systematic treatment of uncertainty in optimization problems that involve a large number of discrete, yes-no decisions. If successful, this work will form the basis of general-purpose software that can be used in a wide variety of planning problems in areas as diverse as electricity generation planning, military operations, supply chain planning, and forest fire response. The availability of methods to solve such problems will give decision makers the ability to make plans that are more robust in the face of uncertainty, leading to improved outcomes and more efficient use of scarce resources. The adoption of these techniques will be encouraged by integrating optimization modeling under uncertainty into courses taken by students in a variety of disciplines.This project will fuse algorithmic ideas from modern convex optimization, mixed-integer programming, and stochastic programming to obtain powerful tools for solving stochastic mixed-integer programs. New algorithms will be designed, convergence results will be obtained, and software will be produced. A vital ingredient of the approach is a variable-splitting decomposition combined with Lagrangian relaxation. Obtaining strong lower bounds in this approach requires optimization of the Lagrangian dual, a challenging mathematical problem of maximizing a high-dimensional, non-smooth, concave function, for which the costs of evaluating the function and its subgradients are high. The research team will investigate the translation of convex optimization techniques that have recently been shown to be successful in data analysis applications to solving this Lagrangian dual. The research team will also investigate the use of integer programming techniques to obtain convergence to an optimal solution, including strong branching and pseudocosts, cutting planes, and primal heuristics.