BUILDING LINEAR PROGRAMMING MODELS

Continuous linear programming (LP) problems are convex mathematical programs, for which extremely efficient solution methods are widely available. Therefore, real-life and large-scale problems can actually be tackled, provided that we are able to cast the decision problem in LP form. To squeeze a problem into the LP paradigm, we need the ability of formalizing decisions, objectives, and constraints, which is more of an art than a science. The first step in learning the art of modeling is to get acquainted with a few standard problems, which can be regarded as paradigms, as well as building blocks for more realistic and interesting problems. In this section we introduce some of these stylized paradigms. Most real-life problems contain part or variations of these prototypes as submodels.

It is also important to draw the line between the abstract form of a model, capturing its structure, and the numerical problem to solve when we associate numerical information to all required data. It is customary to refer to the latter as a problem instance, which should not be confused with the problem itself. To illustrate how a problem is stated in its most general form, let us consider the familiar product mix problem, which we explored with a small-scale numerical example in Section 1.1. To generalize that specific problem instance to its general form, we need the following elements:

1. One or more families of indices to refer to real-life objects, like items to be produced and resources to be used. These indices correspond to sets and are typically used as subscripts when denoting data and decision variables. For instance, in the product mix we will refer to item types by subscript i = 1, …, N, where N is the number of item types; by the same token, we consider M resource classes, indexed by m = 1, …, M.
2. Then, we must list the data we need to gather so as to specify and solve a problem instance. In the product mix problem, we need:
   • Maximum demand, i.e., an upper bound for production and sales of each item: d_i, i = 1, …, N
   • Contribution to profit p_i for each item type i
   • Resource availability R_m (per period) for each resource class m = 1, …, M
   • Resource consumption r_im, for each item type i on each resource class m
3. Last but not least, we need to formalize the decisions we have to make. In this case, this task is quite easy, since we have to decide only how many items to produce for each item type; hence, the decision variables can be expressed as x_i, i = 1, …, N. If production volume is high enough, these decision variables can be assumed as nonnegative real numbers in ; otherwise, they have to be restricted to nonnegative integers in .

(Remark: The importance of finding the right decision variables cannot be stressed enough. All too often, students struggle hopelessly to build an LP model because they fail to clarify which kind of decisions should be made. When this is clear, additional variables are typically needed to express constraints and objectives. Hence, model building is an iterative process in which a first set of “natural” decision variables is found; then, auxiliary variables are added when considering each constraint in turn and the objective function.)

Armed with the notation given above, it is now quite easy to state a general product mix problem:

Let us consider each element of the model in more detail:

• Equation (12.17) is the objective function, i.e., the contribution to profit that we want to maximize.
• Equation (12.18) is a set of constraints, one for each resource class; for each m, we cannot exceed resource availability. Here we use a simple notation where all of the possible values of index ra are listed. Alternatively, we could define a set M = {1, 2, …, m} and write m ∈ M. You may also find a more mathematically inclined notation, like ∀m or ∀m ∈ M. Here the universal quantifier ∀ is used, which simply means “for all.” Then ∀m ∈ M means “for all elements m in the set M.”
• Finally, Eq. (12.19) states that decision variables are nonnegative real numbers not exceeding market limitations d_i for each item i. We recall that simple lower and upper bounds are typically considered separately from more complicated inequality constraints, for the sake of algorithmic efficiency. Insisting on the nonnegativity of x_i may seem redundant, as they enter an objective function that is maximized. However, if we forget that, it may be the case that an item with very low profit margin is produced in a negative quantity, in order to create a fictitious capacity in (12.18), i.e., to make room for the production of more profitable items. If necessary, we may also require integrality of decision variables. Enforcing  transforms the continuous LP above into a pure integer LP.

This is a rather simplistic model, but it is useful to state a couple of remarks in order to avoid common errors when modeling more complex problems.

• In an optimization model, there must be a well-defined objective function. Note that in (12.17) we have a sum over index i. This is the only subscript occurring in both p_i and x_i; hence, we have a well-defined expression. Always make sure that all of the subscripts are “covered” by a sum; for instance, an expression likeis not a well-defined expression since subscript j is not assigned. By a similar token, it does not make any sense to write something likeWhich sum for which j are we maximizing? We will see later how to define multiobjective problems in a meaningful way, but usually an expression like Eq. (12.21) is the result of a gross mistake.
• Also in constraints we must make sure that all of the involved subscripts are “covered.” However, in the case of a constraint, subscripts may be covered either by a sum or a quantifier (but not both). For instance, in (12.18) we have a coefficient r_im, where subscript i is covered by the sum and m is covered by the quantifier. Clearly, you must make sure that your use of subscripts makes sense. In this case, we must write a capacity constraint for each resource class m; in each constraint, the sum must run over the whole set of item types using resource m. Also note how the sum couples different products; when capacity constraints are involved, we cannot plan production of each item separately, as they compete for the use of shared and limited resources.

Now we are ready to tackle some variations on production planning and some different classes of models.