离散分布下带机会约束优化问题的理论及分支-胞元算法研究

Optimization problems with random parameters have many real-world applications in engineering, management and finance. Chance constraint is an important modeling method in dealing with the stochastic property of optimization problems under uncertainty. This project aims to systematically investigate the theory and branch-and-cell method of chance constrained programming problems with finite discrete distributions. We will study the property of chance constraints, establish the relationship between chance constraints and the cells of hyperplanes in discrete geometry, and then solve chance constrained programming problems with discrete distributions via cell-enumeration method in discrete geometry. Based on those results, together with the combination of mixed-integer programming method and cell-enumeration method, the branch-and-cell method for chance constrained programming problems with finite discrete distributions will be established in this project. We will also investigate the polynomially solvable subclasses of chance constrained programming problems with finite discrete distributions. According to the property of linear programming, we will establish valid inequalities for chance constrained linear programming, including transportation problem and knapsack problem. By incorporating the branch-and-cell method proposed in this project, the branch-cell-cut method will be designed for solving chance constrained linear programming with large-scale scenarios efficiently. The output of this research will advance optimization theory and methodologies of chance constrained programming problems with finite discrete distributions.

参数具有随机性的优化问题在工程、管理和金融等领域具有广泛的应用. 利用机会约束处理参数的随机性是不确定环境下的一种常用建模方法. 本项目旨在系统和深入地研究离散分布下带机会约束优化问题的理论和分支-胞元算法. 项目将针对离散分布下机会约束的特殊性, 建立该约束与离散几何中超平面的胞元的联系, 并研究利用离散几何中的胞元枚举法求解离散分布下带机会约束的优化问题. 在此基础上, 本项目将结合整数规划方法与胞元枚举法, 建立针对离散分布下带机会约束问题的分支-胞元算法. 我们也将研究离散分布下带机会约束问题的多项式可解类. 针对线性规划的特殊性, 本项目拟构建离散分布下带机会约束运输问题及背包问题的强有效不等式, 并结合本项目提出的分支-胞元算法, 设计分支-胞元-割算法, 以快速有效解决大规模样本下带机会约束的线性规划问题. 本项目的研究成果将推动离散分布下带机会约束问题的理论和算法的发展.

本项目经过四年的研究，基本实现了项目立项时的研究目标，对项目立项时的研究内容进行了重点研究。 本项目在四年的研究中主要集中在离散分布下带机会约束问题的理论及算法研究，主要研究内容有：.（1）.整数规划方法和胞元枚举法的结合以及分支-胞元算法研究。.（2）.离散分布下带机会约束问题的多项式可解类。.（3）.离散分布下带机会约束线性规划问题。.随着研究的深入，我们在项目的四年研究中还在下列与项目相关的扩展方向进行了研究：.（4）.整数规划方法在供应链网络体系的应用研究。.（5）.次序（低次序）优化问题的最优性条件和复杂性。.（6）.带连续变量或基约束的二次规划问题的MIQP变换。.（7）.带二次约束整数二次规划问题的MIQP变换。.项目取得了一系列较高水平的研究成果。至结题，在本项目的资助下共发表（或在线发表，或录用）SCI/SSCI论文11篇，其中包括运筹与管理权威期刊SIAM Journal on Optimization, INFORMS Journal on Computing, Transportation Research Part B: Methodological等。获得上海市科技进步二等奖1项，申请发明专利2项。