Algorithm for minimizing the cost of goods from different suppliers, what resources to study?

Question

Algorithms

I'm trying to write a small project for myself on my knee, but I'm not too strong in algorithms. I got stuck and wondering which way to dig.
Task:
There are a number of different products, in my test data it is 87.
There are various sellers who sell these products. (In my data, 163) Each of them has only some of the desired items in stock and different prices + shipping.
You need to find from whom and what goods to order in order to get the cheapest. So that in the end we get all the necessary goods. The shipping cost can be considered constant.
Examples - we may have one seller who sells all the goods, but more expensive than the rest, who have only a part of the goods, we can order from different sellers, paying more for shipping, but in the end saving at the expense of lower prices. Or vice versa, we have a bunch of sellers who sell one product very cheaply, and one who sells everything at once, but at a higher price. Then we can order more expensive, but save money due to the fact that we pay delivery once.

For some time now I have been trying to solve the problem head-on, not that it was really necessary, but it’s just interesting to figure it out myself :)
So far, in a sane time, it has only been possible to do a minimization of the number of sellers - I did it on the assumption that the price spread is not strong. But he quickly discovered that whoever has the largest assortment - the prices are also the largest, and it turns out so-so.
I tried to minimize prices with a blunt enumeration - but it also turns out for a very long time. there are too many possible combinations, even if you make optimizations by putting the "most promising" sellers at the beginning of the search and breaking the search if the current price has already exceeded the minimum found.
I am sure that on the basis of this we can make a quick search for a "sufficiently optimal" solution, if we do not go through all possible combinations, but stop it all after some time, assuming that with optimal sellers at the beginning, we will find an acceptable solution in the first few passes, and then we will only run into empty space, squeezing out the remaining pennies.

Actually, the task sounds like something that has already been tried to be solved somewhere, I just don’t know about it :) Therefore, first of all, it’s interesting if there are any ready-made solutions / data structures that can do this or something similar. I understand that most likely you need to dig somewhere in the direction of combinatorics, but I don’t know the right words to ask Google :)

Answer 1

yes. you understood by your example why greedy algorithms do not work and practically came to branch-and-bound. A "sufficiently good" solution can be obtained by heuristics, the best - only by enumeration (though not complete, but sometimes very long, because it is necessary to prove that this is really the best solution).
you have a knapsack problem (fill the knapsack with the required number of goods while minimizing the total cost).
here I even outlined an example of solving this type of problem using ready-made solvers (your model is different, but the principle is the same): What are worthy alternatives to the greedy algorithm (greedy)? . At least there are all the keywords to understand what to look for next.
(well, yes, this is far from the only way to solve, I'm just lazy and describe the model for the mip solver is the fastest for me. Ilya Nikolaevsky and Sergey Sokolov can add a lot of interesting things)

Answer 2

Can be reduced to linear integer programming.
Indicator variables (0 or 1) - whether you buy this product from this seller (x_ij).
Another variable is whether you pay this seller for shipping (y_j).
Restrictions:
y_j >= x_ij
sum_j (x_ij) = 1
Objective function - to minimize costs: sum_ij x_ij*c_ij + sum_j y_j*d_j
Then solve with some solver (there are a lot of fast libraries).
You can also use all sorts of annealing methods or genetic algorithms.
It is possible still full search with cutoffs. Obviously, if we take some set of sellers, then each of them must have a minimum price for some product. This means that it is possible to maintain the current minimum prices for all products at the selected sellers (+infinity if no one sells this product). You can take some seller only if his price for some goods is less. Well, and all sorts of early exits - if the sum of the minimum prices in general for all + the current delivery costs is higher than the optimal answer so far, there is no point in adding sellers further.