- info@octeract.co.uk

In this case study, four vendors, A, B, C and D, had submitted bids to supply certain quantities of an item a company wanted to purchase in large quantities (See Table 1). The price each vendor gave was related to the setup costs (how much it costs to set up the machines to produce this product) which are independent of quantity sold, and scaled costs; the larger the quantity of the products to be purchased, the lower the cost (See Figure 1).

Due to Vendor B, this cost minimization problem can be posed as a Mixed Integer Non-Linear Programming (MINLP) problem.

The insights we have gathered from many optimization consultancies show that this problem would be linearized with the method of Taylor series expansion and so turned into a MILP problem that would be solved with a linear solver.

Octeract solved the problem both at its original and linearized form.

When the problem was solved for different amounts of the required product, the MILP resulted in to a different buying strategy than the MINLP in about 10% of the tested demand. This meant a different choice of vendors and false lower costs than expected in reality.

On the other hand, the MINLP problem returned the optimal solution flawlessly.

Linearizing more than one equations significantly increases the complexity of the resulting linearized counterpart. In the case where the original problem does not involve any integer variables, the linearization will result into their introduction complicating the problem even more. Most importantly, even for large values of linearization points and powerful linear solvers, there can be no guarantee of optimality (in most cases not even feasibility) of the approximate solution.

Symbol\Letter | Description | Annotation Type | ||
---|---|---|---|---|

i | Pricing policy for each vendor (can be 1 or 2) | index | ||

j | Vendor’s name (can be A, B, C or D) | index | ||

\begin{equation} u_{j,i} \end{equation} | Amount of product bought from vendor j and pricing policy i | variable (continuous) | ||

\begin{equation} y_{j,i} \end{equation} | Was an amount of products bought from vendor j and pricing policy i ? If yes, then 1. If no, then 0 | variable (binary) | ||

\begin{equation} y_{j} \end{equation} | Answers the question of whether any amount was bought from vendor j. If yes, then 1. If no, then 0 | variable (binary) | ||

\begin{equation} c_{j} \end{equation} | The total cost paid to vendor j from purchasing an amount of products from them | variable (continuous) | ||

d | Total amount of product needed | Parameter (Client specified) |

Also, we had to take into account the following in the modelling of the problem:

1. Is vendor j selected at all? If yes, then let’s think about the amount of products bought from this vendor. This in mathematics translates to:\begin{equation} \sum_{i=1}^{2}y_{j,i} \leq y_{j}, \end{equation}

2. The minimum amount of products that can be purchased from vendor B is 4 and for vendor D is 20. Any amount lower than these, will incur the cost of paying for 4 products for vendor B and 20 products from vendor D.

3. The price for purchasing the product from Ventor B was given by a non linear equation where c is the order cost and u is the amount of products to be purchased from Vendor B.

4.When the demand was set to d = 5, it was low enough to be covered by a single vendor (see Table 1). But, the MILP was unable to determine successfully which vendor would that be. Also, 5 times the linearisation points were required for the MILP to converge to the correct solution, leading to a problem with 21 linear variables, 21 binary variables and 43 linear inequalities and equations.

Table 2: Names of vendors and costs for purchasing the needed product from each vendor depending on set up costs (independent of number of items purchased) and number of items purchased.

1. Is vendor j selected at all? If yes, then let’s think about the amount of products bought from this vendor. This in mathematics translates to:\begin{equation} \sum_{i=1}^{2}y_{j,i} \leq y_{j}, \end{equation}

2. The minimum amount of products that can be purchased from vendor B is 4 and for vendor D is 20. Any amount lower than these, will incur the cost of paying for 4 products for vendor B and 20 products from vendor D.

3. The price for purchasing the product from Ventor B was given by a non linear equation where c is the order cost and u is the amount of products to be purchased from Vendor B.

4.When the demand was set to d = 5, it was low enough to be covered by a single vendor (see Table 1). But, the MILP was unable to determine successfully which vendor would that be. Also, 5 times the linearisation points were required for the MILP to converge to the correct solution, leading to a problem with 21 linear variables, 21 binary variables and 43 linear inequalities and equations.

Vendor | Set Up Cost | Product Price | Units of Product |
---|---|---|---|

A | 1.05 | 0.55 | 1-30 |

B | 2.24 | c = 5 ln(u + 0.2) − 6 | 5-60 |

C | 1 | 3 | 1-4 |

0.07 | 4-80 | ||

D | 8 | 0.5 | 20-30 |

0.03 | 30-65 |

The problem now takes the following form:
\begin{equation} \label{MINLP}
\begin{aligned}
\underset{u,y}{\text{min}} & \quad c_A + c_B + c_C + c_D \\
\text{s.t.} & \quad c_A = 0.55u_{A,1} + 0.5y_{A,1} \\
& \quad c_B = (5\ln(5 + 0.2) -6)y_{B,1} + 5\ln(u_{B,2} + 0.2) – 6y_{B,2} – 5\ln(0.2)(1-y_{B,2})\\
& \quad c_C = 3u_{C,1} + 2y_{C,1} + 0.07u_{C,2} + 9.72y_{C,2}\\
& \quad c_D = 8y_{D,1} + 0.5u_{D,2} – 2y_{D,2} + 0.03u_{D,3} + 12.1y_{D,3}\\
& \quad u_{A,1} + \sum_{i=1}^{2}u_{B,i} + \sum_{i=1}^{2}u_{C,i} + \sum_{i=1}^{3}u_{D,i} \geq d \\
& \quad y_{A,1} \leq y_{A}, ~ \sum_{i=1}^{2}y_{B,i} \leq y_{B}, ~ \sum_{i=1}^{2}y_{C,i} \leq y_{C} , ~ \sum_{i=1}^{3}y_{D,i} \leq y_{D} \\
& \quad y_{A,1} \leq u_{A,1} \leq 30y_{A,1} \\
& \quad y_{B,1} \leq u_{B,1} \leq 5y_{B,1}, ~ \quad 5y_{B,2} \leq u_{B,2} \leq 60y_{B,2} \\
& \quad y_{C,1} \leq u_{C,1} \leq 4y_{C,1}, ~ 4y_{C,2} \leq u_{C,2} \leq 80y_{C,2} \\
& \quad y_{D,1} \leq u_{D,1} \leq 20y_{D,1}, ~ 20y_{D,2} \leq u_{D,2} \leq 30y_{D,2}, ~ 30y_{D,3} \leq u_{D,3} \leq 65y_{D,3} \\
& \quad u \in \mathbb{U} \subseteq \mathbb{R}^{k=24} \\
& \quad y \in \mathbb{Y} \subseteq \{0,1\}^{l=12}
\end{aligned}
\end{equation}

Because of the cost-demand relationship from purchasing an amount of the needed product from Vendor B, this problem is formulated as an MINLP problem.

It is a small problem comprising of:
1 nonlinear variable \(u_{B,2}\).
1 nonlinear equation \(c_{B}\).
11 linear variables.
12 binary variables.
24 linear inequalities and equations.

All of the experts in optimization reading the mathematics section are thinking that the way they would solve this fast, easily and reliably would be to use Taylor series expansion to linearize the above MINLP.

The part of the original MINLP requiring linearization is the part where the cost for purchasing amounts of the product from vendor B is calculated. Meaning that the definitions for \(c_{B}\) and \(u_{B,2}\) need to be linearized.

Below, you can find the linearized expressions: \begin{equation} \begin{aligned} &c_{B} \simeq (5\ln(5 + 0.2) -6)y_{B,1} + \sum_n\left( \frac{5}{p_j+0.2}u_{B,j+1} + \left(- \frac{5p_j}{p_j+0.2}+5\ln(p_j+0.2)-6\right)y_{B,j+1}\right) \\ & p_j = \frac{110j+10n-55}{2}, ~\forall j \in \{1,2,\dots,n\}\\ & \left(5+55\frac{(j-1)}{n}\right)y_{B,j+1} \leq u_{B,j+1} \leq \left(5+55\frac{j}{n}\right)y_{B,j+1}, ~ \forall j \in \{1,2,\dots,n\}\\ & u_{A,1} + \sum_{i=1}^{n+1}u_{B,i} + \sum_{i=1}^{2}u_{C,i} + \sum_{i=1}^{3}u_{D,i} \geq d \\ \end{aligned} \label{Taylor} \end{equation}

With these linearizations, the original MINLP problem has become an MILP comprising of:

The part of the original MINLP requiring linearization is the part where the cost for purchasing amounts of the product from vendor B is calculated. Meaning that the definitions for \(c_{B}\) and \(u_{B,2}\) need to be linearized.

Below, you can find the linearized expressions: \begin{equation} \begin{aligned} &c_{B} \simeq (5\ln(5 + 0.2) -6)y_{B,1} + \sum_n\left( \frac{5}{p_j+0.2}u_{B,j+1} + \left(- \frac{5p_j}{p_j+0.2}+5\ln(p_j+0.2)-6\right)y_{B,j+1}\right) \\ & p_j = \frac{110j+10n-55}{2}, ~\forall j \in \{1,2,\dots,n\}\\ & \left(5+55\frac{(j-1)}{n}\right)y_{B,j+1} \leq u_{B,j+1} \leq \left(5+55\frac{j}{n}\right)y_{B,j+1}, ~ \forall j \in \{1,2,\dots,n\}\\ & u_{A,1} + \sum_{i=1}^{n+1}u_{B,i} + \sum_{i=1}^{2}u_{C,i} + \sum_{i=1}^{3}u_{D,i} \geq d \\ \end{aligned} \label{Taylor} \end{equation}

With these linearizations, the original MINLP problem has become an MILP comprising of:

- 11 + n linear variables.
- 12 + n − 1 binary variables.
- 24 + 2n − 1 linear inequalities and equations.

Both problems were tested for the same series of demand d. The MILP problem was linearized in two points
(n = 2) and solved using OSICBC while the MINLP problem was solved using Octeract Engine. All
problems returned a solution within fractions of a second for both Optimization Engines.

The bid evaluation problem was adapted from Chapter 3 of J. Bracken, & G. P. McCormick “Selected applications of nonlinear programming”, pp. 28–37, Wiley (1968) New York.

- info@octeract.co.uk

## Leave A Comment