Wednesday, February 15, 2023

Supplier selection: an easy MIP

This is a fairly standard supplier selection model. It was posted in [1]. It is interesting as it is a good fit for a MIP model: it is simple to model, it solves fast, and it is not obvious how to solve without an optimization model.

The problem is:
  • We want to order items in different quantities from suppliers.
  • Suppliers have an available inventory for these items. This can be zero.
  • We can split the ordering over different suppliers.
  • The cost structure is as follows:
    • Shipping cost is a fixed cost per supplier.
    • Item cost is a variable per-unit cost. 

A good way to learn about a problem is to generate random data for it. Here I used 50 items and 10 suppliers. The data I invented looks like:

----     45 PARAMETER demand  demand for items

item1   2.000,    item2   9.000,    item3   6.000,    item4   4.000,    item5   3.000,    item6   3.000,    item7   4.000
item8   9.000,    item9   1.000,    item10  6.000,    item11 10.000,    item12  6.000,    item13 10.000,    item14  8.000
item15  2.000,    item16  7.000,    item17  2.000,    item18  3.000,    item19  7.000,    item20  5.000,    item21  4.000
item22  4.000,    item23  2.000,    item24  2.000,    item25  6.000,    item26  9.000,    item27  3.000,    item28  7.000
item29  8.000,    item30  4.000,    item31  2.000,    item32  6.000,    item33  2.000,    item34  9.000,    item35  3.000
item36  3.000,    item37  6.000,    item38  8.000,    item39  7.000,    item40  5.000,    item41  5.000,    item42  2.000
item43  4.000,    item44  1.000,    item45  4.000,    item46  2.000,    item47  7.000,    item48  6.000,    item49  8.000
item50  3.000


----     45 PARAMETER avail  availability of items

         supplier1   supplier2   supplier3   supplier4   supplier5   supplier6   supplier7   supplier8   supplier9  supplier10

item1        5.000       6.000       5.000       2.000                               5.000       4.000                   6.000
item2                    1.000       4.000       6.000       1.000                   4.000       4.000       3.000       2.000
item3        1.000       1.000       1.000       7.000       3.000       6.000       2.000       1.000       5.000
item4        1.000                   2.000       3.000       1.000       1.000       2.000       2.000       2.000       7.000
item5        7.000       2.000       2.000       6.000       3.000       7.000                   5.000                   4.000
item6                                3.000       4.000       5.000       1.000       3.000       2.000       1.000       7.000
item7        3.000       1.000       3.000       2.000       2.000       7.000       1.000       2.000                   3.000
item8                    3.000       2.000       1.000                   4.000       4.000                   6.000       7.000
item9        4.000       4.000       2.000       4.000       5.000       4.000       1.000       5.000       4.000
item10       7.000       1.000       5.000       6.000       7.000       1.000       2.000       1.000       1.000       5.000
item11       5.000                   1.000       3.000       1.000       5.000       6.000       1.000       3.000       5.000
item12       6.000       4.000       7.000                   1.000                   4.000       1.000       5.000
item13       3.000       6.000       3.000       4.000                   4.000       3.000       7.000       1.000       1.000
item14                   1.000                               6.000       4.000                   1.000       7.000       2.000
item15       4.000       2.000       5.000       1.000       3.000       3.000       6.000       4.000       3.000       4.000
item16       7.000       2.000                   7.000       4.000       2.000       7.000       6.000                   7.000
item17       4.000       1.000       5.000       2.000       7.000       7.000                   2.000       5.000       4.000
item18                   6.000       7.000       4.000       2.000       3.000                   6.000       4.000       5.000
item19       5.000       5.000                   7.000       5.000       7.000       6.000       4.000       5.000       5.000
item20       6.000       4.000                   3.000                   5.000       1.000       1.000       6.000       7.000
item21       6.000       5.000                   2.000       6.000       6.000       6.000       1.000       3.000
item22       2.000       3.000       2.000       1.000       6.000       3.000       1.000       3.000       2.000       7.000
item23                   3.000       2.000       3.000       5.000       5.000       2.000                   7.000       1.000
item24       7.000       3.000                   2.000       3.000       3.000                   6.000       6.000
item25       3.000       2.000       7.000                   5.000       7.000       7.000       7.000       6.000       3.000
item26       4.000       6.000       4.000                   4.000       4.000       5.000       1.000       2.000       2.000
item27       4.000       2.000       1.000       5.000       4.000       4.000       5.000       5.000                   6.000
item28       5.000       1.000       4.000       5.000       1.000       2.000       4.000       5.000       3.000       1.000
item29                               7.000       7.000       7.000       6.000       1.000                   4.000       1.000
item30       7.000       6.000       2.000                   3.000       2.000                   4.000       3.000       3.000
item31       7.000       1.000       1.000       4.000       5.000       2.000       1.000       7.000       2.000
item32       2.000                   6.000       1.000       3.000       2.000       3.000       5.000       4.000       1.000
item33       1.000       2.000       4.000       2.000                   5.000       5.000       2.000       6.000       1.000
item34       5.000       5.000       6.000       4.000       2.000       4.000       3.000                   6.000       2.000
item35                   4.000                   5.000       7.000       4.000       3.000       5.000       4.000       7.000
item36       6.000       1.000       2.000       5.000       3.000       7.000       7.000       7.000       2.000       3.000
item37       4.000       7.000       1.000       5.000       6.000       4.000                   6.000       2.000       3.000
item38       2.000       4.000       4.000       4.000       4.000       7.000       2.000       6.000       7.000       7.000
item39       2.000       2.000       1.000       1.000       5.000       2.000       6.000       4.000       2.000       5.000
item40                   6.000                   3.000       2.000       5.000       3.000       4.000       2.000       5.000
item41       7.000       3.000       1.000       4.000       2.000       7.000                   4.000       3.000       1.000
item42       4.000       4.000       2.000       2.000       4.000       4.000                   3.000       7.000       3.000
item43       1.000       3.000       3.000       1.000       5.000                   4.000                   4.000       6.000
item44                   6.000       2.000       1.000       3.000       2.000       4.000                   7.000
item45       6.000       6.000       5.000       3.000       3.000       6.000       7.000       4.000       2.000       3.000
item46       2.000       3.000                   6.000       4.000       5.000       6.000       3.000       7.000       3.000
item47       3.000       5.000       5.000       4.000       1.000       4.000       4.000       5.000       1.000       1.000
item48       7.000       3.000                   7.000       2.000       7.000       3.000       4.000       1.000       1.000
item49       5.000       6.000       4.000       7.000       3.000       2.000       6.000       6.000                   7.000
item50                   4.000                   3.000       5.000       4.000       2.000                               1.000


----     45 PARAMETER shipcost  shipping cost

supplier1  23.574,    supplier2  15.066,    supplier3  27.148,    supplier4  35.761,    supplier5  11.076,    supplier6  20.661
supplier7  20.136,    supplier8  24.595,    supplier9  17.781,    supplier10 36.736


----     45 PARAMETER itemcost  cost of items

         supplier1   supplier2   supplier3   supplier4   supplier5   supplier6   supplier7   supplier8   supplier9  supplier10

item1        4.397       3.538       4.946       4.032                               3.032       4.071                   4.329
item2                    3.336       3.300       3.227       3.414                   4.908       3.216       4.740       2.653
item3        4.226       1.003       2.821       2.677       1.063       1.328       3.395       3.221       3.472
item4        4.540                   1.759       2.712       1.666       4.545       3.706       4.453       1.371       4.986
item5        3.467       1.003       3.436       1.695       2.245       3.916                   1.339                   2.768
item6                                3.636       2.938       2.273       4.656       1.737       4.488       2.824       2.836
item7        1.496       1.415       1.940       2.361       4.492       4.379       4.292       2.922                   4.655
item8                    4.717       1.432       2.402                   4.440       2.362                   1.852       4.705
item9        2.443       4.504       1.593       2.824       2.073       2.187       1.462       2.599       4.647
item10       2.006       1.412       1.585       2.545       1.186       1.106       1.616       1.291       4.315       2.599
item11       2.669                   4.889       1.974       2.448       3.521       1.971       1.404       2.624       2.916
item12       1.580       3.039       4.541                   1.222                   3.030       4.056       4.916
item13       3.882       4.488       2.198       4.016                   4.375       2.873       3.620       2.512       2.435
item14                   2.018                               2.022       2.802                   4.779       2.342       1.194
item15       4.226       3.930       4.680       2.327       1.839       1.189       4.532       1.371       4.348       2.855
item16       1.001       1.626                   3.820       2.121       3.542       3.320       4.848                   3.057
item17       3.361       3.270       1.120       4.876       3.375       1.238                   3.176       1.509       2.682
item18                   4.526       3.866       2.254       4.972       1.221                   3.476       4.218       2.186
item19       4.836       3.779                   3.526       3.464       3.092       1.564       4.347       4.568       3.786
item20       2.247       2.423                   4.044                   1.545       3.867       4.855       2.768       2.058
item21       2.777       2.587                   2.468       3.485       4.439       4.020       4.603       2.752
item22       1.276       4.754       4.376       4.802       3.318       1.141       2.630       1.230       3.128       1.450
item23                   4.575       1.967       3.569       2.163       4.254       1.745                   3.003       4.755
item24       3.726       1.741                   4.492       1.660       2.723                   4.087       4.912
item25       4.778       1.995       4.546                   4.538       4.860       3.997       3.590       3.994       3.093
item26       3.744       3.764       4.463                   4.183       1.870       3.358       4.690       3.412       1.143
item27       4.644       3.260       2.299       2.560       2.197       1.876       4.287       1.611                   4.802
item28       1.128       3.938       1.442       2.951       2.444       1.866       4.695       2.800       4.884       1.385
item29                               2.916       3.889       2.733       1.633       1.403                   4.222       2.595
item30       1.468       4.497       1.579                   1.711       3.181                   2.874       4.637       3.892
item31       1.665       2.310       3.325       3.310       3.510       1.107       1.518       1.257       2.244
item32       3.314                   4.239       3.717       3.943       2.354       1.897       4.600       4.318       2.265
item33       4.809       2.027       3.504       4.885                   4.848       2.701       1.422       1.308       3.577
item34       2.249       3.381       3.426       3.535       4.833       1.329       1.501                   3.421       3.966
item35                   4.390                   2.410       3.566       4.583       2.553       2.094       4.882       2.385
item36       2.638       4.759       3.412       4.598       2.139       1.889       3.299       3.038       3.230       2.377
item37       2.593       4.105       1.113       2.450       4.023       2.900                   1.305       1.390       2.319
item38       1.802       1.363       2.795       2.851       4.248       2.800       4.817       1.491       2.626       4.545
item39       3.813       4.500       3.221       2.023       2.037       2.420       1.548       4.228       2.304       2.715
item40                   1.036                   1.897       3.643       2.150       1.524       2.628       1.646       4.447
item41       2.511       4.554       2.080       4.110       2.691       2.719                   1.996       2.527       1.284
item42       3.863       3.812       1.281       4.874       2.080       2.273                   4.534       3.345       2.528
item43       4.892       3.683       4.805       3.873       2.774                   4.519                   2.879       2.855
item44                   2.486       1.473       4.862       4.374       3.885       4.858                   2.458
item45       4.073       2.330       3.168       1.554       2.255       1.320       4.737       2.977       3.716       3.766
item46       1.219       1.961                   4.531       1.402       3.713       1.406       1.171       4.014       4.948
item47       1.059       1.587       4.964       1.529       1.342       1.744       4.161       4.458       3.992       2.558
item48       4.180       3.484                   4.045       3.321       3.654       1.329       3.267       2.773       2.313
item49       2.322       1.492       3.471       3.136       1.576       2.569       1.059       4.483                   1.982
item50                   4.213                   1.336       4.949       3.233       3.728                               4.438


This looks large enough to make it interesting and a bit realistic, and also to get a feeling for the performance of the solver.

It is possible to generate infeasible models, so I checked that we actually order less than the total availability over all suppliers. It is nice that we can check for infeasibility before even running the solver, so let's use that possibility. The feasibility check is: \[\sum_s  \color{darkblue}{\mathit{avail}}_{i,s} \ge \color{darkblue}{\mathit{demand}}_{i}\] If this does not hold, we can stop with a message.

The optimization model can look like:


Mathematical Model
\[ \begin{align} \text{Sets} \\ & i \text{: items} \\ & s \text{: suppliers} \\ & \hline \\ \text{Data} \\ & \color{darkblue}{\mathit{shipCost}}_s \text{: shipping cost}\\ & \color{darkblue}{\mathit{itemCost}}_{i,s} \text{: item cost}\\ & \color{darkblue}{\mathit{demand}}_{i} \text{: demand quantities}\\ & \color{darkblue}{\mathit{avail}}_{i,s} \text{: availability}\\ & \color{darkblue}{\mathit{maxBuy}}_{i,s} := \min\left\{\color{darkblue}{\mathit{avail}}_{i,s},\color{darkblue}{\mathit{demand}}_{i}\right\} \text{: upperbound on buying quantities}\\ & \hline \\ \text{Variables} \\ & \color{darkred}{\mathit buy}_{i,s} \text{: purchase quantities} \\ & \color{darkred}{\mathit use}_{s} = \begin{cases}1&\text{if supplier is used}\\ 0&\text{otherwise}\end{cases} \\ & \hline \\ \text{Model} \\ \min& \sum_s \color{darkblue}{\mathit shipCost}_s\cdot \color{darkred}{\mathit use}_s + \sum_{i,s} \color{darkblue}{\mathit itemCost}_{i,s}\cdot \color{darkred}{\mathit buy}_{i,s} \\ & \sum_s \color{darkred}{\mathit buy}_{i,s} = \color{darkblue}{\mathit demand}_{i} && \forall i \\ & \color{darkred}{\mathit buy}_{i,s} \le \color{darkblue}{\mathit maxBuy}_{i,s} \cdot \color{darkred}{\mathit use}_s && \forall i,s\\ & \color{darkred}{\mathit buy}_{i,s} \in \{0,\dots,\color{darkblue}{\mathit maxBuy}_{i,s}\}\\ & \color{darkred}{\mathit use}_s \in \{0,1\} \end{align}\]

The \( \color{darkblue}{\mathit{maxBuy}}_{i,s}\) quantities are used as big-Ms in the model, so we pay a bit of attention to make them not too big. In this case, we can easily calculate good values for them: \[\color{darkblue}{\mathit{maxBuy}}_{i,s} := \min\left\{\color{darkblue}{\mathit{avail}}_{i,s},\color{darkblue}{\mathit{demand}}_{i}\right\}\]

The first constraint distributes the demand over the different suppliers. The second constraint implements \[\color{darkred}{\mathit use}_s=0 \implies  \color{darkred}{\mathit buy}_{i,s}=0\>\>\forall i,s\] This is a disaggregated version. We can also write: \[\color{darkred}{\mathit use}_s=0 \implies  \sum_i \color{darkred}{\mathit buy}_{i,s}=0\>\>\forall s\] using \[\sum_i \color{darkred}{\mathit buy}_{i,s} \le \color{darkblue}M_s\cdot \color{darkred}{\mathit use}_s \>\>\forall s\] We would need to calculate for \(\color{darkblue}M_s\). The disgregated version can be faster even though it generates many more constraints. Note that we don't need to implement the implication \[ \color{darkred}{\mathit use}_s=1 \implies \color{darkred}{\mathit buy}_{i,s}\gt 0 \] This is automatically taken care due to the structure of the objective function. The costs will make sure we never use a supplier if we don't ship anything from it.

I assume that we can't split a single item, so integer variables are used to model buying quantities. In this case, the solution is integer-valued even if we relax the \(\color{darkred}{\mathit buy}_{i,s}\) variable to be continuous. As I don't think that is really guaranteed, I kept them as integer variables.

This model solves very fast. Cplex needed 0.1 seconds and zero nodes (the problem was solved during preprocessing). The solution is:


----     97 VARIABLE totalcost.L           =      598.132  to be minimized

----     97 VARIABLE use.L  supplier is used

supplier1 1.000,    supplier5 1.000,    supplier6 1.000,    supplier7 1.000,    supplier8 1.000,    supplier9 1.000


----     97 VARIABLE buy.L  orders to be placed at suppliers

         supplier1   supplier5   supplier6   supplier7   supplier8   supplier9

item1                                            2.000
item2                    1.000                   1.000       4.000       3.000
item3                    3.000       3.000
item4                    1.000                   1.000                   2.000
item5                                                        3.000
item6                                            3.000
item7        3.000                                           1.000
item8                                            3.000                   6.000
item9                                            1.000
item10                   5.000       1.000
item11                   1.000                   6.000       1.000       2.000
item12       5.000       1.000
item13                                           3.000       6.000       1.000
item14                   6.000                                           2.000
item15                               2.000
item16       7.000
item17                               2.000
item18                               3.000
item19                               1.000       6.000
item20                               5.000
item21       1.000                                                       3.000
item22                               3.000                   1.000
item23                                           2.000
item24                   2.000
item25                                                       6.000
item26                               4.000       5.000
item27                                                       3.000
item28       5.000                   2.000
item29                   1.000       6.000       1.000
item30       4.000
item31                               2.000
item32       1.000                   2.000       3.000
item33                                                                   2.000
item34       2.000                   4.000       3.000
item35                                                       3.000
item36                               3.000
item37                                                       6.000
item38       2.000                                           6.000
item39                   1.000                   6.000
item40                                           3.000                   2.000
item41       1.000                                           4.000
item42                   2.000
item43                   4.000
item44                                                                   1.000
item45                               4.000
item46                                                       2.000
item47       3.000       1.000       3.000
item48                                           3.000       2.000       1.000
item49                   2.000                   6.000
item50                               3.000


The columns in the last table should add up exactly to the demands. The fixed costs are high enough that the model only selects six suppliers.


Conclusion


This problem can be solved with a nice little MIP model. The model is simple, and the solution time is very fast. A good showcase for using a MIP model.


References



Appendix: GAMS model

$ontext

 

  Supplier selection problem

 

  We want to order quantities for different items.

  The shipping cost is a fixed cost: any amount ordered from

     a supplier has the same shipping cost.

  There are also variable cost: the item cost.

 

  We use here random data.

 

  A check is added for the case that demand exceeds the availability.

 

  maxBuy are big-M values. We try to make them as small as possible.

 

$offtext

 

*-----------------------------------------------------------------------

size of the problem

*-----------------------------------------------------------------------

 

Sets

   i 'items' /item1*item50/

   'suppliers' /supplier1*supplier10/ 

;

 

*-----------------------------------------------------------------------

random data

*-----------------------------------------------------------------------

 

 

Parameters

   demand(i)      'demand for items'

   avail(i,s)     'availability of items'

   shipcost(s)    'shipping cost'

   itemcost(i,s)  'cost of items'

;

 

demand(i) = uniformint(1,10);

avail(i,s) = uniformint(0,7);

shipcost(s) = uniform(10,40);

itemcost(i,s)$avail(i,s) = uniform(1,5);

 

display demand,avail,shipcost,itemcost;

 

*-----------------------------------------------------------------------

derived data

*-----------------------------------------------------------------------

 

Parameters

   totalavail(i)  'total availability'

   short(i)       'shortages'

   maxbuy(i,s)    'upperbound on buy'

;

 

totalavail(i) = sum(s,avail(i,s));

short(i) = max(0, demand(i)-totalavail(i));

maxbuy(i,s) = min(demand(i),avail(i,s));

 

display totalavail,short,maxbuy;

 

 

*-----------------------------------------------------------------------

stop if we have shortages. That would yield an infeasible model.

*-----------------------------------------------------------------------

 

abort$card(short) "not enough availability";

 

*-----------------------------------------------------------------------

model

*-----------------------------------------------------------------------

 

variables

    totalcost 'to be minimized'

    buy(i,s)  'orders to be placed at suppliers'

    use(s)    'supplier is used'

;

integer variable buy;

binary variable use;

buy.up(i,s) = maxbuy(i,s);

 

equations

    objective          'minimize totalcost'

    meetdemand(i)      'distribute demand over suppliers'

    use_supplier(i,s)  'use=0 => buy=0'

;

   

 

objective..  totalcost =e= sum(s,shipcost(s)*use(s)) + sum((i,s),itemcost(i,s)*buy(i,s));

meetdemand(i)..  sum(s, buy(i,s)) =e= demand(i);

use_supplier(i,s).. buy(i,s) =l= maxbuy(i,s)*use(s);

 

model m /all/;

solve m minimizing totalcost using mip;

 

display totalcost.l,use.l,buy.l;

 

 

If the data set is very large and avail(i,s) is very sparse, we probably should adapt the code a bit to exploit this. Basically, we should skip generating buy(i,s) when avail(i,s)=0

2 comments:

  1. For fixed use(s) in {0,1}, the resulting problem is pure network with integer coefficients, so it is no coincidence that the buy(i,s) variables would automatically take integer values.

    ReplyDelete
    Replies
    1. Nice. Interesting, so relaxations don't guarantee anything, but for integer solutions it is ok.

      Delete