CODEWITHSUNDEEP
optimizationmathematical-optimizationdiscrete-mathematics
DonkeyKong
DonkeyKong

Reputation: 13

Program to optimize cost

This is my problem set for one of my CS class and I am kind of stuck. Here is the summary of the problem.

Create a program that will:
1) take a list of grocery stores and its available items and prices
2) take a list of required items that you need to buy
3) output a supermarket where you can get all your items with the cheapest price

input: supermarkets.list, [tomato, orange, turnip]
output: supermarket_1

The list looks something like
supermarket_1
$2.00 tomato
$3.00 orange
$4.00 tomato, orange, turnip

supermarket_2
$3.00 tomato
$2.00 orange
$3.00 turnip
$15.00 tomato, orange, turnip

If we want to buy tomato and orange, then the optimal solution would be buying 
from supermarket_1 $4.00. Note that it is possible for an item to be bough 
twice. So if wanted to buy 2 tomatoes, buying from supermarket_1 would be the 
optimal solution.

So far, I have been able to put the dataset into a data structure that I hope will allow me to easily do operations on it. I basically have a dictionary of supermarkets and the value would point to a another dictionary containing the mapping from each entry to its price.

supermarket_1 --> [turnip --> $2.00]
                  [orange --> $1.50]

One way is to use brute force, to get all combinations and find whichever satisfies the solution and find the one with the minimum. So far, this is what I can come up with. There is no assumption that the price of a combination of two items would be less than buying each separately.

Any suggestions hints are welcome

Upvotes: 1

Views: 279

Answers (3)

Reinhard
Reinhard

Reputation: 399

Finding the optimal solution for a specific supermarket is a generalization of the set cover problem, which is NP-complete. The reduction goes as follows: Given an instance of the set cover problem, just define a cost function assigning 1 to each combination, apply an algorithm that solves your problem, and you obtain an optimal solution of the set cover instance. (Finding the minimal price hence corresponds to finding the minimum number of covering sets.) Thus, your Problem is NP-hard, and you cannot expect to finde a solution that runs in polynomial time.

You really should implement the brute-force method you mentioned. I too recommand you to do this as a first step. If the performance is not sufficient, you can try a using a MIP-formulation and a solver like CPLEX, or you have to devolop a heuristic approach.

For a single supermarket, it is rather trivial to find a mixed integer program (MIP). Let x_i be the integer number how often product combination i is contained in a solution, c_i its cost and w_ij the number how often product j is contained in product combination i. Then, you are minimizing 


sum_i x_i * c_i

subject to conditions like


sum_i x_i * w_ij >= r_j,

where r_j is the number how often product j is required.

Upvotes: 2

Victor P.
Victor P.

Reputation: 675

I am not sure what you mean by "brute force" solution. Why don't you just calculate the cost of your list of items in each of the supermarkets, and then select the minimum? Complexity would be in O(#items x #supermarkets) which is good.

Regarding your data structure you can also simply have a matrix (2 dimension array) price[super][item], and use ids for your supermarkets/items.

Upvotes: 0

Martin James
Martin James

Reputation: 24847

Well, you have one method, so implement it now so you have something that works to submit. A brute-force solution should not take long to code up, then you can get some performance data and you can think about the problem more deeply. Guesstimate the number of supermarkets in a reasonable shopping range in a large city. Create that many supermarket records and link them to product tables with random-ish prices, (this is more work than the solution).

Run your brute-force solution. Does it work? If it outputs a solution, 'manually' add up the prices and list them against three other 'supermarket' records taken at random, (just pick a number), showing that the total is less or equal. Modify the price of an item on your list so that the solution is no longer cheap and re-run, so that you get a different solution.

Is it so fast that no further work is justified? If so, say so in the conclusions section of your report and post the lot to your prof/TA. You understood the task, thought about it, came up with a solution, implemented it, tested it with a representative dataset and so shown that functionality is demonstrable and performance is adequate - your assignment is over, go to the bar, think about the next one over a beer.

Upvotes: 1

Related Questions