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 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
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
- How would I go about finding the optimal way to split up an order, https://stackoverflow.com/questions/75447782/how-would-i-go-about-finding-the-optimal-way-to-split-up-an-order
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/ s '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.
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.
ReplyDeleteNice. Interesting, so relaxations don't guarantee anything, but for integer solutions it is ok.
Delete