A TAXONOMY OF OPTIMIZATION MODELS

In Part I we got acquainted with two elementary and prototypical optimization models, which we recall here for readers’ convenience:

1. The production mix optimization model:²Here the decision variables x₁ and x₂ represent production quantities of two items; in a real-life problem we have many more items, and their production could be restricted to integer amounts: . In Eq. (12.1) we see a function that must be maximized, as it relates to profit. This objective function is not exactly our profit, as it does not consider fixed costs; nevertheless, it differs from true profit by a term which is constant with respect to the decisions that we are making at this level. Profit is maximized with respect to decision variables, subject to (s.t.) a set of constraints, which define a feasible region, also called feasible set. Inequalities (12.2)–(12.5) represent limitations due to finite capacity of the four resources that are used to manufacture the two item types. Finally, constraints (12.6) and (12.7) ensure that nonnegative amounts are produced, and that they do not exceed market demand bounds.
2. The economic order quantity model:³In this case, we have only one nonnegative decision variable Q, but the form of the objective function is definitely more complicated than Eq. (12.1). To begin with, it is nonlinear; then, it is not defined for Q = 0, and we should only consider the open interval Q > 0. Nevertheless, if we extend the objective function so that it takes the value +∞ when Q = 0, we immediately see that, since we are minimizing a cost, we may consider the interval Q ≥ 0 as the feasible region.⁴

Looking at these two examples, we notice similarities and differences:

• In an optimization model we have an objective function that can be minimized or maximized. In the following, we will mostly refer to minimization problems, with no loss of generality. In fact, any maximization problem can be converted into an equivalent minimization by changing the sign of the objective function or, if you prefer, by flipping it upside down:
• The objective function can be linear or nonlinear. In the production mix problem, we see an example of a linear objective function. A linear objective function is characterized by a sum likeEach decision variable x_j is multiplied by a coefficient c_j, which in a minimization problem could be the cost of carrying out activity j at level such as producing an amount x_j of item j. The precise meaning of the coefficients depends on the problem. In the production mix problem, where the objective is maximized, they represent a contribution to profit. Recall that adding a constant term would make the function linear affine, but this would not change the optimal solution. Any other objective form, such as functions involving products of decision variables or powers with an exponent different from one, is nonlinear. In the EOQ model, the term 1/Q renders the problem nonlinear. Generally speaking, a nonlinear objective function makes the problem more complicated. As we shall see, we may sometimes approximate a nonlinear objective by a piecewise linear one.
• In the EOQ model, we have a very simple restriction on the decision variable, which is just restricted to nonnegative values. In this case, the feasible set is . In the production mix model, we have a list of more complicated constraints. Generally speaking, the feasible set is described by a set of constraints of the following forms:
  • Inequality constraints are represented by inequalities like g(x) ≤ 0 or g(x) ≥ 0. When dealing with a generic optimization model, we will typically use inequalities of the formThere is no loss of generality in this choice, since we may always transform an inequality of the larger-than type as follows:We have four such inequalities in the production mix problem; to cast constraint (12.2) into form (12.9), we just shift the constant term to the left:If the function g is linear (affine), i.e.we have a linear constraint. If function g(·) involves products of variables, general powers of them, or exponential functions, etc., the constraint is nonlinear.
  • Equality constraints are represented by equations of the form h(x) = 0. We do not have equality constraints in the two examples above, but we will see examples of them later. A generic linear equality constraint can be written asNote that changing the sign of all the coefficients involved in this constraint has no effect on the feasible set. Equality constraints may be nonlinear as well.
  • We may also have simple lower bounds on decision variables, like x_j ≥ l_j, and upper bounds, like x_j ≤ u_j. In the production mix model we see the most common example of lower bound, i.e., a non-negativity restriction on decision variables, as well as upper bounds enforced by market limitations. In principle, simple bounds could be treated as inequality constraints. However, most optimization algorithms treat them separately for efficiency reasons.
  • Finally, in the following we will find examples of integrality restrictions., like . In both examples above, we could enforce such restrictions to make sure that we plan production of an integer amount of items; this may be not needed when we consider items that can be produced in amounts represented by continuous (real) variables, such as tons of a chemical element. We will see that, in general, restricting variables to integer values makes the solution of an optimization problem much harder. Whenever possible, it is advisable to get rid of such restrictions, even if it entails some degree of approximation. This is acceptable, for instance, in the case of items produced in large amounts, since rounding 1020.37 up or down implies a negligible error; this is not acceptable if production occurs on a very small scale, i.e., just a few items. The most common use of integer decision variables stems from the need to model logical decisions, such as “open a new manufacturing plant” or “do not open a new manufacturing plant.” In such a case, we may represent our decision as a binary (or logical) decision variable that may take only one of two values: x ∈ {0, 1}. Clearly, binary variables are discrete in nature, and relaxing them to continuous values in the interval [0, 1] makes no sense: Either you build a plant or not, as building 47% of it has no meaning.

In general and abstract terms, we may refer to an optimization problem in the following form

where S, the feasible set, is a subset of . If , we have an unconstrained optimization problem; otherwise, we have a constrained optimization problem. An optimization model like (12.10) is also referred to as a mathematical programming model. The key feature is that there is a finite set of n decision variables x_j, j = 1, …, n, collected into vector x. However strange it may sound, there are problems featuring an infinite set of decision variables. One such example occurs when we are looking for a function u(t) of time, where t ranges on the continuous interval [0, T]. The function u(t) should satisfy some constraints and be optimal according to some well-defined criterion. These problems are quite common in optimal control theory, where u(t) is a control input that should be applied to a system in order to force an optimal behavior in terms of desirable output. Optimal control problems are widely considered in economics as well, when time is assumed continuous in the model. In this book, we will consider only a discrete representation of time, which is partitioned into time periods (time buckets) indexed by t = 1, 2, 3, …, T. Hence, we will only deal with mathematical programs.

When we consider the actual ways in which we may describe the feasible set S, we see that there is a rich set of possible structures of optimization models. Yet, this variety can be boiled down to a smaller set of prototypes by using simple manipulations. For instance, an inequality constraint may be transformed into an equality constraint by introducing a nonnegative slack variable s as follows:

Fig. 12.1 Inequality constraints may be active/binding or not.

We may also go the other way around and transform an equality constraint into two inequality constraints:

These tricks of the trade may be useful not only when stating general properties, but also when considering concrete solution methods.

A generic inequality constraint g(x) ≤ 0 defines a portion of n-dimensional space. In the plane, it may define a region like the shaded one in Fig. 12.1; to be precise, in the figure we observe a curve corresponding to equation g(x) =0 and a shaded region corresponding to points such that the strict inequality g(x) < 0 applies. With reference to a specific point, an inequality constraint may be active or inactive. The constraint is active at point x_b in the figure, since there it is satisfied as an equality, g(x_b) = 0; on the contrary, the constraint is inactive at x_a, since g(x_a) < 0. It is important to notice that we may freely move in a neighborhood x_a without going out of the feasible set, provided that our step is small enough; on the contrary, we cannot move at will around x_b since only some directions preserve feasibility. Furthermore, a little perturbation of the constraint could make x_b infeasible. If we consider the optimal solution x*, we also say that an inequality constraint is binding if g(x*) = 0, i.e., if it is active at the optimal solution; if g(x*) < 0, the constraint is nonbinding. A noteworthy specific case occurs when considering the nonnegativity requirement x_j ≥ 0. When all the decision variables are strictly positive at the optimal point, i.e., when  for all j, we speak of an interior solution.

Example 12.1 For the optimal mix problem (12.1), we have observed that any mix feasible with respect to the second resource is also feasible with respect to the first and third ones. In fact, any point satisfying inequality (12.3) will also satisfy inequalities (12.2) and (12.4), since item type 1 has the same resource requirement on all of the related resources, whereas item type 2 has the largest requirement on the second one, which is a bottleneck. Hence, (12.2) and (12.4) are redundant constraints and will never be binding for the optimal mix. The practical implication is that there is no point in increasing the availability of resources that are not saturated, as this would not improve profit.

It can be expected that some optimization problems are relatively easy to solve, whereas others can be quite challenging. Therefore, it is important to understand which features draw the line between easy and difficult models. As we have seen, important attributes are “linear” vs. “nonlinear,” as well as “continuous” vs. “discrete.” When dealing with calculus, we have also considered other important features, which relate to convexity.⁵ We already know that even an unconstrained minimization problem involving a function of just one decision variable may be relatively difficult, as it may feature many local optima. We generalize to problems involving multiple variables and constraints; in the following subsections, we illustrate all of these concepts by very simple examples.