Help me with this algorithm prog

Alright /prog/, I'm coming here for help with an algorithm I've been trying to solve but I think the problem may be intractable.

Essentially, I have n unique thing I want to buy in a market with m sellers. Not all of the m sellers sell each items. I want to construct a set of purchases so that I buy all n items the cheapest way possible. This problem, in its current form, is quite easy and can be solved by greedily buying from the cheapest offer for each item.

Here is the hard part: for these items, transactions can only be made in whole units, however items are priced to 3 decimals. Therefor if I buy something for 1.550, I end up paying 2 for it. If I buy 2 items for 1.550 and 1.300 from a seller however, I end up paying only 3 for them. How can I compute the most efficient way to buy all the items? Keep in mind my input size may be up to 200 items and 20 (possibly) unique sellers per item?

Going with the cheapest still produces the optimal result.

No it does not: observe the following scenario:

Given items a, b, c and sellers s1, s2..
S#:# indicates S# sells the item for #

a: S1: 1.1, S2: 1.4
b: S1: 1.9, S2: 1.1
c: S1: 1.1, S2: 1.4

Using a greedy approach you would but item a and c from S1, totalling 2.2 (rounded up to 3 since you can only purchase in whole units), and b from S2 for 1.1 (rounded up again to 2). This yields a total purchase of 5 units. If you buy each item from S2 however, you only spend 4 units

Oh yea, and after analyzing my data set it appears there may be up to 200 unique sellers per item instead of 20 as I thought @_@.

that actually sounds pretty challenging...

you could have an array of items and an array of baskets
each item contains information about the price it was paid for and the corresponding basket, together with the averaged extra that had to be paid for the basket price to reach a whole number
each basket contains the items in it and their price, and the seller, so for each seller can be only one basket

my idea would be to iterate the m sellers and make a basket of every of them with all they sell, this means associated will be k averaged values of item where k is the number of sellers that sell that item

one you have all the averaged baskets you know, for each item, whose basket has the least loss, then you remove the item from all other baskets and redo the overhead costs, and move to the next item. the point is that if later on you remove an item that was on a previous basket, the loss for that item should still be supported by the overall gain of the other baskets, maybe, I need to test this

It's not particularly hard to implement a solution, but the problem is NP-complete so it's always going to suck.

OP here, I have implemented the greedy solution and brute force solution, however the brute force solution takes >10 minutes on n=8 things to buy and it has been running for 3 hours so far on n=15. On problems with n<=8, it produces the exact same answer as the greedy solution however I'm assuming with more input this will not be the case. My goal now is to develop a heuristic to come close to the optimal solution within a reasonable time frame. My current idea is to start with the greedy solution, then try to minimize seller "waste". What do you guys think?

>>7

sounds good. You can bound the round up cost of buying from n sellers by n units. So if you are buying from 200 sellers, the greedy solution might put you 200 units over! This is an interesting problem OP. It's definitely worst looking into for an efficient solution.

I think the problem can be stated with matrices.

Let C be a known cost matrix, where C(i,j) is the cost in units of one item of type j, being bought from supplier i.

Let Q be a known quantity vector, where Q(j) is the integer representing the desired quantity of item j.

We will find a purchase matrix, P, where P(i,j) is the quantity of items of type j, bought from from supplier i. In order for P to be valid we must have that \sum_{i \in suppliers} P(i,j) = Q(j), and P(i,j) >= 0.

Consider a utility function u(P), defined as:

u(P) = \sum_{i \in suppliers}( \ceiling( \sum_{j \in items}( C(i,j)*P(i,j) ) ) )

Choose a valid P that minimizes u(P).

One thing I'd like to know is what are the bounds of the prices? 1 and 2? 0-infinity?

This sounds like a job for OpenCL bro, just create all possible purchases and look for the cheapest one. FLOPS are what fucking gpus were designed for

>>1
items are priced to 3 decimals

>>10
FLOPS

No. FIXED POINT

Here's a naive python solution that start with the greedy solution and converges to some local optimum.

Can you tell FIOC is not my native language?


#!/usr/bin/env python
from decimal import *
from math import ceil
from fileinput import input
from collections import defaultdict
from itertools import permutations

market = defaultdict(dict)
orders = {}

for line in input():
    item, offers = line.split(": ", 1)
    for offer in offers.split(", "):
        seller, price = offer.split(":")
        orders[seller] = set()
        market[item][seller] = Decimal(price)

# greedy solution
for item, offer in market.items():
    cheapest = min(offer, key=offer.get)
    orders[cheapest].add(item)


def price(seller, items):
    sum = 0
    for item in items:
        sum += market[item][seller]
    return int(ceil(sum))

def total(orders):
    sum = 0
    for (seller, items) in orders.items():
        sum += price(seller, items)
    return sum

print orders
print total(orders)

def consolidate(orders):
    bestsavings = 0
    bestorderpair = None
    for orderpair in permutations(orders.items(), 2):
        seller1, items1 = orderpair[0]
        seller2, items2 = orderpair[1]
        separateprice = price(seller1, items1) + price(seller2, items2)
        combinedprice = price(seller1, items1.union(items2))
        savings = separateprice - combinedprice
        if(savings > bestsavings):
            bestsavings = savings
            bestorderpair = orderpair
   
    if(bestsavings > 0):
        seller1, items1 = bestorderpair[0]
        seller2, items2 = bestorderpair[1]
        orders[seller1] = items1.union(items2)
        orders[seller2] = set()
        return True
    return False

while(consolidate(orders)):
    pass

print orders
print total(orders)

bampu pantsu