Heuristic algorithms for a capital budgeting problem with the option to defer - Costa, A.; Paixão, J. P. (Congresso da APDIO - IO 2017, 2017)
We present and discuss heuristic algorithms for the capital budgeting problem with the option to defer the investment decision (CBPD) where one deals with a set of projects candidates for investment over a time period and limited by a budget. The CBPD can be formulated as an integer linear programming model. The decision is taken in order to maximize the total amount expected and respecting the budget. The value of each project is estimated by an option pricing approach leading to a binomial tree which grows exponentially with the number of periods. Since the decision variables are associated to the leaves of the tree, the integer linear problem turns out to be computationally quite intractable even for a small number of projects or periods. Recently we presented a surrogate constraint approach providing upper bounds on the optimal value and sub-solutions that, through an heuristic procedure are made feasible for the CBPD producing lower bound values for the optimum. However, our computational experience shows that the quality of the feasible solutions is reasonably poor for the largest test instances. Hence, alternative heuristics should be considered for the problem such as those presented in this talk. Preliminary computational results are discussed. Keywords: Real options; Capital budgeting; Scenario-based optimization; 0-1 Integer programming; Surrogate Relaxation; Heuristic.