Benders decomposition algorithm for multi-project portfolio selection

LI Xingmei, ZHONG Zhiming, ZHAO Qiuhong

Systems Engineering - Theory & Practice ›› 2018, Vol. 38 ›› Issue (11) : 2863-2873.

PDF(766 KB)
PDF(766 KB)
Systems Engineering - Theory & Practice ›› 2018, Vol. 38 ›› Issue (11) : 2863-2873. DOI: 10.12011/1000-6788(2018)11-2863-11

Benders decomposition algorithm for multi-project portfolio selection

  • LI Xingmei1,2, ZHONG Zhiming1,2, ZHAO Qiuhong3
Author information +
History +

Abstract

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.

Key words

project portfolio selection / project scheduling / mixed integer linear programming / Benders decomposition / large-scale optimization problem

Cite this article

Download Citations
LI Xingmei , ZHONG Zhiming , ZHAO Qiuhong. Benders decomposition algorithm for multi-project portfolio selection. Systems Engineering - Theory & Practice, 2018, 38(11): 2863-2873 https://doi.org/10.12011/1000-6788(2018)11-2863-11

References

[1] 中国2017年上半年创投报告:最"壕腾讯、阿里".[EB/OL]. http://www.sohu.com/a/198957758_169042.[2017-10-09].
[2] Taylan O, Bafail A O, Abdulaal R M S, et al. Construction projects selection and risk assessment by fuzzy AHP and fuzzy TOPSIS methodologies[J]. Applied Soft Computing, 2014, 17(4):105-116.
[3] Wu Y, Xu C, Ke Y, et al. An intuitionistic fuzzy multi-criteria framework for large-scale rooftop PV project portfolio selection:Case study in Zhejiang, China[J]. Energy, 2018, 143:295-309.
[4] Karasakal E, Aker P. A multicriteria sorting approach based on data envelopment analysis for R&D project selection problem[J]. Omega, 2017, 73:79-92.
[5] Jeng J F, Huang K H. Strategic project portfolio selection for national research institutes[J]. Journal of Business Research, 2015, 68(11):2305-2311.
[6] Arratia M, Lopez I, Schaeffer S, et al. Static R&D project portfolio selection in public organizations[J]. Decision Support Systems, 2016, 84(C):53-63.
[7] Fliedner T, Liesiö J. Adjustable robustness for multi-attribute project portfolio selection[J]. European Journal of Operational Research, 2016, 252(3):931-946.
[8] Hall N G, Long D Z, Qi J, et al. Managing underperformance risk in project portfolio selection[J]. Operations Research, 2015, 63:660-675.
[9] 王勇胜, 梁昌勇, 鞠彦忠. 不确定多期滚动项目组合选择优化模型[J]. 系统工程理论与实践, 2012, 32(6):1290-1297. Wang Y S, Liang C Y, Ju Y Z. Multi-phase rolling optimization model of project portfolio selection under uncertainty[J]. Systems Engineering-Theory & Practice, 2012, 32(6):1290-1297.
[10] 李星梅, 刘再领, 赵秋红. 可打断项目组合选择问题局部敏感性分析[J]. 系统工程理论与实践, 2016, 36(7):1816-1825. Li X M, Liu Z L, Zhao Q H. The local sensitivity analysis of project portfolio selection problem with divisibility[J]. Systems Engineering-Theory & Practice, 2016, 36(7):1816-1825.
[11] Sefair J A, Méndez C Y, Babat O, et al. Linear solution schemes for mean-semivariance project portfolio selection problems:An application in the oil and gas industry[J]. Omega, 2016, 68:39-48.
[12] Li X M, Fang S C, Tian Y, et al. Expanded model of the project portfolio selection problem with divisibility, time profile factors and cardinality constraints[J]. Journal of the Operational Research Society, 2015, 66(7):1132-1139.
[13] Li X M, Fang S C, Guo X L, et al. An extended model for project portfolio selection with project divisibility and interdependency[J]. Journal of Systems Science & Systems Engineering, 2016, 25(1):119-138.
[14] Jafarzadeh M, Tareghian H R, Rahbarnia F, et al. Optimal selection of project portfolios using reinvestment strategy within a flexible time horizon[J]. European Journal of Operational Research, 2014, 243(2):658-664.
[15] Belenky A S. A Boolean programming problem of choosing an optimal portfolio of projects and optimal schedules for them by reinvesting within the portfolio the profit from project implementation[J]. Applied Mathematics Letters, 2012, 25(10):1279-1284.
[16] 陶莎, 盛昭瀚, 朱建波. 交互作用不确定下的项目组合选择鲁棒决策[J]. 中国管理科学, 2017, 25(4):190-196. Tao S, Sheng Z H, Zhu J B. Robust decision-making of project portfolio selection with uncertain project interaction[J]. Chinese Journal of Management Science, 2017, 25(4):190-196.
[17] CPLEX Optimizer[EB/OL]. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/.
[18] Gurobi Optimization[EB/OL]. https://www.gurobi.com/.
[19] Shariatmadari M, Nahavandi N, Zegordi S H, et al. Integrated resource management for simultaneous project selection and scheduling[J]. Computers & Industrial Engineering, 2017, 109:39-47.
[20] Yu L, Wang S, Wen F, et al. Genetic algorithm-based multi-criteria project portfolio selection[J]. Annals of Operations Research, 2012, 197(1):71-86.
[21] 杨颖, 杨善林, 胡小建. 基于战略一致性的新产品开发项目组合选择[J]. 系统工程理论与实践, 2014, 34(4):964-970. Yang Y, Yang S L, Hu X J. New product development project portfolio selection based on strategic fit[J]. Systems Engineering-Theory & Practice, 2014, 34(4):964-970.
[22] 寿涌毅, 王承超, 李盈, 等. 资源受限项目组合选择及调度的双层决策方法[J]. 系统管理学报, 2014, 23(4):489-494. Shou Y Y, Wang C C, Li Y, et al. Bi-level decision approach for resource-constrained project portfolio selection and scheduling[J]. Journal of Systems & Management, 2014, 23(4):489-494.
[23] Glover F. Surrogate constraint duality in mathematical programming[J]. Operations Research, 1975, 23(3):434-451.
[24] Li H L, Fang S C, Huang Y H, et al. An enhanced logarithmic method for signomial programming with discrete variables[J]. European Journal of Operational Research, 2016, 255(3):922-934.
[25] Lu H C. Improved logarithmic linearizing method for optimization problems with free-sign pure discrete signomial terms[J]. Journal of Global Optimization, 2017, 68(1):95-123.
[26] Li X M, Huang Y H, Fang S C, et al. Reformulations for project portfolio selection problem considering interdependence and cardinality[J]. Pacific Journal of Optimization, 2016, 12(2):355-366.
[27] Fontaine P, Minner S. Benders decomposition for discrete-continuous linear bilevel problems with application to traffic network design[J]. Transportation Research Part B:Methodological, 2014, 70(70):163-172.
[28] Oliveira F, Grossmann I E, Hamacher S. Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain[J]. Computers & Operations Research, 2014, 49:47-58.
[29] Ye H, Li Z. Robust security-constrained unit commitment and dispatch with recourse cost requirement[J]. IEEE Transactions on Power Systems, 2016, 31(5):3527-3536.
[30] Sherali H D, Fraticelli B M P. A modification of Benders' decomposition algorithm for discrete subproblems:An approach for stochastic programs with integer recourse[J]. Journal of Global Optimization, 2002, 22:319-342.
[31] Lofberg J. YALMIP:A toolbox for modeling and optimization in MATLAB[C]//IEEE International Symposium on Computer Aided Control Systems Design, IEEE, 2005:284-289.

Funding

National Natural Science Foundation of China (71772060, 71471006)
PDF(766 KB)

566

Accesses

0

Citation

Detail

Sections
Recommended

/