A Comparison of Surrogate Relaxations for a Capital Budgeting Model - Costa, A.; Paixão, J.P (11th International Conference on Computational Management Science, 2014)
Contingent claims analysis can be used for project evaluation when the project develops stochastically over time and the decision to invest into this project can be postponed. In that perspective, a scenario based capital budgeting model that captures risk uncertainty and managerial flexibility, maximizing the time-varying of a portfolio of investment options has been presented in the literature. With that linear integer programming model, one determines the project value but, also, one discerns when to exercise the option to invest. Specifically, the option to postpone an investment is exercised if such decision yields a value larger than the value of immediate exercise. Since the value of each project is estimated by the binomial option pricing approach, the number of variables of the corresponding linear integer program is straightforwardly related to the number of states in the binomial tree which grows exponentially with the number of projects and the number of periods. According to our experience, the linear integer problem turns out to be computationally quite intractable even for a small number of projects or a reduced number of periods. Hence, we present and discuss surrogate constraint relaxation approaches for the problem that lead to the determination of upper bounds for the optimal value of the problem. In each surrogate relaxation, a surrogate constraint represents a weighted nonnegative linear combination of the constraints of the original model. We derive and computationally test several of rules for initializing and updating the constraint weights associated to the surrogating process. In order to determine lower bounds for the optimal value of the problem, the optimal solution of the surrogate relaxation is used to guiding a greedy-type heuristic procedure for building up a feasible solution for the problem. For comparing the surrogate relaxation approaches, computational experience is carried out for a set of test instances previously considered in the literature.