Underestimating Costs in a Bidding Optimization Problem Can Cost You a Lot

What is the best combination of amount of items and vendors to minimize the total cost for purchasing a required item in bulk when it is provided by different vendors?
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.
Figure 1: Graph depicting the cost for different amounts of the same product for all 4 vendors
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.

This could be dangerous for the company. Why?

Because by solving the linearized problem, the costs from following a specific buying strategy could be underestimated by up to 5%!
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.
In this case study, the problem was small having only 1 nonlinearity in the constraints and variables. The discrepancies could be avoided since the cost graphs could be plotted (See Figure 1). But when the problem gets bigger, the chance of getting suboptimal results with the linearization increases. In general, the size and complexity of this type of problem is prohibitive for such a visual representation and result comparison.

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.
The mathematical annotation used to model the bidding optimization problem described above:
Symbol\LetterDescriptionAnnotation Type  
iPricing policy for each vendor (can be 1 or 2)index
jVendor’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 ivariable (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 0variable (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 0variable (binary)
\begin{equation} c_{j} \end{equation}The total cost paid to vendor j from purchasing an amount of products from themvariable (continuous)
dTotal amount of product neededParameter (Client specified)
Table 1: Annotation for Bidding Problem

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.
VendorSet Up CostProduct PriceUnits of Product
A1.050.551-30
B2.24c = 5 ln(u + 0.2) − 65-60
C131-4
0.074-80
D80.520-30
0.0330-65
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.
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:
    • 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.
    Bibliography

    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.

    Leave A Comment

    Leave a Reply