7

Is there a better way to compute cartesian product. Since cartesian product is a special case that differs on each case. I think, I need to explain what I need to achieve and why I end up doing cartesian product. Please help me if cartesian product is the only solution for my problem. If so, how to improve the performance.

Background:

We are trying to help customers to buy products cheaper.

Let say customer ordered 5 products (prod1, prod2, prod3, prod4, prod5).

Each ordered product has been offered by different vendors.

Representation Format1:

Vendor1 - offers prod1, prod2, prod4

vendor2 - offers prod1, prod5

vendor3 - offers prod1, prod2, prod5

vendor4 - offers prod1

vendor5 - offers prod2 vendor6 - offers prod3, prod4

In other words

Representation Format2:

Prod1 - offered by vendor1, vendor2, vendor3, vendor4

Prod2 - offered by vendor5, vendor3, vendor1

prod3 - offered by vendor6

prod4 - offered by vendor1, vendor6

prod5 - offered by vendor3, vendor2

Now to choose the best vendor based on the price. We can sort the products by price and take the first one.

In that case we choose

prod1 from vendor1

prod2 from vendor5

prod3 from vendor6

prod4 from vendor1

prod5 from vendor3

Complexity:

since we chose 4 unique vendors, we need to pay 4 shipping price.

Also each vendor has a minimum purchase order. If we don't meet then we end up paying that charge as well.

In order to choose the best combination of product. We have to do cartesian product of offered products to compute the total price.

total price computation algorithm:

foreach unique vendor 
if(sum(product price offered by specific vendor * quantity)<minimum purchase order limit specified by specific vendor)
totalprice +=sum(product price * quantity) + minimum purchase charge + shipping price
else
totalprice +=sum(product price * quantity) + shipping price
end foreach

In our case

{vendor1, vendor2, vendor3, vendor4}

{vendor1, vendor3, vendor5}

{vendor6}

{vendor1, vendor6}

{vendor2, vendor3}

4 * 3 * 1 * 2 * 2 = 48 combination needs to be computed to find the best combination.

{vendor1,vendor1, vendor6, vendor1, vendor2}=totalprice1,

{vendor1, vendor3, vendor6, vendor1, vendor2}=totalprice2,

.

.

{vendor4, vendor5, vendor6, vendor6, vendor3}=totalprice48

Now sort the computed totalprice to find the best combination.

Actual Problem:

If customer order's more than 15 products.Lets assume, each product has been offered by 8 unique vendor then we end up computing 8^15=35184372088832 combination. Which takes more than couple of hours. If customer order's more than 20 products then it takes more than couple of days.

Is there a solution to approach this problem in a different angle?

Improve this question
2
  • 1
    This looks like a linear (or may be dynamic) programming problem, the guys at: math.stackexchange.com/?as=1 may be able to point you to a mathematically sound algorithm for it. Although such algorithms provide optimal solutions they require some background in the subject. Commented Apr 25, 2012 at 20:25
  • @EmmadKareem: It definitely isn't linear programming (dynamic programming means something completely different). It might be integer linear programming, but I don't see how to write the cost function as linear and even if it was, integer linear programming is NP-hard anyway. Commented Apr 26, 2012 at 7:51

1 Answer 1

Reset to default
2

Your Problem is in the same category as the famous "travelling salesman problem". Finding the best solution will be very expensive with rising numbers of vendors and products. You can try to implement a backtracking algorithm that tries to cut the solution space as early as possible.

Some ideas are:

  1. Start with the "biggest cost" = max(quantity * min(price))
  2. Try to minimize the number of vendors (=> try to get more products from a vendor already in the list)
  3. add a solution if all items are ordered
  4. break and track back if the current total sum is bigger than your best result
  5. ...
Improve this answer
3
  • What do you mean by "same category"? NP-hard but not in NP? Commented Apr 26, 2012 at 7:01
  • @scarfridge - It's just a "rough" classification to give an image. Any NP-* problem would have done the job. Btw. the rucksack problem fits even better. Commented Apr 26, 2012 at 8:39
  • Okay, so I guess you don't know the scientific name either. Commented Apr 26, 2012 at 10:31

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.