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 = {p₁, .., p_n} for n projects, a cost vector C = {c₁, .., c_n} associated with a binary vector X = {x₁, .., x_n}, x_i = 1 if project i is selected; x_i = 0 otherwise, and a budget vector B = {b₁, .., b_m} defining the capital budget bounding the overall cost of selected projects x_i in X over m periods, the problem is to

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.

The datafiles can be downloaded here: multiple periods and single period.

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