## Benchmark Datasets in Capital Budgeting

Problem Description

The basic model of capital budgeting problems is 0-1 multidimensional knapsack problems. Given a profit vector P = {p1, .., pn} for n projects, a cost vector C = {c1, .., cn} associated with a binary vector X = {x1, .., xn}, xi = 1 if project i is selected; xi = 0 otherwise, and a budget vector B = {b1, .., bm} defining the capital budget bounding the overall cost of selected projects xi in X over m periods, the problem is to

Max{PX: CXB, X = {x1, .., xn}, xi ∈ {0, 1}}

Two sets of problem instances in capital budgeting with a range of interdependencies constraints has been generated, with m = 1 and m > 1, details given in Table 1 and Table 2, respectively.

Table 1. Problem characteristics of single time period capital budgeting problem instances (m = 1). "x(y)" de-notes the number of corresponding constraints (x) and the number of projects involved (y), respectively, i.e. "2(2, 3) denotes two interdependencies, involving 2 and 3 projects, respectively". "-" de-notes an absence of the corresponding constraint.
 Problems p30_1 p30_2 p30_3 p30_4 p30_5 p30_6 p30_7 p30_8 p30_9 p30_10 No. of projects 30 30 30 30 30 30 30 30 30 30 Budget B 1412600 655200 979200 1207800 687900 802000 641700 995600 994600 1109400 Best NPV 5582140 3549600 4802600 5677000 3445220 3827950 3525280 5010060 4731830 5202060 Exclusive 2(2, 3) 2(2, 3) 2(2, 3) 2(2, 3) 1(2) 1(3) 1(2) 1(2) 1(2) 2(2, 3) Complement 2(2, 3) 1(3) 1(2) - 2(2, 3) 2(2, 3) 2(2, 3) 1(3) 1(2) 2(2, 3) Contingency 1(2) 1(2) 1(2) - 1(2) - 1(2) 1(2) - 1(2) Problems p50_1 p50_2 p50_3 p50_4 p50_5 p50_6 p50_7 p50_8 p50_9 p50_10 No. of projects 50 50 50 50 50 50 50 50 50 50 Budget B 170500 122100 207500 203800 158900 1738600 1589000 2091100 1376700 1860800 Best NPV 811320 613800 974800 888100 752000 8389900 8374000 9215700 6428660 7844660 Exclusive 2(2, 3) 2(2, 3) 2(2, 3) 2(2, 3) 1(2) 1(3) - 1(3) 1(2) 2(2, 3) Complement 2(2, 3) 1(3) 1(2) - 2(2, 3) 2(2, 3) 2(2, 3) 1(3) 1(2) 2(2, 3) Contingency 1(2) - 1(2) 1(2) 1(2) - 1(2) 1(2) 1(2) 1(2)

Table 2. Problem characteristics of multiple time period capital budgeting problem instances (m > 1). "x(y)" de-notes the number of corresponding constraints (x) and the number of projects involved (y), respectively. "-" de-notes absence of the corresponding constraint. For mknap1, only an average ratio of budget to the overall costs of all periods can be calculated due to the different budget limits in multiple periods.
 Problems mknap1_1 mknap1_2 mknap1_3 mknap1_4 mknap1_5 mknap1_6 mknap1_7 No. of projects 6 10 15 20 28 39 50 No. of periods 10 10 10 10 10 10 10 Best NPV 4140 8352 3940 6780 12080 14185 22155 Exclusive 1(2) 1(3) 2(2, 3) 1(3) 2(2, 3) - 2(2, 3) Complement 1(2) 1(2) 1(3) 2(2, 3) - 2(2, 3) 2(2, 3) Contingency 1(2) - 1(2) 1(2) 1(2) 1(3) -

### Selected Results

Table 3 Fitness distance correlation for single time period capital budgeting with and without interdependencies. "Infeasible %" denotes range of the percentage of infeasible solutions of 1-30/50 distance to the best know solu-tion. "Budget/all %" denotes the ratio between the capital B to the sum of costs required for all projects.
 Problems p50_1 p50_2 p50_3 p50_4 p50_5 p50_6 p50_7 p50_8 p50_9 p50_10 average Budget/all % 53 38 66 69 45 72 69 85 50 67 without fdc -0.49 -0.81 -0.42 -0.44 -0.62 -0.47 -0.46 -0.53 -0.52 -0.43 -0.52 s.d. 0.16 0.21 0.11 0.11 0.17 0.1 0.11 0.07 0.16 0.12 0.13 Infeasible % 30~49 48~98 1~25 1~27 44~83 1~20 1~29 1~13 42~63 1~31 with fdc -0.74 -0.87 -0.69 -0.69 -0.76 -0.6 -0.58 -0.7 -0.64 -0.71 -0.7 s.d. 0.19 0.17 0.16 0.16 0.17 0.13 0.13 0.15 0.18 0.16 0.16 Infeasible % 40~90 49~99 33~91 31~90 50~95 21~61 28~56 19~86 45~89 33~89 Problems p30_1 p30_2 p30_3 p30_4 p30_5 p30_6 p30_7 p30_8 p30_9 p30_10 average Budget/all % 80 44 65 89 41 50 41 67 66 74 without fdc -0.58 -0.66 -0.5 -0.6 -0.74 -0.59 -0.76 -0.5 -0.51 -0.5 -0.59 s.d. 0.1 0.22 0.14 0.99 0.18 0.16 0.18 0.14 0.12 0.12 0.24 Infeasible % 2~4 44~80 4~24 2~8 48~88 36~65 43~89 11~27 3~27 9~28 with fdc -0.83 -0.88 -0.75 -0.7 -0.74 -0.67 -0.79 -0.65 -0.51 -0.77 -0.73 s.d. 0.13 0.13 0.16 0.13 0.18 0.17 0.22 0.16 0.16 0.15 0.16 Infeasible % 19~87 44~95 33~88 12~73 48~88 40~84 46~96 30~74 19~37 26~88

Table 4 Fitness distance correlation for multiple periods capital budgeting with and without interdependencies
 Problems mknap1_1 mknap1_2 mknap1_3 mknap1_4 mknap1_5 mknap1_6 mknap1_7 average Budget/all % 73 72 71 57 74 67 63 without fdc -0.74 -0.63 -0.63 -0.61 -0.46 -0.43 -0.36 -0.55 s.d. 0.32 0.24 0.19 0.26 0.19 0.22 0.21 0.23 Infeasible % 41~65 31~63 24~42 50~66 15~45 23~45 27~49 with fdc -0.91 -0.64 -0.89 -0.76 -0.68 -0.50 -0.51 -0.70 s.d. 0.19 0.26 0.20 0.25 0.26 0.27 0.21 0.23 Infeasible % 71~84 52~71 36~93 50~90 42~91 28~76 30~80

Last updated date 10/June/2009