求解多项目组合选择问题的奔德斯分解算法

Benders decomposition algorithm for multi-project portfolio selection

随着我国经济的快速发展,项目组合选择问题所面临的待选项目集日益膨胀.而项目组合选择模型通常表示为整数规划或混合整数规划的形式,过多的待选项目会对项目组合选择模型的高效求解带来巨大的挑战.针对这一问题,本文研究了多项目组合选择模型的奔德斯分解算法.将原问题分解成仅考虑从待选项目集中选出最优组合的主问题与对已选项目进行排序的子问题,通过主子问题间的迭代逐步逼近最优解.通过算法性能分析,发现直接使用奔德斯分解算法存在着收敛速度慢,子问题不可行的缺点.为了加速算法的收敛速度,对主问题进行了修正,提出了一种利用潜在的最优项目及有效不等式改进主问题的新思路.最后,通过算例分析,对比了直接使用分支定界法与使用奔德斯分解算法两类求解方法的求解效率,验证了本文所提出方法的有效性与合理性.

With the rapid development of China's economic,the set of candidate projects in project portfolio selection is growing.Project portfolio selection models are usually formulated as integer or mixed integer programming.Too many candidate projects will pose a great challenge to efficient computation.To tackle this problem,this paper studies the Benders decomposition algorithm of project portfolio selection model.We decompose the original model into a master problem which only consider optimal project selection,and a subproblem which only considers the scheduling of selected projects.The optimal solution is approximated by the iteration between master problem and subproblem.The performance analysis of Benders decomposition algorithm shows that it suffers from the shortcoming of slow convergence and infeasibility of subproblem if we use benders decomposition directly.To accelerate the convergence,we modify the master problem by using potential optimal projects and valid inequations.Finally,we compare the solution efficiency of two different solution approaches,including branch and bound algorithm and Benders decomposition algorithm.The results show the capability and characteristics of the proposed algorithm.