Blending Models and Linearizable Objectives

Introduction

Exercise 4.3 illustrates and example of blending problems. \(x_j\) is defined to be the fraction of ingredient \(j\) in the blend. Units costs of the ingredients are given along with the daily requirements for protein, fat, and fiber that a serving of it fulfills. The gereral form of the problem is as follows:

\[ \text{Minimize} \quad \sum_{j=1}^{n} c_jx_j\]

\[ \text{Subject to} \quad \sum_{j=1}^{n} x_j = 1\]

\[ \quad \sum_{j=1}^{n} a_{ij}x_j \geq b_i \quad \text{for } i=1,2,3\]

\[ \quad x_j \geq 0 \quad \text{for } j=1,2,3,...,n\]

where \(c_j\) is the cost of ingredient \(j\), \(a_{ij}\) is the amount of nutrient \(i\) in ingredient \(j\), and \(b_i\) is the minimum daily requirement for nutrient \(i\). The problem is to find the blend that meets the minimum daily requirements at minimum cost.

Linearization of the Objective Function

Suppose we have the following non-linear objective function:

\[ \begin{aligned} & \max f(x_1, \dots, x_8) \triangleq \min \{r_j x_j : j = 1, \dots, 8\} \\ & \text{s.t.} \quad \sum_{j=1}^{8} x_j \leq 25 \\ & \quad \quad x_j \leq u_j \quad j = 1, \dots, 8 \\ & \quad \quad x_j \geq 0 \quad j = 1, \dots, 8 \\ \end{aligned} \]

We can introduce variable \(f\) to replace \(\min \{r_j x_j : j = 1, \dots, 8\}\) with introducing additional constraints:

\[ \begin{aligned} & \max f\\ & f\leq r_{j}x_{j} \quad j=1,2,3,4,5,6,7,8\\ & \sum_{j=1}^{8} x_j \leq 25\\ & x_j \leq u_j \quad j = 1, \dots, 8\\ & f\geq 0\\ & x_j \geq 0 \quad j = 1, \dots, 8\\ \end{aligned} \]

Example 4.9 illustrates how \(minmax\) function can be linearized.

References

1: Optimization in OR textbook by R. Rardin