MP in Action‎ > ‎How to Use MP‎ > ‎

Non-Linear Optimization Using Extensions to LP

This article picks up from But my Problem isn't Linear! which covered ways of handling non-linearities where there could be discontinuities.

This article is concerned with ways of tackling problems which have non-linearities but which do not have discontinuities.

Special Ordered Sets of Type 2

In the last article we saw how a Special Ordered Set of type 1 (S1 set) could be used to represent a multiple-choice problem. A set of binary variables {δi} was defined with the extra structure that at most one member could be non-zero and with a hint to the MIP code in the form of a reference row. Each element of the S1 set appears in the reference row and their coefficients are used to guide the MIP algorithm in partitioning the set during the branch-and-bound algorithm.

A Special Ordered Set of type 2 (S2 set) is very similar to an S1 set except that at most two adjacent members can be non-zero. The usual form in which it is found is where the sum of the members of the S2 set equals 1. In this case the members are conventionally represented by the symbol λ and we have the convexity constraint

Σi λi = 1

Consider a variant of our factory problem from last time. A decision must be made whether to expand the current factory or build a new one on a green-field site. Some back-of-the-envelope calculations have been made of various options. The costs against incremental capacity are shown in Figure 1.

Figure 1: Costs of Increasing Capacity

For a small increase in capacity it makes sense to expand the existing plant, but if a larger increase is required, it is better to build a new plant. Thus we have the curve shown in Figure 2 for the cost vs. incremental capacity.

Figure 2: Representing the Possibilities with an S2 Set

We could formulate this problem with binary variables as the only integer constructs. But the performance of the MIP code will be much better if we use an S2 set. We identify a set of points {i = 1, 2, ... I} on the curve between which we are happy to interpolate linearly. Note that there are several points on the curve which we must represent:

  • "do nothing", i.e. zero increment of capacity and zero cost;
  • "do a little", i.e. a small increment of capacity at the existing plant and the fixed cost of making any change to the plant;
  • the "cross-over", where it becomes more economic to build a new plant rather than expand the existing one;
  • "do as much as possible", i.e. build as large a new factory as could be wanted.

How many other points should be represented is very much a matter of personal preference. Very often the data are of such quality that it is unlikely to be worth using more than a couple of further points We shall use a total of 6 points and denote the increments in capacity by CAPINCi and their costs by COSTi.

We can think of the λi variables as representing the "probability of choosing option i". That is, if λi = 1, we will choose option i. If λ3 = 0.25 and λ4 = 0.75 we shall have moved three-quarters of the way from option 3 to option 4, i.e. point A in Figure 2. Because of the restriction that at most two adjacent elements of the set can be non-zero, we cannot have the solution λi = 0.2, λi+2 = 0.8 or combinations in which three or more members of the set take non-zero values.

When we solve a MIP problem, the first stage is to solve it as an LP and find the continuous solution. In this the integer restrictions are not observed. With the structure of cost vs incremental capacity shown in Figure 2, the optimal solution will lie on the line between points 1 and 6, i.e. the "do nothing" option and "do as much as possible". This is because this is the most "cost-effective" way of achieving any required level of capacity.

Suppose that the continuous solution lies at point P on the line between points 1 and 6. The model has decided to use an increment of capacity between CAPINC4 and CAPINC5 at a cost between COST3 and COST4. Now although this solution involves "cheating", it actually tells us a lot about what the real solution will be. The chances are that the model will actually want a solution somewhere between points 3 and 5, i.e. an increment of capacity between CAPINC3 and CAPINC5 at a cost between COST3 and COST5.

The beauty of the S2 set is that the MIP code is able to focus in on these possibilities straightaway rather than spending its time on irrelevant branches. Without the S2 set, it is likely that the MIP code would identify that the model didn't want to expand the existing factory and spend a lot of time branching variables representing different capacities of new factory. Only when it found these rather expensive might it reconsider the possibility of expanding the existing factory. The S2 set enables the model to see immediately that if it doesn't want to spend as much as COST4 it should expand the existing factory rather than building a new one.

S2 sets are very good at representing non-linear relationships between two continuous variables, as with cost and capacity here. If you can express the relationship as y = f(x), then an S2 set is likely to be as good a way of modelling it as you can achieve using MIP. Having said that, it is not a panacea, and if the relationship involves a high degree of non-linearity, it may not be successful.

Successive Linear Programming

Successive Linear Programming (SLP), also known as "recursion", is a very different technique. It consists of solving a succession of LPs each of which represents the "tangent plane" to the non-linear problem at the last solution. It is thus an analogue of Newton's method for finding the root of an equation. A difference is that the distance which one is permitted to move from the last solution may be constrained so as to counter potential instability.

The technique is widely used in modelling oil refineries. It addresses one of the main difficulties which arises with LP models, the so-called "Pooling Problem". This occurs where one has a "pool" of product whose qualities depend on previous activities (e.g. which combination of crude oils is being processed and how; the ratio in which component oils are being blended).

Using purely linear constraints it is possible to constrain the qualities of the "pool" to lie within limits. But what if we then wish to use the material in the "pool" for further blending? We shall need decision variable xPOOL to tell us how much of the material to use in the blend. We shall use xi for the quantities of other components i to be used and assume that they have known qualities Qi. We must constrain the quality of the blend to be less than QMAX. Then we have the constraint:

QPOOL * xPOOL + Σi Qi xi ≤ QMAX ( xPOOL + Σi xi )

But what is QPOOL? If we knew the answer, we should have a linear constraint. We don't, so the constraint is non-linear. QPOOL is itself a decision variable, the consequence of activities upstream in the refinery (this is the reason for the "*": it shows that we are multiplying two decision variables together).

Successive Linear Programming enables us to tackle problems such as this where we have products of decision variables. It works best where, as in an oil refinery, the problem is "nearly linear". To see what it involves, consider the term QPOOL* xPOOL. For clarity we shall drop the POOL. Now we have values of Q and x from our last solution; denote these by Qs, xs. These are constants. We express Q and x as:

Q = Qs + ΔQ
x = xs + Δx

where ΔQ, Δx are small changes in Q and x from their current values; these may be positive or negative. Then

Q * x = (Qs + ΔQ) * (xs + Δx) = Qs x + xs Q - Qs xs + ΔQ * Δx

Now the first two terms in this last expression are the product of a known constant and a decision variable while the third is the product of two constants. The last is the product of two small quantities, which we disregard. We therefore have the linear expansion:

         Q * x ≈ Qs x + xs Q - Qs xs

This approximation (and analogues for other functions of decision variables) is the basis of SLP. In principle it can be implemented using any LP software but in practice it is much easier if the modelling package and the LP code are set up to handle it. The LP packages which are used in refineries have such facilities, as does XPRESS among algebraic modelling languages.

SLP is a hill-climbing technique. It works by finding the best solution within the neighbourhood of the existing solution. It can therefore be expected only to find a local optimum, whereas MIP techniques do, in principle, find the global optimum (but completing the branch-and-bound search may take longer than the universe is old!).

For "nearly-linear" problems this is adequate, but for more difficult problems other techniques are better, such as those based on successive quadratic programming. The restricted distance which the algorithm can move from one solution to the next can even be an advantage. It mirrors the restrictions which exist in continuous process industries such as oil refineries where it is impracticable to make dramatic switches from one day to the next.

Related articles include But my Problem Isn't Linear! and What Can Integer Programming Do?. To find other articles, refer to the MP in Action page.

Comments