权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Scalable Methods for Solving Stochastic Mixed-Integer Programs

求解随机混合整数程序的可扩展方法

基本信息

批准号：
1634597
负责人：
James Luedtke
金额：
$ 39.96万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-09-01 至 2020-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1634597&HistoricalAwards=false
关键词：
Scalable Methods Solving Stochastic Mixed

项目摘要

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.

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