5.4 Semi-continuous Variables

Although relatively little used, 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, giving effect to the instruction: "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

It would be nice if semi-continuous variables enabled you simply to specify lower and upper bounds, L and U, such that the variable was either 0 or lay between L and U. Unfortunately in many LP codes they don't. Instead you define a semi-continuous variable, x, by means of a semi-continuous upper bound, U'. This means that x takes the value 0 or any value between 1 and U'. As a consequence, if you wish to change a continuous variable in your model to be semi-continuous, you cannot simply specify a lower bound L below which it becomes semi-continuous. Instead you must modify the formulation to scale the variable x so that the semi-continuous lower bound is 1.

Another use of semi-continuous variables is in scheduling models. Here it enables you to ensure that a model incurs the fixed cost of carrying out an activity without going on to fit activities together in an optimum combination (as in a knapsack problem).

Consider a problem where we are running a depot and must resupply it every so often. There are several options for how we resupply it, with economies of scale for the larger modes of transport. We are concerned primarily with the next month, but wish to ensure that we don't achieve an "optimum" solution for the forthcoming month at the expense of stoking up problems for the future.

The continuous solution will be to resupply the depot using the largest mode of transport. If the depot's consumption is small, this will expressed as a fraction of a delivery. But either a delivery is being proposed within the next month or it is not. And if there is no delivery, the depot will run out. So there is a binary decision as to whether there should be a delivery or not.

On the other hand, once the model has decided to make a delivery, there is a sensible interpretation which can be placed on a non-integer number of deliveries greater than 1, say r. It is that deliveries should be made that number of times per month, i.e. every 30/r days. Further, this is a more realistic solution than would be obtained if one were to seek a wholly integer solution. For in that case, the model might decide that 1 delivery by the largest (and most economical) mode of transport was insufficient but that 2 were too much. It might then propose 2 visits by a smaller mode of transport, which is a much less attractive solution.

previous contents next

Comments