CODEWITHSUNDEEP
algorithmdynamic-programminglinear-programming
Sushant Rao
Sushant Rao

Reputation: 484

Need a algorithm to find the minimum cost in a subset of elements

I am trying to find an optimal algorithm that can find the largest subset where the sum of the elements is the lowest while covering all elements.

eg :- Imagine A B C are retailers and W X Y Z are products, the goal is to minimize the visits, and lower the price. 

    A    B    C
W   4    9    2  
X   1    3    4 
Y   9    3    9
Z   7    1    1 

So it appears my top two choices are 
a) B:{XYZ} - 7   C:{W} - 2
b) C:{WXZ} - 7   B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9.

This problem seems similar to vertex cover and other linear programming algorithms, but I can't figure out the right one.

Update:

It seems I need to add an additional variable. Introducing t. If the cost of visiting fewest retailers and the next fewest is > t, the next former is picked. 

Continuing with the example.

say t = 5,

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7   C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7   C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7   C:{W} - 2 is picked

Really I'm just interested if there is already an algorithm that fits this pattern. I can't be the first person that needs this sort of optimization.

Upvotes: 1

Views: 1597

Answers (1)

Ram Narasimhan
Ram Narasimhan

Reputation: 22496

You have a problem with two objectives - 1. to minimize the total lower cost of the products and also to 2. minimize the number of stores visited. (The comment by @btilly rightly shows two competing solutions.)

Multiple objectives are fairly common in these types of Integer programming problems. See MCDM. To resolve this, you need to have two types of costs (you currently have only one.)

  1. The cost of buying product p from retailer r (which you have specified) C_rp
  2. The cost of visiting a retailer: C_r

Intuition: If C_r is very high, then we'll buy all the products from one retailer. If C_r is small, then we go to multiple retailers and buy from whomever is selling it most inexpensively.

Your problem can be modeled as a variant of the "Assignment Problem." Also, read up on the so-called fixed-charge transportation problems (FCTP) if you need more references. (There is a fixed charge to visiting a retailer once.)

So on to the Integer programming formulation:

Decision Variables

  Binary
  X_rp = if product p is purchased from retailer r, 0 otherwise 
  Y_r = 1 if retailer r is visited, 0 otherwise

Objective Function

 Min C_rp X_rp + C_r Y_r

Constraints 

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer)

Next, we need to ensure that Y_r is one if even one of the X_rp is 1 for for that retailer. Normally, we'd resort to the Big M method, but it is easier in this problem.

X_rp <= Y_r  for all p, for all r.

If any of the X variables becomes 1, that forces the Y_r to become 1. The model will pay the price C_r.

To solve, you can use any LP solver. The good news is that problem has an integrality property, meaning that integer solutions naturally occur even when linear programming solution techniques are used.

Hope that helps.

Upvotes: 1

Related Questions