What DS/AI technique should I try for this optimization problem?

Question

The dataset stores the prices of different stores of each item:

Item	Store1_price	Store2_price	Store3_price
Apple	2.00	3.23	2.48
Table Salt	1.52	5.20	2.53

There will be around 10 stores and an unlimited number of items.

My problem is to find the best combination of stores to buy each item (e.g. buy apple in store1, and buy table salt in store1) so that both the total price of all items is minimized AND the number of stores is minimized.

If there are 10 possible stores and 100 items, the number of combinations will be 10^100 and it will be highly inefficient if I need to list all the combinations.

Does anyone know how this problem should be tackled?

Answer 1

The problem can be visualized as a constraint optimization problem with the constraints Best Combination (products*store) Optimization Problem s

1. Minimize the total sum cost of products min (sigma(i=1,n) p(i)) where i is the ith product bought, for n being the total number of products bought

2. min |s|, where s denotes the cardinalilty of stores visited. Here we minimize the number of stores visited.

@Stat Begineer - Do we have a given list of products that are to bought or the products are bought based on their availability in the stores ?

PS- Light GBM could be one of the potential solutions https://www.youtube.com/watch?v=ohGeGfUCV_A

Answer 2

You can use a genetic algorithm like PyGAD to explore millions of random scenarios and get the best one among them.

It might not be the optimal solution, but much better than any human classification or a long machine calculation.

Therefore, you just have to set a fitness function that takes into account:

• The minimum number of stores
• The minimum price of items

The main question is: Which cost would you pay for each new store?

For example, if every new store costs 100$, your function will look like this:

total_price = sum(items_storeA) + sum(items_storeB) +...+ (nb_stores-1)*100