Fixed-charge problem and semicontinuous decision variables

The knapsack model and its variants are pure binary programming models. In this section we get acquainted with a quite common mixed-integer model, arising when the cost structure related to an activity cannot be represented in simple linear terms. The fixed-charge problem is one such case. Let decision variable x ≥ 0 represent the level of an activity. The total cost TC(x) related to the activity may consist of two terms:

• A variable cost, which is represented by a term like cx, where c is the unit variable cost.
• A fixed charge f, which is only paid if x > 0, i.e., if the activity is carried out at a positive level.

In principle, we could introduce a step function such as

and express total cost as

Unfortunately, the step function is nonlinear and discontinuous at the origin, as it jumps from 0 to 1. An alternative representation is obtained by introducing the following binary variable:

Then we link x and δ by the so-called big-M constraint:

where M is a suitably large constant. To see how Eq. (12.51) works, imagine that δ = 0; then, the constraint reads x ≤ 0, whatever the value of M is. This constraint, together with the standard nonnegativity restriction x ≥ 0, enforces x = 0. If δ = 1, the constraint is x ≤ M, which is nonbinding if M is large enough; in practice, we should take a sensible upper bound on the level of activity x. In principle, the exact choice of the big-M is not relevant; however, the tighter bound we use, the faster a branch and bound solver will be in tackling the problem, as we shall see in Section 12.6.3. Apparently, the constraint allows for an absurd solution in which δ = 1 and we pay the fixed charge f, but we do not carry out the related activity, i.e., we leave x = 0. While it is true that this is feasible for constraint (12.51), a solution like this will never be optimal for the objective function

Example 12.14 Suppose that we are given a set of activities, indexed by i = 1, …, n. The level of activity i is measured by a nonnegative continuous variable x_i; the activity levels are subject to a set of constraints, formally expressed as x ∈ S. Each activity has a cost proportional to the level x_i and a fixed charge f_i, which is paid whenever x_i > 0. Assume that we know an upper bound M_i on the level of activity i, and introduce a set of binary variables δ_i to represent fixed charges. Then, we should solve the following model:

In the next sections we illustrate a few classical examples of problems involving the big-M trick of the trade. Another common requirement on the level of an activity is that, if it is undertaken, its level should be in the interval [m_i, M_i]. Note that this is not equivalent to requiring that m_i ≤ x_i ≤ M_i. Rather, we want something like

which is a nonconvex set (recall that the union of convex sets need not be convex). Using the same trick as above, we may just write

These constraints define a semicontinuous decision variable. Semicontinuous variables may be used, e.g., in the following cases:

• We are blending an end product by using chemicals, and we have a choice between several ingredients; however, there is no point in using a very small amount of a raw material, as this implies that some piece of blending equipment will get dirty for nothing.
• We want to build a financial portfolio, but we do not want to include assets with a very small weight, as this will just make the portfolio hard to manage because of transaction costs that are incurred whenever an asset is bought or sold.