|
|
-
Abstract
- This paper proposes a heuristic algorithm for solving the project selection problem under budget constraint. A decision criterion of net profit in conjunction with the techniques of searching the feasible range and the reduced candidate set is applied to obtain better heuristic solution and to minimize the computation effort. Six cases with different data variances are tested using the algorithm, and results show that the approach proposed can produce near-optimal solution efficiently.
- Keywords:
- Project, feasible range, reduced candidate set, NP-complete.
-
I. INTRODUCTION
- The selection and priortization of projects from feasible candidates is a critical issue to achieve organization's objective. Traditional approaches used net present value (NPV), internal rate of return (IRR), or payback period to rank project candidates. The NPV method suggests that the project
with the highest net present value should be selected. The IRR method chooses the project with the largest internal rate of return that is higher than the firm's expected rate of return. The payback period, on the other hand, searches for the project with the shortest payback period. Among the three most common methods, the payback period is believed to be the least reliable approach and, therefore, it should be used only on a referential basis.
- Apparently, the selection of project using the above methods is not a difficult task, many commercial packages can be used to help ease the decision process. However, when several projects with known cost and profit are to be selected under a budget constraint, and the objective is to maximize the total profit, then the problem becomes much complicated.
- Consider the project selection problem in Equation (1), if we try all possible combinations of the item selections to decide the optimal solution, we may need O(2n) computation time in the worst case. Obtaining the optimal solution is very expensive and intractable. Thus, developing a heuristic algorithm which provides near-optimal solution and takes nonexponential time becomes necessary.
- Before searching the optimal solution set, if the solution space can be tighten to certain feasible range, the computing time can be significantly reduced. Fortunately, two major improvements can be made from the data set. Firstly, using the available budget and the given cost of each project, we can constrain the feasible range (CR), alternatively, we can constrain the number of projects to be selected, in stead of conducting all possible search on the range of [0, n]. Secondly, after the feasible range is determined, we can reduce the candidate set (RCS) through a linear search algorithm [3] or the variable dominant matrix [4]. Moreover, consider Equation (1) again, if the decision variables xk is selected (xk=1), then it will cost ck from the budget and add the performance contribution pk to the objective function. Obviously, it would be more meaningful to use the "net profit", (pk-ck) as the decision criterion, rather than the profit-to-cost ratio (pk/ck). The purpose of this paper is to use the net profit pk-ck as the performance contribution to the objective function, and then employ the dominant matrix to reduce the candidate set. It can be seen that the proposed algorithm can assist the decision maker in selecting the projects.
-
II. HEURISTIC ALGORITHM
- Mathematically, the problem of project selection under budget constraint can be expressed as follows:
 (1)
Subject to:
 (2)
xk = 0 or 1
- where k is the project number,
- pk and ck indicate the profit
and cost of each project,
- B is the budget constraint.
- The project selection problem is a simple and interesting discrete programming, even with one constraint, it is already NP-complete. In other words, it takes O(2n) computation time to decide the optimal solution in the worst case. Thus, heuristic algorithm that yields near-optimal solution but consumes non exponential time should be searched. Using multiple criteria to produce a candidate set, supplemented by a technique to further squeeze the feasible range can be a possible approach. Generally, the index that can precisely relate the cost and profit is able to produce better heuristic solution. One of the criteria based on the concept of linear programming is the ratio between profit and cost, i.e. rk = pk/ck. However, even if divisibility is allowed, sorting by rk does not give optimal solution in the project selection problems [4]. This can be easily realized from the fact that two rk of the same value will be viewed as two equally acceptable candidates, while the difference between the profits resulting from each project can be quite significant. In addition, the project selection problem is to make decision of selecting either all (selected) or nothing (not selected). Using rk to measure the fraction of the contribution does not capture the intrinsic nature of the problem. Another linear search algorithm based on the nondecreasing order of ck or the nonincreasing order of pk also cannot give the optimal solution, although an exceptional example can always be constructed. Instead of the one-way linear search, observing two criteria jointly, such as rk and ck, rk and pk, or pk and ck, one can conduct the two-way linear search. Unfortunately, the optimal solution is still not guaranteed. Practically, from the perspective of maximizing the surplus, the maximized net profit, which is the cost subtracted by the profit, i.e. (pk - ck), may frequently be the actual goal of the decision makers. Thus, it will be used as the criterion in this study to improve the heuristic solution.
- To reduce the problem, the candidate set can be divided into three parts: selected set (SS), excluded set (ES), and remaining candidate set (RCS), and n = SS + ES + RCS, where SS and ES contains projects that will be certainly selected and excluded respectively, and RCS is composed of the remaining projects that cannot be surely decided. In stead of searching the complete enumeration, the method that maximizes the selected set and excluded set is able to significantly reduce the computation time. Thus, the feasible range [L, U] indicating the number of projects that can be possibly selected must be first determined, where L is the expected minimum number of projects, and decided by the nondecreasing order of ck, and U is the expected maximum number of projects, and obtained from the (pk - ck) sorted by the nonincreasing order. Using the feasible range and the dominant matrix, the selected set and excluded set can be easily determined. The problem is therefore dramatically reduced. Summarily, the following algorithm can be derived:
- Algorithm:
- Determine the value of (pk - ck) of each project.
- Sort (pk - ck) by the nonincreasing order
to obtain L when
- Sort ck by nondecreasing order to obtain U when
- Construct the dominant matrix in such a way that project k is said to dominate project j if and only if (pk - ck) > (pj - cj) and ck < cj . Let WIN(k) and LOSS(k) denote the number of projects that project k dominates and been dominated respectively.
- Obtain the selected set and excluded set using results of steps 2, 3, and 4. project k is in the selected set if WIN(k) (n - L), and in the excluded set if LOSS(k) U.
- Construct another dominant matrix to compare the remaining candidate set, the optimal solution is then reduced to the enumeration of C(RCS, m - SS), where m is a value in [L, U].
-
III. NUMERICAL EXAMPLE
- Suppose that 15 projects are to be selected within the 1500 budget constraint (see Table 1), Using steps 2 and 3 of the algorithm, the feasible range can be obtained as [1, 2]. In other words, only one or two projects should be selected. Combining feasible range with dominant matrix shown in Table 2 yields the three partitioned sets: SS = {f}, ES = {3, 4, 5, 6, 7, 9, 10, 11, 13, 15}, and RCS = {1, 2, 8, 12, 14}. Therefore, it needs only C(5, 1) + C(5, 2) = 15 choices from RCS to reach the optimal solution
in stead of the enumeration of 215 = 32768, which means 15/32768 = 0.04577 % of the computation time considering all possible combinations. This is obviously a significant saving. The optimal solution of the problem is {8, 12} with 7581.
|
|
Project k |
cost ck |
profit pk |
pk - ck |
|
1 |
518 |
3219 |
2701 |
|
2 |
689 |
3749 |
3060 |
|
3 |
1133 |
2721 |
1588 |
|
4 |
705 |
2607 |
1902 |
|
5 |
1121 |
2940 |
1819 |
|
6 |
1115 |
2674 |
1559 |
|
7 |
1826 |
3600 |
1774 |
|
8 |
643 |
3676 |
3033 |
|
9 |
1997 |
3358 |
1361 |
|
10 |
1100 |
2646 |
1546 |
|
11 |
740 |
1576 |
1836 |
|
12 |
832 |
3905 |
3073 |
|
13 |
1097 |
1642 |
1545 |
|
14 |
541 |
2936 |
2395 |
|
15 |
1062 |
4016 |
2954 |
|
Table 1. N=15, B = 1500 (Case 1)
|
|
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
WIN |
|
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
10 |
|
2 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
10 |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
4 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
8 |
|
5 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
|
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
8 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
10 |
|
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
11 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
7 |
|
12 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
|
13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
14 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
9 |
|
15 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
7 |
|
LOSS |
0 |
0 |
9 |
4 |
8 |
8 |
9 |
0 |
14 |
8 |
5 |
0 |
8 |
1 |
3 |
|
|
Table 2. Dominant Matrix of Case 1
|
-
- To further verify the performance of the algorithm, five other cases with different data variances are experimented. Table 3 shows the results of the feasible range, partitioned set, and the computation time. It can be seen that four out of the six cases (cases 3, 4, 5, 6) produce feasible range with L = U. This is of great advantage since no further reduction of the range is necessary. Examining the partitioned sets, one can find that the
remaining candidate set (RCS) of each case is significantly reduced, the RCS is even contracted to a null space for cases 5 and 6.Due to the fact that the proposed approach tends to form large selected and excluded sets, the computation efforts are thus economically limited to the minimum. Only a very small percentage of the exhaustive computation time is required for each case to reach the optimal solution, cases 5 and 6 can
even yield optimal solution right in the first iteration. However, the heuristic method does sacrifice the optimality for efficiency. project 2 and project 16 in cases 3 and 4 are excluded respectively. Besides these two instances, the optimal solutions of the four cases are reached efficiently.
|
|
n |
[L,U] |
Partitioned Sets |
% of Exhaustive Time needed |
Optimal Solution |
|
15(C 1) |
[1, 2] |
SS = {f} RCS = {1, 2, 8, 12, 14} |
0.04577 |
{8, 12} |
|
20(C 2) |
[3, 4] |
SS = {3} RCS = {1, 4, 6, 7, 8, 17, 19, 20} |
0.008 |
{3, 6, 7, 8} |
|
23(C 3) |
[12, 12] |
SS = {1, 4, 7, 8, 11, 12, 13, 14} RCS = {5, 15, 17, 18, 20, 21, 23} |
0.00041 |
{1, 2, 4, 5, 7, 8, 11, 12, 13, 15, 17, 18} |
|
28(C 4) |
[3, 3] |
SS = {f} RCS = {3, 5, 13, 15, 17, 25, 26, 27} |
0.00002 |
{15, 16, 17} |
|
28(C 5) |
[27, 27] |
SS = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27} RCS = {f} |
optimal |
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27} |
|
37(C 6) |
[31, 31] |
SS = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30, 31, 36} RCS = {f} |
optimal |
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30, 31, 36} |
|
Table 3. Results of Experimented Cases
|
-
IV. CONCLUSION
- An efficient heuristic algorithm for solving the project selection problem under budget constraint has been presented in this study. The net profit is used as the decision criterion to reflect the actual goal of the decision makers. The performance of the algorithm is justified by experimenting the computation time.. It is observed from the results that the algorithm developed produces very small feasible range. In particular, the upper and lower bounds of four cases are found to be the same value. This is advantageous since further reduction of the range is not necessary. Additionally, the remaining candidate set is lessened to the possible minimum, the extra computation time is therefore drastically reduced. It is believed that the algorithm is robust enough to efficiently produce better heuristic solution.
REFERENCES
- Nemhauser, G. L. and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiely & Sons Publishing Company, 1988.
- Bjorndal, M. H. et al. Some thoughts on Combinatorial Optimisation, European Journal of Operational Research, Vol. 83, pp253-270, 1995.
- Yang, C., Link Enhancement Using Constrained Range and Reduced Candidate Set Searches, Computer Communications, Vol. 15, No. 9, pp 573-580, 1992.
- Yang, C. and R. Y. Lin, Budget Management of Network Capacity Planning by Searching Constrained Range and Dominant Set, IEEE Journal on Selected Areas in Communications, Vol. 12, No. 6, pp1031-1038, 1994.
- Martello, S. and P. Toth, Knapsack Problem: Algorithms and Computer Implementations, Wiley, Chichester, U.K., 1990.
- Balas E. and E. Zemel, An Algorithm for large zero-one knapsack problems, Operation Research, Vol. 28, pp1130- 1154, 1980.
-
About the author
- Dr. Wei received Ph. D. Degree in Engineering Management from University of Missouri-Rolla, USA. He is now an Associate Professor in Department of Industrial Engineering and Management in Chung-Hua Polytechnic Institute, Hsin-Chu, Taiwan. Dr. Wei published papers in Journal of Advanced Manufacturing Technology, Journal of Computer and Industrial Engineering, Journal of Integrated Manufacturing Systems, Industrial Robots, and Journal of Computer Integrated Manufacturing. His research areas include manufacturing engineering, project management, and R&D management. Dr. Wei is the author and coauthor of several books.
|
|
