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

But my Problem Isn't Linear!

Many readers will be familiar with Linear Programming (LP) and know how it can be used to find the best solution to problems involving "continuous" decision variables and "linear" constraints.

This article starts to explore how far it is practicable to go in representing apparently nonlinear problems using Linear Programming and what can be achieved with Mixed Integer Programming.

Continuous Decision Variables

In an LP model the decision variables are continuous. This means that they are permitted to take any value between a lower bound (zero if a bound is not specified explicitly) and an upper bound (infinity if a bound is not specified). For many situations this is a reasonable assumption. It works better than you might expect because at an optimum solution most decision variables will be at one of their bounds, typically at zero.

Despite this, there will be occasions when the value which an LP model declares as optimum is not really acceptable. For instance, in making a blend of 10 tonnes of animal feed per day, it may declare that 15 kg of salt should be added. If you were making a cake, it would be reasonable to add a pinch of salt, because you would ensure that it was distributed evenly throughout the mixture. But if a blender is running continuously with a man periodically emptying 50kg sacks into a hopper, it will be impracticable to add 15 kg of salt each 24 hours.

Then there are the yes/no decisions. Either something is done, or it isn't. This cannot be represented by a continuous decision variable. Nor can a decision where the answer must be a whole number, e.g. the number of 50kg sacks to be used in making our 10 tonnes of feed. In practice it often suffices to use the young child's system of counting: "1, 2, 3, lots" (i.e. continuous values beyond 4), as other inaccuracies in a model render it specious to seek to establish whether it is better to use 10 or 11 sacks of one component.

Linear Constraints

Although it may appear that linearity is a very severe restriction to impose on the constraints of a model, in practice it is less of a problem than the requirement for decision variables to take continuous values. This is for several reasons:

  • to a first order, the world is linear;
  • values can be transformed by a monotonic function (e.g. by taking logarithms) so that the resulting constraints are linear;
  • constraints can be expressed by relating one linear combination of decision variables against another where the value of neither combination is known.

These points may be exemplified by the constraints used in the oil industry to control the quality of blends of component oils. Suppose we have volumes v1 and v2 of two oils with qualities Q1 and Q2 which blend linearly by volume (note that lower case is being used for unknowns and upper case for known data). Then the quality, q, of the blend is given by:

q = ( Q1 * v1 + Q2 * v2 ) / ( v1 + v2 )

If we require that q be less than some maximum QMAX, we appear to have a non-linear constraint. But a simple piece of manipulation yields the constraint:

( Q1 - QMAX ) * v1 + ( Q2 - QMAX ) * v2 ≤ 0

which is linear.

Some qualities may blend geometrically, i.e. the quality, q, of the blend is given by:

q = [ Q1 v1 * Q2 v2 ] 1 / ( v1 + v2 )

Here it suffices to replace Q in our constraint by Θ = log Q. Other qualities may require more exotic transformations to yield what are known as linear blend indices. The Refutas blend index for viscosity (VBI) takes the form:

VBI = A + B log (log (viscosity + C ) )

where A, B, and C are constants.

Some qualities blend by weight rather than by volume. VBI is an example. For such qualities we need to know the density D1 and D2 of the components. The density of the blend, d, is then a variable which we can constrain in the ordinary way.

It might appear that we need to use products or quotients of variables to constrain a quality which blends by weight. But this is not so. The following constraint suffices:

[ ( Q1 - QMAX ) / D1 ] * v1+ [ ( Q2 - QMAX ) / D2 ] * v2 ≤ 0

Similar techniques can be used with other types of constraint to represent apparently non-linear relationships with linear constraints. But there are constraints which are intrinsically non-linear and which cannot be represented directly, e.g.

z = x * y

Also, where linear approximations are used, they only hold over a small range and if the model seeks to move outside that range, the nonlinearity must be recognised and modelled directly.

Discontinuous Variables

The simplest type of discontinuous variable used in Integer Programming is the binary variable. This is a decision variable which takes the value 0 or 1. It is used to represent yes/no decisions and is often associated with fixed costs which are incurred if some action is taken. Generalisations of it include integer variables which take values 0, 1, 2, ... N and semi-continuous variables which take the value 0 or any (continuous) value between 1 and some upper limit U.

Although binary variables are the simplest type of discontinuous variable, they are also the hardest type for an LP-based technology such as Mixed Integer Programming to handle. This is because MIP first finds the continuous optimum solution to the problem disregarding the integer constructs and then seeks to find integer feasible solutions by various heuristic techniques. In the continuous solution a binary variable is constrained simply to lie between 0 and 1 and so if the continuous optimum value does not happen to lie at 0 or 1 the MIP algorithms must decide which extreme to push it to.

Contrast this with general integer variables or semi-continuous variables. If we have a general integer variable with an upper bound of 10 and it takes the value 5.5 in the continuous solution, the chances are that the optimum integer value will be 5 or 6. Further, pushing the variable to either of those values is unlikely to have as much effect on other decision variables in the solution as pushing a binary variable from, say, 0.3 to 0 or to 1. Even pushing a binary variable from 0.01 to 0 can have an enormous effect (indeed it may make the problem infeasible) because it is eliminating the activities associated with that variable entirely.

Although relatively little used (and unfortunately stuck in a vicious circle of absence from much LP software), semi-continuous variables are one of the most elegant integer programming constructs, and one which works very well. They provide a direct means of eliminating fiddly quantities from a solution, such as the salt in our animal feed example. They enable you to say "either do something seriously or don't do it at all". This is particularly useful where the true cost of an activity is as shown in the graph, i.e. cost is generally proportional to the level of activity, but there are diseconomies of scale if a very small amount is used. The semi-continuous variable is used to exclude the region between 0 and 10 in which the diseconomies of scale apply.

Figure 1: Semi-continuous Costs

Sets of Decision Variables

Although binary variables are the bane of MIP, they become benign when present in groups of related binary variables known as Special Ordered Sets.

A Special Ordered Set of type 1 (S1 set) consists of a set of binary variables {δi} such that at most one has a non-zero value. It thus represents a multiple-choice problem: choose one of these or none at all. Often the user is also asked to specify a reference row in which the members of the S1 set appear with coefficients which reflect some property of the various options, e.g. their cost or their size.

Consider an example in which a decision must be made as to whether to build a new factory and, if so, which one of several possibilities is to be built. The decision whether to build each possible factory is represented by the binary variables δ1, δ2, δ3, ... with δ0 used to represent "do nothing". Each factory has a capital cost and produces revenue benefits elsewhere in the model through increased production, greater efficiency, etc as shown in the chart below.

Figure 2: Cost vs Benefit for Options

In general we would expect that greater capital investment will result in greater benefits but there may well be diminishing returns as investment increases and anomalies (as with option 3 in the chart).

Intuitively we can see that the problem is really one of selecting the appropriate level of investment. It is thus closer to that of deciding the value of an integer variable x = 1, 2, 3, ... than that of deciding individually the values of a number of binary variables. The MIP algorithm follows this approach. It uses the continuous solution to help it to focus in quickly on the most likely options, thereby speeding the solution process. We shall see more examples of how to assist the optimization process with other integer constructs in later articles.

Related articles include How to Build a Mathematical Programming Model and Non-Linear Optimization Using Extensions to LP. To find other articles, refer to the MP in Action page.

Comments