Nonlinear Integer Programming: Algorithms and Applications
Bruce A. Murtagh
Macquarie Graduate School of Management
Sydney, Australia
Abstract
This paper describes recent efforts to incorporate integer programming capability within nonlinear programming algorithms. The structure of problems may be exploited in producing an integer feasible solution adjacent to a local continuous optimum. This solution can be accepted as near-optimal if it is sufficiently close in objective value to the continuous optimum, or else be used as an enhanced bound in a branch and bound procedure.
Application areas of current interest to which these algorithms have been applied include asset allocation models for portfolio management, and yield management with side conditions. Computational experience in the application of these models is discussed.
The focus of this paper is on developing and applying nonlinear integer programming algorithms to commercial situations where the need for integer capability is an important requirement of the model. The paper describes efforts to enhance convergence to a local integer feasible solution close (in some sense) to a local solution of the continuous relaxation of the problem.
The paper also proceeds to describe the application of such algorithms in two areas of current interest: asset allocation and yield management. For the asset allocation problem in funds management the objective is to minimise some (nonlinear) definition of risk, subject to the requirement that the expected return from the optimised solution exceeds a specified target return. There are other constraints as well, such as the requirement that the allocation of funds to each asset class satisfies upper and lower limits, and the change in funds allocated to a particular asset class in each time period be within a specified limit. There is also of course the requirement that the allocations in each class sum to the total funds available. The integer aspects of the model arise for a number of reasons, chief of which is the requirement for many asset classes that allocations are assigned in discrete amounts. There is also a minimum transaction level for some asset classes, so the investment is either zero or above a lower threshold; this situation can be handled effectively with an integer programming formulation. Finally, transaction costs can be somewhat complex, depending on the level of investment. Again, an integer programming formulation can be used to model these complexities.
Yield management is the task of deciding how to optimise the expected return from products which are perishable. In particular the nature of airline seats, hotel rooms, rental cars and other time-sensitive products is such that in the passage of time their value reduces abruptly to zero; once the flight has departed, or the day or night passes, the product no longer can be sold at all for that period. In endeavouring to sell more units by offering a discount, the problem arises of deciding how many units to protect at the full price for customers who are willing to pay it (and are assumed to book later than the discount customers). The problem grows in size and complexity with several levels of discount, however it is common practice to have multiple discount classes particularly in the airline industry. The integer aspects of the problem arise through the units protected for each discount class having to be a discrete number. Simple rounding may be adequate when there are a large number of units available in each class, but as the day of accommodation or flight departure gets closer there are only a small number of units available and the integer requirements become important.
The next section examines algorithmic approaches to nonlinear integer programming which incorporate existing large-scale optimisation capability. The discussion will also include some ramifications of nonlinearity in deciding a solution. The following section will describe applications in asset allocation models, and then there will be a section describing our experience with applying the algorithm to yield management problems, particularly when there are side conditions on the solution.
Much of the work described in this section has centred on efforts to extend the MINOS algorithm of Murtagh and Saunders [8] for large-scale nonlinear programming to include the capability of handling integer requirements on a relatively small subset of the total variables in the problem.
Early work on this endeavour is described in a paper by Murtagh [7] in which a direct search algorithm is developed exploiting the presence of "superbasic" variables which arise in nonlinear applications. These are extra variables over and above the standard "basic" variables in linear programming which achieve values away from their lower or upper bound at the solution. By rotating the integer variables into the superbasic set, and by expanding that set if necessary, they may be set at integer values as long as feasibility is retained.
This work is extended in a more recent paper by Murtagh and Sugden [10], in which a more advanced selection procedure is developed. The steps can be summarised as follows:
Not all these steps are straightforward, and more recent efforts have been in devising methods for overcoming contingencies such as the incoming nonbasic hitting its other bound before either a basic hits its bound (whether it is an integer variable or not) or a basic integer becoming integer-feasible.
This section describes an approach to asset allocation which focuses on downside risk as the objective to be minimised. To devise the best means of asset allocation among a number of sectors it is necessary to examine the patterns of growth of the accumulation indices in each sector and the variability in their performance; then optimise the allocation of assets to achieve a measured balance between risk and return.
The accumulation indices are analysed to build up a probability distribution of returns for each sector from the raw data. Also an appropriate forecasting model is developed to predict next-period returns.
Given the above information the optimisation task is to allocate assets to sectors to achieve a target level of return for the whole portfolio at minimum risk. Risk can be defined in many ways; in our work the preferred representation is one of downside risk i.e. minimising the likelihood of downside movement from expected value.
The raw data is in the form of accumulation indices reflecting capital gain and dividend reinvestment. Returns are measured by the relative movement of indices over each time period. The previous 52 time periods up until present time are measured. Rather than calculate the mean and standard deviation and assume a normal distribution for each sector, the actual distribution of returns is modelled. The variation from expected value is measured for each of the previous time periods and weighted exponentially in time to give maximum credence to recent time periods and minimal to the oldest. Each of these measures forms a separate constraint in the model.
In determining the likely performance of individual sectors for the next period in the future a state-space vector version of an auto-regressive integrated moving average forecasting technique is used [4],[11].
The most widely used measure of risk in asset allocation is variance, which is well known and forms the basis of the Capital Asset Pricing Model. As techniques of numerical optimization have improved, it has been applied to quite large portfolio analysis problems [6],[12]. However there are two fundamental difficulties with the mean-variance model:
The assumption that returns are normally distributed about the mean, and the required storage and calculation of a (usually dense) variance co-variance matrix.
Variance being used as a measure of risk equally penalises both upside and downside variation.
Other measures of risk have appeared in recent literature, including mean absolute deviation which does not require an assumption of normality [5],[13],[15]. The focus of the work described here is on downside risk, so the preferred risk measure is the negative semiabsolute deviation, which only measures the under-performance from expected value. A similar concept using variance would be the negative semi-variance and it is possible to choose this as a measure of risk as an option in the model.
A model (called ATLAS) has been developed which has one of the above expressions for risk as the objective function and target return as a constraint. Target return can be expressed as either an absolute return or a relative return above a defined benchmark portfolio. Other constraints in the model include upper and lower limits of holdings in each asset class, and also upper and lower limits of holdings in specified groups of asset classes, for example total equities and total growth assets (defined as equities and property). There are also move limits on transactions in any one period, and both buying and selling incur transaction costs.
The ATLAS model has been implemented on data for several markets. An Australian version includes five local equity classes, two direct property indices, local and international fixed interest (including CPI bonds), and several international equity classes as well as foreign 3-month cash holdings. There are similar localised versions for Japan, Malaysia and Singapore, and an international version which uses the Morgan Stanley Capital Indices for 32 countries. The model has been tested on monthly data starting from December 1979, particularly on the Australian version.
Numerical experience with the model has been obtained by assuming that an investor had only the data available up to the present day and a decision on allocation for the next period had to be based on this. The model uses information based on results from the previous 52 months, so predictions and allocations commence April 1984.
The performance of the model was compared with six other widely reported indices.
It has been a feature of results obtained with the model that the implementation significantly outperformed these indices; although it slightly under-performed domestic and foreign equities in the months leading up to the October 1987 crash.
The portfolio survived the 1987 crash with little loss of value and went on to draw away significantly from the other indices. The Australian All Ordinaries Index was the closest performer but showed markedly higher volatility than the portfolio index.
Another area where the problem to be addressed is distinctly nonlinear as well as integer is in yield management with side conditions. The objective function contains complex integrals representing the expected value of total revenue as a function of protection levels for the different discount classes. The complicating factor is the concept of "nested protection", where a customer in a higher cost class is not refused any unit as long as there are units available in any of the discount classes – it can be seen that this is much more realistic than simply dividing the total number of units into fixed allocations for each discount class.
Belobaba [1] examined the concept of nested protection in the airline industry, and developed a heuristic approach labelled the Expected Marginal Seat Revenue model. This compared the expected revenue to be gained from one more seat protected for the higher fare class versus allowing it to be sold at a lower fare.
Later, Brumelle and McGill[2], Curry[3], and Wollmer[14] presented independently the extension to optimal booking limits. Brumelle and McGill used continuous distributions and finally approximated the solution using multidimensional numerical quadrature. Their calculated protection levels are determined from the a set of simple equations based on the partial derivatives of the expected revenue function. Wollmer used a discrete distribution for the passenger demand and presented the optimal booking limit in terms of a convolution sum.
Curry used a continuous distribution and expressed his result in terms of a convolution integral.
Curry’s model for nested fare classes may be formulated as follows.
The expected revenue for class i plus the remaining i-1 classes, which have their booking limit reduced by the number who have booked in class i is:
Ri (IIi –1,A) = ò [ Firi + R i-1(IIi-2, A-ri)] p(ri).dri
+ [ Fi (A -IIi-1) + R i-1(IIi-2,IIi-1)] ò pi(ri).dri
Where,
IIo = 0, Ro = 0
Ri-1(P i-2, A) = Expected revenue of the remaining i-1 classes.
pi(ri) = Probability density function of requests ri for class i
A = Total number of units available
IIi = Protection limit for class1 through class i
Fi = average fare of class-i
The limit of the first integral are between zero and A-IIi, and the limits of the second integral are between A-IIi and infinity.
Curry used the optimality conditions arising from these equations for specific instances as data in a linear programming model for optimising protection levels.
Our approach has been somewhat different in that we use the equations directly as the objective function in a nonlinear integer programming model. This approach has the advantage of allowing side conditions to be imposed on the solution rather than relying on optimality conditions of an (unconstrained) solution. These side conditions appear as explicit constraints in the optimisation model, and may include user-specified upper and lower limits on protection levels. They may also include more general limits on the proportions of units in each discount class in relation to each other, for example the protection level for the full cost class be at least sixty percent of the protection level for the first discount class.
The model has been implemented in AESOP for a total of nine fare classes, consisting of three groups of three nested protection levels. The model has been tested on a variety of data, both randomly generated and that described in the papers cited above. The validity of the model was verified by comparing results with those previously reported, and several versions of linear constraints added in the form as described in the previous paragraph. A detailed description of the model and the results obtained is contained in a separate report [9].
Implementation of the nonlinear integer programming algorithm described in the second section of this paper in two classes of practical application areas has demonstrated the usefulness of the approach. Asset allocation models can have varying requirements for integer solutions depending on the nature of the investments and the complexity of the transaction costs, so in this area of application the integer aspects of the algorithm are a secondary consideration. This is in contrast to the situation for yield management applications where integer solutions are mandatory, and become more important as the event time gets closer.
6. References