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
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:
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 CAPINC_{i} and their costs by COST_{i}. 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 CAPINC_{4} and CAPINC_{5} at a cost between COST_{3} and COST_{4}. 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 CAPINC_{3} and CAPINC_{5} at a cost between COST_{3} and COST_{5}. 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 COST_{4} 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 x_{POOL} to tell us how much of the material to use in the blend. We shall use x_{i} for the quantities of other components i to be used and assume that they have known qualities Q_{i}. We must constrain the quality of the blend to be less than Q_{MAX}. Then we have the constraint:
But what is Q_{POOL}? If we knew the answer, we should have a linear constraint. We don't, so the constraint is non-linear. Q_{POOL} 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 Q_{POOL}* x_{POOL}. For clarity we shall drop the _{POOL}. Now we have values of Q and x from our last solution; denote these by Q^{s}, x^{s}. These are constants. We express Q and x as: Q = Q^{s} + ΔQ where ΔQ, Δx are small changes in Q and x from their current values; these may be positive or negative. Then Q * x = (Q^{s} + ΔQ) * (x^{s} + Δx) = Q^{s} x + x^{s} Q - Q^{s} x^{s} + Δ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 ≈ Q^{s} x + x^{s} Q - Q^{s} x^{s} 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. |
MP in Action > How to Use MP >