\(\newcommand{\R}{{\mathbb{R}}}\) \(\newcommand{\Z}{{\mathbb{Z}}}\) \(\newcommand{\N}{{\mathbb{N}}}\) \(\newcommand{\var}[1]{{\color{red}{\mathbf{#1}}}}\) \(\newcommand{\param}[1]{{\color{blue}{#1}}}\) \(\newcommand{\mathsc}[1]{{\normalfont\textsc{#1}}}\) \(\def\sc#1{\dosc#1\csod}\) \(\def\dosc#1#2\csod{{\rm{#1{\rm\small #2}}}}\) \(\newcommand{\set}[1]{{\sc#1}}\) \(\newcommand{\mathvar}[1]{\var{#1}}\) \(\newcommand{\mathpar}[1]{\param{#1}}\) \(\newcommand{\half}{{\small{\frac{1}{2}}}}\)
4. Blending Models¶
Blending models deal with situations in which some raw material has to be mixed in order to obtain a blend with specific quality requirements. An example has been already presented in the introduction for the case of blending aluminum from scrap (see application: Blending aluminum scrap).
The following table summarizes some of the most typical applications of blending models; each application is identified by the input “materials”, the quality to be taken into consideration, the desired output.
A classic and well–known example of blending is the so-called diet problem; this is also the first example of a non trivial linear optimization problem solved by means of the simplex method (see [14], [13]).
Note
In the early days of linear optimization, the father of the simplex method, George Dantzig, solved a problem originally proposed to him by George Stigler (1982 Nobel prize winner in Economics) in the following form:
“For a moderately active man weighing 154 pounds, how much of each of 77 foods should be eaten on a daily basis so that the man’s intake of nine nutrients will be at least equal to the recommended dietary allowances (RDAs) suggested by the National Research Council in 1943, with the cost of the diet being minimal?”
A list of available foods is given, along with associated characteristics, like purchase price and nutritional characteristics (vitamins, proteins, carbohydrates, fat, calories, iron, …). It is required to find a minimum cost food blend which satisfies nutritional requirements (upper and/or lower bounds on each nutritional characteristics). A blending model specialized for diets can be represented as follows:
#------------------------------------------------------#
# optimal food bleding problem #
#------------------------------------------------------#
set FOODS;
set ELEMENTS;
param minQual{ELEMENTS}, default 0.;
param maxQual{ELEMENTS}, default Infinity;
param compos{ELEMENTS,FOODS};
param cost{FOODS};
param minReq{FOODS}, default 0.;
param maxReq{FOODS}, default Infinity;
# -----------------------------------------------------#
# variable declaration and bounding
# -----------------------------------------------------#
var Buy{f in FOODS} >= minReq[f], <= maxReq[f], integer;
var Content{el in ELEMENTS} >= minQual[el], <= maxQual[el];
# -----------------------------------------------------#
# objective function
# -----------------------------------------------------#
minimize totalcost: sum {f in FOODS} cost[f] * Buy[f];
# -----------------------------------------------------#
# constraints
# -----------------------------------------------------#
s.t. qual_def{el in ELEMENTS}:
Content[el] = sum{f in FOODS} compos[el,f] * Buy[f];
It can be immediately seen that, apart from some name changes included to make the model more readable, this is exactly the blending problem introduced in section Structured linear optimization models. The main difference is that, usually, in diet problems there is no constraint on the total quantity to be produced. However, a similar constraint might be needed when planning blends different from human food. In the above model some parameters default to 0, for lower bounds, or to \(\infty\), for upper bounds. An infinite upper bound means that the corresponding constraint is absent from the model.
Usually, the objective in blending models is cost minimization; however, sometimes the objective might be of a qualitative nature: for example, in a diet model, we might wish to minimize caloric contents, or, in aluminum scrap blending, we might wish to minimize iron. It’s easy to modify the objective by suitably changing the cost parameter.
When blending certain quantities of materials, each of them additively contributes to the quality of the blend. E.g., if 100g of a given kind of pasta contains 73g of carbohydrates and 14g of proteins, while 100g of Parmesan cheese contains 15g of carbohydrate and 28g of proteins, in a blend of 100g of pasta and 20g of cheese the carbohydrate contents will be
while for what concerns proteins the blend will contain
Some attention needs to be paid for the cases in which quality requirements are expressed not in terms of absolute quantities but of percentages. As an example, in an aluminum bending problem we usually require that iron is no more than 3%. Of course if a specific quantity, say 2000 kg, has to be produced, this can be readily transformed into an an absolute requirement: the blend should contain at most 60 kg of iron (3% of 2000). However when the quantity to be produced is itself a variable, the exact requirements cannot be determined a priori.
When the lower and upper bounds \(\param{minQual}, \param{maxQual}\) refer to a percentage, denoting by \(\var{x}\) the main variable of the problem and by \(\param{Q}\) the matrix containing the composition of foods, a formulation of the quality requirement might be:
However, in this constraint some variables appear in the denominator and, therefore, the model is no more linear, something that, if at all possible, is strongly advisable to avoid. This constraint can be easily transformed into a linear equivalent one by multiplying both members by the denominator:
or, equivalently,
The original Stigler diet model included a list of 77 foods and nine types of nutrients, and was considered in order to find the minimal cost diet for subsistence. The diet problem was resolved by hand by a group of nine researchers in 1947; its solution required 120 man-days of calculation. This model can now be solved to optimality in a fraction of a second on any personal computer with free open source solvers.
A data file with some of the foods and the nutritional specifications from the original paper by Stiegler is reported in the following piece of code. Of course the example has the sole purpose of illustrating the modeling methodology and should not be considered as a realistic example of a diet model. As Stiegler wrote on his paper, “No one recommends these diets for anyone, let alone everyone”.
# a reduced dataset from The Cost of Subsistence, George J. Stigler
# Journal of Farm Economics, Vol. 27, No. 2 (May, 1945), pp. 303-314
# The optimization problem requires a min cost diet for one year
set FOODS := wheat cornmeal cannedmilk margarine cheese peanut-b lard
liver porkroast salmon greenbeans cabbage onions potatoes
spinach sweet-pot peaches prunes limabeans navybeans;
set ELEMENTS := calorie protein calcium iron vitamin-a vitamin-b1
vitamin-b2 niacin vitamin-c;
param minQual := # recommended daily allowances
calorie 3
protein 70
calcium 0.8
iron 12
vitamin-a 5
vitamin-b1 1.8
vitamin-b2 2.7
niacin 18
vitamin-c 75;
param compos (tr): # This table is transposed for better reading.
# According to the original paper, this is the
# nutritive value of 1 $ spent per food. So
# actual nutritional contents is this one
# multiplied by the cost
calorie protein calcium iron vitamin-a
vitamin-b1 vitamin-b2 niacin vitamin-c :=
wheat 44.7 1411 2 365
0 55.4 33.3 441 0
cornmeal 36 897 1.7 99
30.9 17.4 7.9 106 0
cannedmilk 8.4 422 15.1 9
26 3 23.5 11 60
margarine 20.6 17 0.6 6
55.8 0.2 0 0 0
cheese 7.4 448 16.4 19
28.1 0.8 10.3 4 0
peanut-b 15.7 661 1 48
0 9.6 8.1 471 0
lard 41.7 0 0 0
0.2 0 0.5 5 0
liver 2.2 333 0.2 139
169.2 6.4 50.8 316 525
porkroast 4.4 249 0.3 37
0 18.2 3.6 79 0
salmon 5.8 705 6.8 45
3.5 1 4.9 209 0
greenbeans 2.4 138 3.7 80
69 4.3 5.8 37 862
cabbage 2.6 125 4 36
7.2 9 4.5 26 5369
onions 5.8 166 3.8 59
16.6 4.7 5.9 21 1184
potatoes 14.3 336 1.8 118
6.7 29.4 7.1 198 2522
spinach 1.1 106 0 138
918.4 5.7 13.8 33 2755
sweet-pot 9.6 138 2.7 54
290.7 8.4 5.4 83 1912
peaches 8.5 87 1.7 173
86.8 1.2 4.3 55 57
prunes 12.8 99 2.5 154
85.7 3.9 4.3 65 257
limabeans 17.4 1055 3.7 459
5.1 26.9 38.2 93 0
navybeans 26.9 1691 11.4 792
0 38.4 24.6 217 0
;
param cost:= # cost in $cent. per unit (prices as of 1939). One unit: 1lb
# unless differently specified
wheat 36 # 10 lb
cornmeal 4.6
cannedmilk 6.7 # 14.5 oz
margarine 16.1
cheese 24.2
peanut-b 17.9
lard 9.8
liver 26.8
porkroast 24.2
salmon 13.0 # 16 oz
greenbeans 7.1
cabbage 3.7
onions 3.6
potatoes 34 # 15 lb
spinach 8.1
sweet-pot 5.1
peaches 16.8 # 2.5
prunes 9.0
limabeans 8.9
navybeans 5.9
;
let {el in ELEMENTS, f in FOODS} compos[el,f] := compos[el,f] *
cost[f] / 100.;
# this was added in order to transform original nutritional data in
# the correct values. It was originally expressed in contents per
# dollar
# We might had kept that value. In this case, the cost would have been
# chosen as 1 for every food and the variable Buy would represent how
# much to spend in each food.
Solving the diet problem with these data produces the following result:
Gurobi 9.1.1: optimal solution; objective 10.86622782
6 simplex iterations
Buy [*] :=
cabbage 0.303093
liver 0.00706178
navybeans 1.03438
spinach 0.061823
wheat 0.0819974
;
: Content.lb Content :=
calcium 0.8 0.8
calorie 3 3
iron 12 60.4669
niacin 18 27.316
protein 70 147.414
vitamin-a 5 5
vitamin-b1 1.8 4.12044
vitamin-b2 2.7 2.7
vitamin-c 75 75
;
totalcost*365.25/100 = 39.6889
The minimum cost diet has a total yearly cost of 39.6889US$ (a very low price indeed, even considering it is referred to 1939).
From the above table the nutritional contents of this “diet” can be observed along with the imposed lower bounds; it is evident that some nutrients are expensive and, thus, in the optimal diet they appear at their lower bound (Calcium, Calories, Vitamins A and C); others, on the contrary, are abundant in the diet, significantly over the lower bound.
Diets built in this way suffer, typically, from a large set of defects. Sometimes it happens that a food appears in too large daily quantities (something we can easily put a remedy to by imposing an upper bound on the variables); frequently, as this case confirms, only a very small set of different foods appear in the solution. Moreover, it is usually undesirable to have non-integer values in the solution, as it is not possible to buy fractions of a single unit for each food. This kind of constraints usually require the introduction of binary variables, a topic we will introduce later in the chapter devoted to Mixed Integer Linear Models.
All of the above are constraints which we would like to add to the basic model in order to obtain an acceptable diet. By the way, this example shows that modeling is usually performed in iterative incremental steps: a simple model is formulated and solved, than the solution is critically analyzed and more refined models are possibly built until, eventually, the solution turns out to satisfy all of the requirements.
Consider the toy diet example below:
set FOODS :=
"Hamburger"
"Cheeseburger"
"Quarter Pounder w/ Cheese"
"McLean Deluxe"
"McLean Deluxe w/ Cheese"
"Big Mac"
"Filet-O-Fish"
"McGrilled Chicken"
"McChicken Sandwich"
…
"H-C Orange Drink (large)"
;
set ELEMENTS := Cal CalFat Fat SatFat Chol Sodium Carbo
Protein VitA VitC Calcium Iron;
param: minQual maxQual :=
Cal 2000 2000
CalFat 0 300
Fat 0 100
SatFat 0 30
Chol 0 375
Sodium 0 3000
Carbo 350 375
Protein 55 .
VitA 100 .
VitC 100 .
Calcium 100 .
Iron 100 .
;
param compos (tr):
Cal CalFat Fat SatFat Chol Sodium Carbo
Protein VitA VitC Calcium Iron :=
"Hamburger" 255 80 9 3 35 490 30 12 4 4 10 15
"Cheeseburger" 305 120 13 5 50 725 30 15 8 4 20 15
"Quarter Pounder w/ Cheese" 510 250 28 11 115 1110 34 28 15 6 30 20
"McLean Deluxe" 320 90 10 4 60 670 35 22 10 10 15 20
"McLean Deluxe w/ Cheese" 370 125 14 5 75 890 35 24 15 10 20 20
"Big Mac" 500 235 26 9 100 890 42 25 6 2 25 20
"Filet-O-Fish" 370 160 18 4 50 730 38 14 2 0 15 10
"McGrilled Chicken" 400 110 12 4 80 680 42 31 8 15 15 8
"McChicken Sandwich" 470 225 25 5 60 830 42 19 2 2 15 10
"Fries, small" 220 110 12 2.5 0 110 26 3 0 15 0 2
"Fries, large" 400 200 22 5 0 200 46 6 0 25 0 6
…
"Diet Coke (small)" 1 0 0 0 0 20 0 0 0 0 0 0
"Diet Coke (medium)" 2 0 0 0 0 25 0.5 0 0 0 0 0
"Diet Coke (large)" 3 0 0 0 0 35 0.5 0 0 0 0 0
"Sprite (small)" 140 0 0 0 0 35 37 0 0 0 0 0
"Sprite (medium)" 205 0 0 0 0 50 53 0 0 0 0 0
"Sprite (large)" 300 0 0 0 0 70 78 0 0 0 0 0
"H-C Orange Drink (small)" 160 0 0 0 0 35 42 0 0 0 0 0
"H-C Orange Drink (medium)" 240 0 0 0 0 50 60 0 0 0 0 0
"H-C Orange Drink (large)" 350 0 0 0 0 75 89 0 0 0 0 0
;
param cost :=
"Hamburger" 0.59
"Cheeseburger" 0.69
"Quarter Pounder w/ Cheese" 1.84
"McLean Deluxe" 2.09
"McLean Deluxe w/ Cheese" 2.19
"Big Mac" 1.84
"Filet-O-Fish" 1.44
"McGrilled Chicken" 2.29
"McChicken Sandwich" 2.04
"Fries, small" 0.77
"Fries, large" 1.17
…
"H-C Orange Drink (large)" 1.17
;
The minimum cost diet turns out to be
Buy [*] :=
"1% Lowfat Milk" 1.84868
"Cheerios" 2.26212
"Cheeseburger" 1.83187
"Chunky Chicken Salad" 0.0304813
"Hamburger" 0.24392
"Honey" 15.511
"Orange Juice" 0.408322
"Sweet 'N Sour Sauce" 4.32537
totalcost = 5.367956845
Even in a toy example like this one we can immediately see that this proposal is not acceptable; let us, for example, add a maximum of 2 portions per food. The result changes as follows
Buy [*] :=
"Barbeque Sauce" 2
"Cheerios" 1.81106
"Chocolate Shake" 2
"Chunky Chicken Salad" 0.212507
"H-C Orange Drink (large)" 0.73578
"Hamburger" 1.82403
"Honey" 2
"Orange Juice" 0.326808
"Strawberry Shake" 0.189541
"Sweet "N Sour Sauce" 2
totalcost = 7.168394112
As it can be easily guessed, additional or more strict constraints usually imply a cost increase. It is also worth observing that the request of an upper bound led to a modification not only in the quantity of the foods of the original solution, but also in the composition of the optimal diet, with new foods entering the blend.
Imposing now integrality we obtain
Buy [*] :=
"1% Lowfat Milk" 1
"Barbeque Sauce" 2
"Cheerios" 1
"Chocolate Shake" 1
"Hamburger" 1
"Honey" 1
"Orange Juice" 1
"Strawberry Shake" 2
"Sweet "N Sour Sauce" 2
"Wheaties" 2
totalcost = 8.45
with a cost 8.45, which, again, is higher than the previous one. We observe that the integer solution is not obtained by rounding the fractional ones, but by a quite different mix.
Of course the model presented here is so elementary to be, in practice, of little practical use; however, it may be the basis for building more realistic ones.
As an example, one of the constraints that often appears in real diets is a limitation on the amount of some types of fats, both in absolute terms or as a percentage of other kinds of fat. When the requirement is absolute, then it can be modeled as above; when however it is relative, some care has to be taken. As an example, in a balanced diet it might be required that the calories from fat do not exceed 30% of the total calories. Based on available data on the amount of calories from fat and the total for each food, the constraint is easily expressed as a linear inequality:
Many other nutritional requirements can be expressed in a similar way; however, it is not always possible, within the framework of linear optimization, to extend the model to account for different requirements. As an example, it frequently happens that the optimal diet consists of only a tiny number of different foods. This is a trivial consequence of the Fundamental Theorem of Linear Optimization and is connected with the fact that the solution returned by most solvers is a basic feasible solution. Imposing a threshold on the number of different foods in the diet cannot be made in a linear optimization model, although it is quite easily done with the introduction of binary variables, as we will see. In chapter Mixed Integer Linear Models we will present modeling techniques which allow for the inclusion of similar constraints, as well as other, more general, logical ones. Constraints like, e.g., “if the diet prescribes to use food A, then it must not contain food B” or “either A or B should be in the diet, but not both”, or “either food A is not part of the optimal diet, or its quantity must be at least 2 portions” can indeed be formulated through linear models with binary variables and “logical constraints”. Suitable models will be presented in section Using binary variables in logical constraints.
The example just described might also be extended over a time horizon: in this case each variable will have an additional index associated to each day or time period; there might be constraints on quality related to each single day as well as constraints on longer periods (e.g., the total calories should not be more than, say, \(3\,000\) per day, while they should be no more than \(2\,500\), on average, per week). In a multiperiod scenario, moreover, there can be different costs per day or different availability of foods.
It is also important to observe that, frequently, in blending problems costs are not linear but piecewise linear, with decreasing slope. This way discounts for large quantities are included in the model. A brief introduction on modeling techniques for piecewise linear functions (or even more general functions) will be presented in section _sect:minmax.
Another observation concerns data quality: frequently most data (nutritional contents, chemical composition) are just estimates of real data, corresponding to the composition of an “average” unit of material or food. The actual contents can be considered as the realization of a random variable. When some information is available or can be assumed on the probability distribution of these data, stochastic models can be considered, in which probabilistic constraints can be added. An example might be the requirement that the contents of iron in a blend should be no more than 2% with probability at least 98%. A very short introduction to the modeling aspects of probabilistic constraints will be given in section Stochastic linear optimization models. Taking into account the distribution of data, and, in particular, variance, can lead to much more robust and reasonable decisions.
4.1. Dual of blending problems¶
The structure of most linear blending problems is that of a standard linear optimization problems, with equations for quality contents and, possibly, an equation associated to the quantity to be produced. In formulae:
where \(c_j\) are unit costs, \(A_{ij}\) represents the percentage of chemical element \(i\) contained in a unit of scrap \(j\), and the total quantity produced is assumed to be one unit - see the beginning of this chapter for a description of the problem.
Assume for now that the equation on the total quantity above is redundant and can be eliminated without changing the set of feasible solutions. By this we mean that this equation is a linear combination of the other equations in the model. The most frequent case is when the composition matrix \(A\) contains a complete chemical analysis, i.e. its rows are associated to all chemical elements in the blend. In practice this is the case when
In this case the blending problem can be represented as
The dual of this standard linear optimization problem can be easily found, associating a dual variable to each chemical element:
In order to interpret this model it is useful to refer to a numerical example. Consider a blending problem with the following data:
The dual of this problem, in explicit form, is:
In order to proceed with an interpretation of this model, in the context of blending, notice that the primal problem requires the minimization of the blend cost. The objective function thus represents a monetary value, e.g. €. From strong duality the optimal value of the dual problem, when it exists, is identical to that of the primal; it is therefore quite reasonable to assume that even for the dual objective function the unit of measurement is monetary. The coefficients of the dual objective are pure numbers (percentages of chemical elements), thus variables \(\var{\lambda}\) represent monetary values. We might interpret the dual as follows: an hypothetical producer of pure metals wishes to fix the selling prices of Lead, Tin and Zinc. Knowing that the buyer requires 40, 30 and 30 units of Lead, Zinc, Tin, the manufacturer can assume to be able sell exactly 40 units of Lead, 30 of Zinc and 30 of Tin. The objective therefore corresponds to the maximization of the total revenue, given the prices of pure metal \(\var{\lambda}_{\texttt{Pb}}, \var{\lambda}_{\texttt{Zn}}, \var{\lambda}_{\texttt{Sn}}\).
For what concerns the constraints, the first one will be
Assuming prices have been chosen for each pure metal, the left hand side represents the cost of a blend composed of 10% Lead, 10% Zinc, 80% Tin: this is the price of a blend perfectly analogous to scrap A. Thus this constraint represents a competitive price fixing for scrap A: the manufacturer sets the price of pure metals in such a way as to make it competitive or equivalent with respect to one unit of type A scrap. Similarly, the other inequalities constrain the prices of pure metals to be set in order to be competitive with respect to each available scrap. Thus the dual of the blending problem is the problem faced by a producer of pure chemical elements who wishes to fix prices in such a way as to maximize the revenues while keeping the cost of synthetic equivalents lower than or equal to the market price for each scrap. So the manufacturer tries to persuade the buyer to use pure metals by setting prices which apparently are competitive with those of the scrap market. However, duality theory guarantees that the cost of the optimal scrap blend is exactly equal to the maximum revenue of the producer: there is a perfect balance between supply and demand, of course as long as both players, the minimizer and the maximizer, know the optimal strategy.
From the complementary slackness theorem, it can also be observed that, if a scrap is contained, at a non zero level, in an optimal blend, the corresponding dual constraint should be satisfied with zero slack (i.e., it should be active); but since the slack in the dual corresponds to the margin of the manufacturer for that scrap, duality implies that in the optimal solution, for every scrap whose purchase is worth, the manufacturer must fix the price in such a way that the margin is zero. It is therefore quite evident that the optimal objectives will be identical: the manufacturer has the possibility to set apparently competitive prices only for materials that the blend purchaser would not buy at all.
Returning to the original blending problem in which equation \(\sum_j \var{x}_j=1\) is included, we may find an interpretation in the following way. Assume that the rows of \(A\) (and of \(b\)) do not sum to 1, otherwise the constraint would be redundant. The linear optimization dual of the problem is now
where a single dual variable \(\var{\mu}\) has been introduced as the lagrange multiplier of the total request constraint. The original problem can be re-written, in equivalent form, by substituting the last equation with a linear combination:
The last equation corresponds to the chemical balance of the remaining elements in the blend. The dual of this problem, introducing a variable \(\var{\lambda}^\prime_{m+1}\) for the last equation, is
or, equivalently,
Comparing with the dual blending problem it is immediately seen that these dual formulations are identical provided we assume
Thus the dual of the generic blending problem can be interpreted exactly as before, provided that we associate a selling price also to the “remainder”, i.e. to a dummy chemical element which corresponds to what remains, in each scrap analysis, to reach 100% of the analysis. This sell price is the dual multiplier associated to the total requirement equation. The prices of the ordinary chemical elements in the two formulations just differ by this quantity.
4.2. Dual of the diet model¶
A diet model is a blending problem, although in general there is no requirement on the total quantity. This has been already observed before, so no change is required. Moreover, in a typical diet problem the constraints on nutrients take the form of inequalities: a \(\geq\) inequality will be imposed for useful nutrients, while a \(\leq\) one will be used for harmful ones. Sometimes, both lower and upper bounds are imposed for some nutrient. The general diet model can be represented as
Denoting by \(\var{\lambda}_i\) and \(\mathvar{\mu}_i\), respectively, the dual variables associated to the first and second group of constraints, the dual of the diet model can be written as:
It is understood that when one of the two limitations is absent also the corresponding dual variable does not enter the dual formulation. The interpretation is similar to that of the blending problem. We might notice that, assuming \(\ell_i < u_i\), in the optimal solution either \(\mathvar{\lambda}_i = 0\) or \(\mathvar{\mu}_i =0\) thanks to complementarity. Thus we may easily consider \(\mathvar{\lambda}_i + \mathvar{\mu}_i\) as the selling price of nutrient \(i\). This price will be non negative for positive nutrients (those associated with a minimum requirement), while for harmful nutrients the selling price will be non positive: in order to “sell” those nutrients we should give them for free or even as a discount on the total synthetic diet cost. The constraints in the dual thus just represent the usual competitiveness constraints of the seller of pure nutrients who would like to convince the diet buyer to choose pure nutrients in place of real foods. In the objective function, depending on the primal constraint, we will have either a price \(\mathvar{\lambda}_i \ell_i\) corresponding to selling \(\ell_i\) units of useful nutrients or a price \(\mathvar{\mu}_i u_i\) associated to the discount associated to the inclusion of \(u_i\) units of harmful nutrients, or 0, for those nutrients whose contents, in the optimal diet, is neither at the lower not at the upper bound.
© Fabio Schoen 2023
