概率约束混合整数规划理论和方法研究

Mixed-integer programming problems with random parameters have many real-world applications in engineering,management and finance. Probabilistic constraint is an important method in modeling the stochastic property of optimization problems under uncertainty. This project aims to systematically investigate the theory and methods of probabilistically constrained mixed-integer programming problems. The research will be pursued in four major thrusts. We will study several important classes of mixed-integer linear and quadratic programming problems with probabilistic constraint including knapsack problem,facility location, minimum cost network flow, transportation, multi-period production problems and quadratic programs. We will study chance-constrained mixed-integer programming under finite distributions, establish tight reformulations by using technqiues of sample surrogate, stratified sampling and constraint surrogate, and develop corresponding branch-and-cut methods. We will investigate the combination of porbabilistic constraint and robust optimization method and establish distributed robust optimization methods and multi-period online optimization methods with limited information under uncertain and dynamic decision-making environment. We will study the applications of chance-constrained mixed-integer programming in financial engineering. In particular, we will establish portfolio selction models based on VaR and Basel Accords risk measures in risk management and finacial decision-making process. Efficient approximation methods and exact methods based on decomposition and cutting planes will be developed for probabilistically constrained finance optimization problems. The output of this reasearch will advance discrete optimization theory and methodologies under uncertainty.

参数具有随机性的混合整数规划问题在工程、管理和金融等领域具有广泛的应用。利用概率约束处理参数的随机性是不确定环境下的一种重要优化建模方法。本项目旨在系统和深入地研究概率约束混合整数规划的理论和算法。项目将着重研究几类重要的概率约束线性和二次混合整数规划问题，如概率约束背包问题、概率约束选址问题、概率约束最小费用网络流、概率约束多阶段产生计划规划等问题；研究离散分布下的概率约束混合整数规划问题，建立模型重构方法和有效的确定性混合整数规划等价问题，并设计相应的分枝-割算法。我们将研究随机和动态环境下概率约束方法与鲁棒优化方法的结合，提出分布式鲁棒优化方法和多阶段概率约束混合整数规划的在线算法。在应用方面，我们将利用概率约束方法建立VaR和新巴塞尔协议风险测度下的投资组合模型，并提出相应的快速近似算法和基于分解和割平面技术的精确算法。项目的研究成果将推动不确定环境下离散优化理论和方法的发展。

参数具有随机性的混合整数规划问题在工程、管理和金融等领域具有广泛的应用。利用概率约束处理参数的随机性是不确定环境下的一种重要优化建模方法。本项目旨在系统和深入地研究概率约束混合整数规划的理论和算法。本项目经过四年的研究，基本实现了项目立项时的研究目标，对项目立项时的研究内容进行了重点研究。本项目主要集中在以下几个研究方向：(1) 带概率约束的二次规划问题的交替方向算法研究；(2) 离散分布下带概率约束优化问题的分支-胞元算法研究；(3) 带稀疏约束凸规划问题的序列凸逼近算法研究；(4) 带半连续变量或基数约束的二次规划问题的MIQP 变换。随着研究的深入，我们在项目的四年研究中还在下列与项目相关的扩展方向进行了研究：（1）金融中带有参数敏感度约束投资组合选择模型与算法研究；（2）金融中非参数风险值投资组合选择模型的坐标轮换方法研究；（3）非凸二次规划的非线性SDP松弛和全局算法研究；（4）次序(低次序)优化问题的最优性条件和复杂性研究；(5)整数规划方法在物流管理和作业排序中的应用研究。项目取得了一系列较高水平的研究成果，已发表和录用了12 篇SCI学术论文，正在SCI源刊二审论文3篇，包括国际运筹与优化权威期刊SIAM Journal on Optimization，INFORMs Journal on Computing, European Journal of Operational Research，Mathematical Programming Computation, Journal of Global Optimization, Journal of Optimization Theory and Applications，Optimization Methods & Software等。