How would I go about finding the optimal way to split up an order
I have a problem (that I think I'm over complicating) but for the life of me I can't seem to solve it.
I have 2 dataframes. One containing a list of items with quantities that I want to buy. I have another dataframe with a list of suppliers, unit cost and quantity of items available. Along with this I have a dataframe with shipping cost for each supplier.
I want to find the optimal way to break up my order among the suppliers to minimise costs.
Some added points:
- Suppliers won't always be able to fulfil the full order of an item so I want to also be able to split an individual item among suppliers if it is cheaper
- Shipping only gets added once per supplier (2 items from a supplier means I still only pay shipping once for that supplier)
I have seen people mention cvxpy for a similar problem but I'm struggling to find a way to use it for my problem (never used it before).
Some advice would be great.
Note: You don't have to write all the code for me but giving a bit of guidance on how to break down the problem would be great.
TIA
Solution
Here is an example of what a mathematical model can look like.
The blue symbols are data (exogenous) and the red symbols are decision variables (endogenous). The first constraint distributes demand over the suppliers. The second constraint implements the implication:
use[s] = 0 ==> buy[i,s] = 0
We don't need:
use[s] = 1 ==> buy[i,s] > 0
because of the structure of the objective function. The costs make sure we never use a supplier while not shipping from there.
The implementation in code is left to the reader. This should not be very difficult: try to stick as closely as possible to the mathematical model. Also, pay attention to the details in the model (everything counts here, there is no fluff).
A small test uses the following random data:
---- 25 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
---- 25 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
---- 25 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
---- 25 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
---- 25 PARAMETER totalavail total availability
item1 33.000, item2 25.000, item3 27.000, item4 21.000, item5 36.000, item6 26.000, item7 24.000
item8 27.000, item9 33.000, item10 36.000, item11 30.000, item12 28.000, item13 32.000, item14 21.000
item15 35.000, item16 42.000, item17 37.000, item18 37.000, item19 49.000, item20 33.000, item21 35.000
item22 30.000, item23 28.000, item24 30.000, item25 47.000, item26 32.000, item27 36.000, item28 31.000
item29 33.000, item30 30.000, item31 30.000, item32 27.000, item33 28.000, item34 37.000, item35 39.000
item36 43.000, item37 38.000, item38 47.000, item39 30.000, item40 30.000, item41 32.000, item42 33.000
item43 27.000, item44 25.000, item45 45.000, item46 39.000, item47 33.000, item48 35.000, item49 46.000
item50 19.000
---- 25 PARAMETER short shortages
( ALL 0.000 )
---- 25 PARAMETER maxbuy upperbound on buy
supplier1 supplier2 supplier3 supplier4 supplier5 supplier6 supplier7 supplier8 supplier9 supplier10
item1 2.000 2.000 2.000 2.000 2.000 2.000 2.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 6.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 4.000
item5 3.000 2.000 2.000 3.000 3.000 3.000 3.000 3.000
item6 3.000 3.000 3.000 1.000 3.000 2.000 1.000 3.000
item7 3.000 1.000 3.000 2.000 2.000 4.000 1.000 2.000 3.000
item8 3.000 2.000 1.000 4.000 4.000 6.000 7.000
item9 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
item10 6.000 1.000 5.000 6.000 6.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 6.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 2.000 2.000 2.000 1.000 2.000 2.000 2.000 2.000 2.000 2.000
item16 7.000 2.000 7.000 4.000 2.000 7.000 6.000 7.000
item17 2.000 1.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item18 3.000 3.000 3.000 2.000 3.000 3.000 3.000 3.000
item19 5.000 5.000 7.000 5.000 7.000 6.000 4.000 5.000 5.000
item20 5.000 4.000 3.000 5.000 1.000 1.000 5.000 5.000
item21 4.000 4.000 2.000 4.000 4.000 4.000 1.000 3.000
item22 2.000 3.000 2.000 1.000 4.000 3.000 1.000 3.000 2.000 4.000
item23 2.000 2.000 2.000 2.000 2.000 2.000 2.000 1.000
item24 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item25 3.000 2.000 6.000 5.000 6.000 6.000 6.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 3.000 2.000 1.000 3.000 3.000 3.000 3.000 3.000 3.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 4.000 4.000 2.000 3.000 2.000 4.000 3.000 3.000
item31 2.000 1.000 1.000 2.000 2.000 2.000 1.000 2.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 2.000 2.000 2.000 2.000 2.000 2.000 1.000
item34 5.000 5.000 6.000 4.000 2.000 4.000 3.000 6.000 2.000
item35 3.000 3.000 3.000 3.000 3.000 3.000 3.000 3.000
item36 3.000 1.000 2.000 3.000 3.000 3.000 3.000 3.000 2.000 3.000
item37 4.000 6.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 5.000 3.000 2.000 5.000 3.000 4.000 2.000 5.000
item41 5.000 3.000 1.000 4.000 2.000 5.000 4.000 3.000 1.000
item42 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item43 1.000 3.000 3.000 1.000 4.000 4.000 4.000 4.000
item44 1.000 1.000 1.000 1.000 1.000 1.000 1.000
item45 4.000 4.000 4.000 3.000 3.000 4.000 4.000 4.000 2.000 3.000
item46 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000 2.000
item47 3.000 5.000 5.000 4.000 1.000 4.000 4.000 5.000 1.000 1.000
item48 6.000 3.000 6.000 2.000 6.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 3.000 3.000 3.000 3.000 2.000 1.000
This is a very easy MIP. It was solved completely during preprocessing, so it took zero branch-and-bound nodes (and about 0.1 seconds). Definitely much easier than the Traveling Salesman problem (TSP). In the comments, it was conjectured this model is about as a difficult as a TSP. That is obviously not the case. Caveat: with different data sets, things may become a bit more difficult.
The solution looks like:
---- 53 VARIABLE totalcost.L = 598.132 to be minimized
---- 53 VARIABLE use.L supplier is used
supplier1 1.000, supplier5 1.000, supplier6 1.000, supplier7 1.000, supplier8 1.000, supplier9 1.000
---- 53 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
From the 10 suppliers in the data, only 6 are selected.
For large problems with lots of sparsity in the data avail[i,s] we can improve the formulation a bit.
I also tried a run with 1000 items and 50 suppliers. That took about 30 seconds to solve to proven optimality. This model has 50k discrete variables, so it is not small. Some commenters said this problem is as hard as a TSP problem. I hope this experiment debunks the notion that this problem is as difficult as the TSP problem (the TSP problem is not easily stated as a MIP that performs somewhat decently). Secondly, it proves that a MIP model is a viable approach for this problem.