In this talk, one presents and discusses surrogate constraint relaxation procedures for an integer programming model addressing the investment decision making relatively to a portfolio of projects, over a time-horizon and under a limited capital budgeting. Adopting a scenario-based approach, that optimization model captures risk uncertainty and managerial ?exibility concerning the decision to invest. In concrete, using that linear integer programming model, one determines for each project the respective value and the time to exercise the option to invest in order to maximize the total amount expected and respecting the available budget. 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. Accordingly 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. In fact, the number of constraints grows exponentially with the projects and periods under consideration. Aggregating either constraints or decision variables, one drastically reduces the dimension of the instances, substituting the initial set of constraints by a much smaller set of surrogate constraints. Each surrogate constraint represents a weighted nonnegative linear combination of a speci?c set of constraints set from the original model. However, the corresponding optimal solution only provides an upper bound for the optimal value of the original problem. This drawback may be mitigated by a ”clever” 1 choice of the weights. Three surrogate relaxation procedures are developed for the problem. The ?rst one aggregates the constraints related to the projects maintaining the original budget constraints while the other two procedures additionally aggregate the budget constraints. The third one also considers an aggregation process of variables based on some properties of the binomial tree. We derive and computationally test di?erent rules for initializing and updating the constraint weights associated to the each 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. Computational experience is reported for a set of test instances previously considered in the literature, allowing a preliminary comparison between the three procedures.

--

Real options; Capital budgeting; Scenario-based optimization; 0-1 Integer programming; Surrogate Relaxation