ASSET DIVESTITURE STRATEGIES WITH RETURN ON EQUITY REQUIREMENTS Technical Report 83-8 James C. Bean Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 March 1983 Revised February 1984 Working paper, results not to be used or quoted without permission of author

ASSET DIVESTITURE STRATEGIES WITH RETURN ON EQUITY REQUIREMENTS James C. Bean Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 ABSTRACT Given a set of assets and projections of future income flows and potential sale values, traditional economic analysis can be used to determine the optimal divestiture time for each asset. However, if a certain level of return on equity must be met each year because of policy or directive from a parent organization, some assets may necessarily be sold at an uneconomic time so that capital gains can be used to meet the return requirements. This paper presents an integer programming formulation of this problem as well as a proven solution methodology. The assumptions of the model are taken from an application in the land development industry. The effect of such return constraints is discussed. Computational experience shows the unusual characteristic that computation time appears to decrease in problem size over a wide range of problem sizes for random problems with structure similar to the motivating example. A discussion of this phenomenon is included. 1. INTRODUCTION Many studies have appeared in the finance and operations research liturature on optimal portfolio management. This paper deals with a case when optimal portfolio strategies cannot be followed due to annual minimum return on equity constraints. Assets may need to be divested uneconomically to satisfy return on equity requirements imposed by policy or an outside force such as a parent organization. The objective of the asset holder is then to maximize profitability to the extent possible under these restrictions. The inclusion of return constraints makes this problem significantly more difficult. With the assumptions of this paper, the problem without return constraints can be solved by complete enumeration since the divestiture decisions for each asset are independent. With the return constraints included, it becomes a moderately difficult integer program. The remainder of this paper includes a section on model specification with subsections on assumptions, notation, formulation and parameter calculation. Following are sections on horizon effects and solution methodology. Next is a section on computation with subsections on computational characteristics of the problem and results of testing. A discussion of the effects of such return on equity constraints on net present value follows. The final section includes extensions, summary, and conclusions. 2. MODEL SPECIFICATION 2.1 Assumptions The assumptions of this model arise from an application in the commercial land development industry. 1

They are: 1) All asset potential value profiles are assumed to be known. This is a significant assumption, however, run times for most problems are small enough that many scenarios can be run to determine solution sensitivity to this data. 2) No assets must be sold to raise capital for more attractive investments. Aquisition of assets is dealt with outside of this model. The model is only concerned with divestiture of current holdings. 3) During each year, a specified dollar return on equity must be met. This return can be met by operating income from the assets and capital gains from selling the assets. Any excess return from one year cannot be carried to the next. These restrictions will be relaxed for part of the computational experiments so that their effects can be evaluated. 4) The discount factor is variable, but never greater than some upper bound strictly less than one. Assumption 1 is necessary for use of a deterministic technique such as that presented here. Assumptions 2 and 3 form the problem structure exploited here. Assumption 4 is only necessary for the horizon discussion in section 3. 2.2 Notation The parameters i and s index an asset sale choice. The parameter t is the running index of monetary flows. Parameters 1) d(t): discount factor in year t 2) d: upper bound on d(t) 3) h(t): return on alternative investments in year t 4) R(t): return requirement for year t in dollars 5) ri(t): potential book income from asset i in year t 6) pi(t): potential cash income from asset i in year t 7) b,,: potential book proceeds from selling asset i in year a 8) g9,: potential cash proceeds from selling asset i in year s 9) N: number of assets held at time 0 10) T: number of years in the study horizon Decision Variables 1) zi,: has the value 1 if asset i sold in year a, 0 otherwise Note that the model allows for separate profiles of return, or so called book value, and actual cash. Typically the return constraints deal with the book values whereas the profit calculations are done with the cash figures. If in some particular application no such distinction is necessary, simply replace r,(t) with p,(t) and bi, with gj, everywhere in the model. 2.3 Formulation The definition of the decision variables above describes much of the modeling approach taken here. For each asset held at the beginning of the study there are T -+- 1 possible decisions. The asset can be sold in year

1,2,..., T or, as choice T + 1, can be held through the end of the study. An asset may be sold during the study for either of two reasons: it is economic to do so, in which case traditional analysis would have indicated the same divestiture strategy; or to satisfy return constraints. The model can be stated mathematically as follows: T+1 N maximize E EZ cf,. T+1 N subject to: E E au,(t)z>R(t) for t 1,2,..., T 8=1 i=1l T+1 i z. =1 for i =1,2,...,N,=1 zi, {O, 1} for all i, a where ci, and ai,(t) are defined below. The first set of constraints are the yearly return requirements. The second set insure that exactly one of the viable options is chosen for each asset. The advantages of this formulation are discussed in section 4. 2.4 Calculating Parameters The objective coefficients must be built up taking into account the impact of each decision over the entire time horizon. The objective coefficients, ce,, involve discount factors, d(t), which may be calculated as appropriate to a particular application. Two possibilities are: a constant annual factor leading to d(t) = d', or could be built up from cost of capital rates. The values of c,, are calculated as follows. For each year before the sale, t < a, asset i contributes d(t)pi(t), discounted operating cash flow, to the discounted profit. During the year of sale, a, the contribution is d(s)[.5pi(s) + g,]. The.5pi(s) comes from an assumption that all sales are made mid-year and that operating profit occurs uniformly across the year. Any other typical assumption on the accounting of operating profit during the year of sale is permissible. It is assumed that any dividends paid or other adjustmients have already been made to gi,. For the years following the sale, t > a, a contribution is made since income from the sale can be invested elsewhere. This term is the opportunity cost of holding the asset. If h(t) is the return from other potential investments in year t, then the contribution to profit in year t is t-1 d(t)h(t)g,.[ I (1 + h())]. The product term is due to the assumed compounding of return from alternative investments. For notational ease, it is assumed that when the limits of any summation or product above are out of bounds that they take the obvious values. Finally, to calculate ci, for s = 1, 2,..., T sum these contributions for years 1 to T. For the case a = T + 1, the choice not to sell the asset during the study, czr(T.1) includes d(t)pi(t) for t - 1, 2,... T plus d(t)gi. This last term is an estimate of the value of the asset not sold. This is similar to salvage value in an equipment replacement problem and is discussed in the section on horizon effects. 3

Calculation of the general constraint coefficients is similar, though book values are used rather than cash values. Here note that t indexes the constraints as there is one minimum return constraint for each year t = Il 2,..., T. For t < J, a,,(t) = r,(t), the book operating income. For the year of sale, t = a, ao,(, a).5r,(z) + bu. Following the sale, t > a, t-1 a.(t)= h(t)bi[ I (1 + h())]. ' -t 1 It is assumed that bi, is nef proceeds and that any necessary adjustments have been made to this value. For the case a = T + 1, a,+l)(t)= ri(t) for t = 1,2,..., T. 3. HORIZON EFFECTS As with any dynamic optimization problem, the study horizon, T, must be chosen carefully to avoid contamination of early decisions by end-f-study effects. These difficulties can arise because the model believes that the world is coming to an end at time miT. This problem is partially alleviated by adding salvage values to the objective coefficients for variables representing the choice not to sell some asset during the study. These values, however, are simply approximations of the actual salvage values which would take into consideration the return constraints for years beyond the chosen horizon. This accurate salvage value is exactly the optimal value to an infinite horizon problem from year T to infinity, which cannot be determined in a problem this general. It is impossible to eliminate the end-of-study problem completely. However, if these effects can be confined to decisions far in the future the immediate decisions can be implemented without loss. The model will be rerun with updated data before the future decisions are implemented. Results from Bean and Smith [1984] can be used to show that a forecast horizon exists for this problem for almost all interest rates. That is, there is a time far enough off that planning to that time or beyond is sufficient to eliminate end-of-study effects from at least the first decision. To use the results in Bean and Smith [1984] we must satisfy several assumptions. First, there must be only finitely many choices available at any specific time in the infinite horizon problem (clearly the case here). Second, we must sufficiently discount the objective values over time. For this problem sufficiently means any d < 1 (interest rate > 0). Finally, we need to know that the set of potentially optimal infinite horizon strategies is at most countably infinite. Such is the case here since each asset can be sold at countably many times (s = 1, 2,...). Then the total strategy space is a finite cartesian product of countable sets and hence is countable. The result is then: Theorem: For almost all discount factor sequences, there is a unique optimal infinite horizon strategy. Moreover, for any L in [1,2,...] there exists a time far enough off that using a problem horizon, T, of that time or beyond, the solution to the finite horizon problem to T agrees with the optimal infinite horizon strategy for all decisions in years 1, 2,..., L. (Almost all means outside of a set of measure zero.) Proof: See Bean and Smith [1984]. Corollary: As a special case with L = 1 there is a forecast horizon. The existing algorithmic results are not general enough to cover this problem. We know that there is a forecast horizon, but cannot verify that we have found it computationally. The difficulty arises from the fact 4

that at any time the system could be in any of 2N states (sold or not sold for each asset). The problems where algorithmic results are common have few states other than time. (This "curse of dimensionality" also explains why the problem was not formulated as a dynamic program.) In the application motivating this study we have used sensitivity analysis on the end-of-study to convince ourselves that the study horizon is long enough. Computing a forecast horizon for this problem is left to future research. 4. SOLUTION METHODOLOGY The integer program above has a structure known as the Multiple Choice Integer Program. This problem has been discussed often in the recent literature (see Bean [1982], Sweeney and Murphy [1980], Martin [1980], Martin, Sweeney and Doherty [1982]). There have also been several successful applications of this structure to a wide variety of problems such as catalogue space planning (Johnson, Zoltners and Sinha [19791) and sales resource allocation (Zoltners and Sinha [1980]). One of the exceptional characteristics of this problem arises from the fact that an asset sale at mid-study affects the return profile for all years of the study; before, during and after the sale. As a result, the constraint matrix for the general constraints of this problem when modeled as a Multiple Choice Integer Program is 100$% dense. This constrained divestiture model is an excellent example of the Multiple Choice Integer Program in that no structure is left unexploited. This formulation has advantages over other possible techniques. As mentioned above, the state space is so complex that dynamic programming is inefficient. The Multiple Choice Integer Program has advantages over general integer programming formulations because it takes advantage of the special structure this problem exhibits. The branch-and-bound tree used for this problem has the characteristic that going forward from any node corresponds to fixing all of the variables associated with one asset; one at 1 and the others at 0. In a general binary tree only one variable would be fixed at a time. Conceptually, this approach reduces the problem from N(T + 1) decisions to N. In the general tree there are 2N(T+1) branches, whereas, the tree employed by the solution technique described below has only (T + 1)N. Hence, the number of potential solutions when the problem is solved with this algorithm increases exponentially in the number of assets, but only polynomially in the study horizon. The solution technique used in this application is that described in Bean [1982]. This is a branch-andbound approach using a branching technique especially designed for Multiple Choice problems. This basic procedure is then enhanced two ways. The variable reduction techniques of Martin, Sweeney, et. al. are used to eliminate variables from consideration a priori. Then, a Lagrangean version of the problem is solved that greatly speeds up the computation times. The result of this Lagrangean approach is a heuristic algorithm that in general has been shown to exhibit only 2-3% error. In this application the upper bound on error is on the order of.5% for sufficiently large problems. The Lagrangean problem solved is not a Lagrangean relaxation, but a Lagrangean alteration of the costs. The feasible region is kept in tact, but the general constraints are relaxed into the objective as well. The resulting formulation is the same as that presented above, with the exceptions that the term T T+1 N E x(t)[ E ~""(t)z. - R(t)] t=l - #1 ~=1 is added to the objective and the constraints X(t)20 are included. The factors {X(t)} are parameters calculated by the routine to alter the objective with least possible error. For details on these values see Bean [1982]. 5

This Lagrangean alteration significantly improves the computational efficiency of the algorithm in the following manner. The branch-and-bound routine chooses nodes by lowest cost. After altering the costs as described above the new costs reflect both actual cost and contribution toward feasibility. Near optimal solutions are then discovered very early in the process. Though altering the costs produces a slightly different problem resulting in the small errors mentioned above, the system is quite good at reporting bounds of the error. Since no relaxation is done, the solution to the altered problem is feasible in the problem of interest. Only the complementarity of the Lagrangean term must be investigated. For details on Lagrangean approaches to integer programming problems see Fisher [1981]. 5. COMPUTATION 5.1 Computational Characteristics The asset divestiture problems discussed here may have large duality gaps leading to difficult computation. Typically the operating return is nearly enough to cover the return requirements. To make up the small remainder an asset must be sold. Since the book proceeds on most assets are large relative to the remaining required return, the return requirements are over satisfied by a great margin. This may lead to a large duality gap. This difficulty is accentuated when the number of assets is not large relative to the model horizon. To further complicate computation with a branch-and-bound routine, divestiture problems often have many near optimal solutions. This makes bounding routines inefficient at fathoming sub-problems. This can be partially overcome if the discount factor is not very near 1 (a characteristic that also serves to shorten forecast horizons). Because of these characteristics and the fact that the number of branches in a Multiple Choice Integer Program tree for this problem increases exponentially in the number of assets, it was expected that the number of assets that the model could solve would be limited. To determine this limit, testing of randomly generated problems of several sizes was carried out. The specifics of these tests are reported in the next section. These tests presented some unusual results. While the computation times increased in horizon length, the solution times appear to decrease, over a wide range of problem sizes, as the number of assets is increased. When the number of assets is not large compared to the number of years in the model horizon, the problem becomes highly constrained. The effect of the return constraints is extreme leading to large duality gaps. When the number of assets is large, the greater flexibility available to the model allows it to quickly find very good solutions. The duality gaps are reduced so that the LP-based bounding and sub-problem ordering characteristics of the algorithm in Bean [19821 quickly verify optimality (to the Lagrangean problem). It appears that for data in the ranges of that found in the land development industry problem solved, it is necessary to have at least three assets in the model for each year to be studied for the algorithm to be at its most effective. 5.2 Computation Results To test the algorithm described here, a sequence of hand picked random problems was solved. The problems were not generated completely at random, but given an actual problem, all data were randomly varied to obtain the set of problems. Each value of r,(t), pi(t), b6,, and g,, was multiplied by a random scaling factor that was uniformly distributed over the interval [.8, 1.21. That is, each value was varied a maximum of 20% from the actual application value. The random factors were generated independently for each piece of data. Also, the return requirements were scaled according to the number of assets in order to keep requiremente/asset comparable as the problem sizes were increased. 6

Five randomly generated problems were solved for each cell consisting of a four or five year horizon and 10, 15, 20, or 25 assets. Hence, these computational results represent 40 test problems. Table 1 shows the average CPU time over the five random problems for each combination of horizon and number of assets. The times are in seconds on the University of Michigan Amdahl 5860 with MTS operating system. Table 2 gives the average number of branEh-and-bound interations for the five problems in each cell. This represents the number of sub-problems analyzed during the problem solution. Table 3 gives the average bound on error due to the Lagrangean term. 6. EFFECTS OF RETURN CONSTRAINTS Requiring a certain return on equity each year may or may not effect the net present value of the portfolio. If the assets turn over in a short period of time, as in a retail establishment, annual return constraints would likely have little or no effect. Constraints of this type come into play where the typical turn-around time of each asset is long, as in the land development industry. The questions that arise are: 1) How large an impact do the constraints have? 2) What can be done to minimize this effect? 3) Should such constraints be imposed? The model presented here can shed some light on the first two questions. The third involves much larger issues and will be merely commented on here. Each of the 40 problems above was rerun with all return constraints relaxed and the resulting values compared with results of the constrained problems. Due to the fact that exact solutions to the constrained problems were not found, the exact loss due to imposing the constraints could not be calculated. However, bounds are available. Table 4 shows upper and lower bounds for the loss due to return on equity constraints for the 40 problems, expressed a percentage of the unconstrained optimum. Note that the loss decreases sharply as the number of assets is increased. It appears that the greater flexibility afforded by more assets not only aids in computation, but partially offsets the effects of the return constraints. Returning to the questions posed above, the impact of the return constraints varies greatly as the problem parameters are varied. In most cases there is some loss. The effects of the return constraints can be minimized by increasing the flexibility of the divestiture decision. This can be done in two ways. First, assets can be added to the portfolio. However, this is not often a simply altered control variable. Alternatively, the assets can be divided into fractional interest. For example, each half interest in a development project can be regarded as a separate asset. Whether or not such constraints are desirable involves larger issues than maximizing net present value of the portfolio. Though it appears that such constraints do cost the investor net present value, if the net present value optimal investment strategy returned nothing for the first several years, this may not be considered effective portfolio management regardless of high future expectations. In such cases the minimum return on equity requirement may be a surrogate for judgement criteria not represented by net present value. 7. EXTENSIONS AND CONCLUSIONS 7.1 Extensions 7

The only constraints dealt with in this paper are the minimum return on equity constraints. The model in Bean [1982] can handle any other constraints that can be formulated in these variables as linear inequalities or equalities. For example, at times this model included the constraint that no asset be sold at a book los's. The addition of constraint will have some effect on the computational efficiency of the algorithm. How great an effect is dependent on the specific constraint. The implied assumption that an asset must be sold in tact can be easily relaxed. In the commercial land development industry it is possible to sell fractional interest in an asset, typically a half or third. This is easily accomplished by considering each fraction of interest as a separate asset. Though this adds to the size of the problem, the computational results above indicate that it may actually improve computation. This also appears to reduce the effect of return on equity constraints. In its full generality this model and solution technique are applicable to many asset divestiture problems other than the land development example that was the basis for this work. The model can be used to analyze the deterministic version of many divestiture problems with constraints linking the divestiture decisions. The qualitative consclusions of this paper cannot be transferred without consideration, but it is conjectured that they are fairly robust. 7.2 Summary and Conclusions The problem of determining optimal or near-optimal divestiture strategies for a portfolio of assets is made significantly more difficult by the addition of minimum return on equity constraints. This more difficult problem can be formulated as a Multiple Choice Integer Program. The procedure presented in Bean [1982] can then be applied to solve the model. The formulation of this problem has several interesting computational characteristics. The general constraint matrix is 100% dense and large duality gaps are common. However, the computation times presented here for hand picked random problems decrease as the number of assets in the model is increased. This is due to the greater flexibility afforded the model in satisfying the return constraints leading to smaller duality gaps. We conjecture that the computation time will decrease to a lower bound of the time to solve the L. P. relaxation, and then increase with it linearly. Finally, many extensions of the model presented here are possible making it applicable to problems in industries other than commercial land development. Acknowledgements I would like to thank Gary Salton and Brad Neuman of the Homart Development Co. for introducing me to this problem and affording me the opportunity to study it. 8

REFERENCES Bean, J. [1982],"A Lagrangean Algorithm for the Multiple Choice Integer Program," Technical Report 82-14, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109. To appear in Operations Research. Bean, J. and R. Smith [1984],"Conditions for the Existence of Planning Horizons," Technical Report 81-8, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 48109. To appear in Mathematies of Operations Research, Vol. 9. Fisher, M. [1981],Lagrangean Relaxation Method for Solving Integer Programming Problems," Management Science, Vol. 27, pp. 1-18. Johnson, M., A. Zoltners and P. Sinha [1979],"An Allocation Model for Catalogue Space Planning," Management Science, Vol. 25, pp. 117-129. Martin, K. [1980],'Branching Strategies for Integer Programming with Special Ordered Sets," Presented at ORSA/TIMS National Meeting, Colorado Springs. Martin, K., D. Sweeney, and M. Doherty [1981],"The Reduced Cost Branch-and-Bound Algorithm for Mixed Integer Programming," Working Paper, Graduate School of Business, University of Chicago. Sweeney, D. and R. Murphy (1981],"Branch-and-Bound Methods for Multi-Item Scheduling," Operations Research, Vol. 29, pp. 853-864. Zoltners, A. and P. Sinha [1980],"Models for Sales Resource Allocation," Management Science, Vol. 2, pp. 242-260. 9

TABLE 1: AVERAGE CPU TIMES IN SECONDS # of Years 4 5 # of Assets 10.670 1.580 15 20 25 2.577.932.856.562.144.488 TABLE 2: AVERAGE BRANCH-AND-BOUND ITERATIONS # of Years 4 5 # of Assets 10 254.6 255.2 15 20 733.4 156.2 88.2 44.0 16.4 56.2 25 TABLE 3: AVERAGE BOUND ON OBJECTIVE ERROR # of Years 4 5 # of Assets 10 15 20 25 6.8% 0.3% 0.1% 0.1% 5.9% 0.3% 0.5% 0.1% TABLE 4: PERCENT LOSS DUE TO EQUITY REQUIREMENTS Upper Bound/Lower Bound # of Years 4 5 # of Assets 10 15 20 25 8.3%/2.5% 1.3%/1.0% 0.2%/0.1% 0.1%/0.1% 7.6%/2.7% 0.8%/0.5% 0.6%/0.1% 0.2%/0.1%