Optimal sequence of non-overlapping purchases

Question

I think this is a scheduling problem, but I'm not even sure on that much! What I want is to find the optimal sequence of non-overlapping purchase decisions, when I have full knowledge of their value and what opportunities are coming up in the future. Imagine a wholesaler who sells various goods that I want to buy for my own shop. At any time they may have multiple special offers running; I will sell at full price, so their discount is my profit. I want to maximize profit, but the catch is that I can only buy one thing at a time, and no such thing as credit, and worse, there is a delivery delay. The good news is I will sell the items as soon as they are delivered, and I can then go spend my money again. So, one path through all the choices might be: I buy 100kg apples on Monday, they are delivered on Tuesday. I then buy 20 nun costumes delivered, appropriately enough, on Sunday. I skip a couple of days, as I know on Wednesday they'll have a Ferrari at a heavy discount. So I buy one of…

Accepted Answer

The simplest way to think of this problem is as analogous to a shortest-path problem (although treating it as a maximum flow problem probably is technically better). The day numbers, 1 ... 19, can be used as node names; each node j has a link to node j+1 with weight 1, and each product (b,d,g,p) in the list adds a link from day b to day d+1 with weight g. As we progress through the nodes when path-finding, we keep track of the best multiplied values seen so far at each node.

The Python code shown below runs in time O(V+E) where V is the number of vertices (or days), and E is the number of edges. In this implementation, E = V + number of products being sold. Added note: The loop for i, t in enumerate(graf): treats each vertex once. In that loop, for e in edges: treats edges from the current vertex once each. Thus, no edge is treated more than once, so performance is O(V+E).

Edited note 2: krjampani claimed that O(V+E) is slower than O(n log n), where n is the number of products. However, the two orders are not comparable unless we make assumptions about the number of days considered. Note that if delivery delays are bounded and product dates overlap, then number of days is O(n) whence O(V+E) = O(n), which is faster than O(n log n).

However, under a given set of assumptions the run time orders of my method and krjampani's can be the same: For large numbers of days, change my method to create graph nodes only for days in the sorted union of x[0] and x[1] values, and using links to day[i-1] and day[i+1] instead of to i-1 and i+1. For small numbers of days, change krjampani's method to use an O(n) counting sort.

The program's output looks like the following:

```
 16 :   2.36992 [11, 15, 1.4, 'Yellow Ferrari']
 11 :   1.6928 [8, 10, 1.15, 'Red shoes']
 8 :    1.472 [4, 7, 1.28, 'Priest costumes']
 4 :    1.15 [1, 3, 1.15, 'Viagra']
```

which indicates that we arrived at day 16 with compounded profit of 2.36992, after selling Yellow Ferrari's on day 15; arrived at day 11 with profit 1.6928, after selling Red shoes; and so forth. Note, the dummy entry at the beginning of the products list, and removal of quotes around the numbers, are the main differences vs the JSON data. The entry in list element `graf[j]` starts out as `[1, j-1, 0, [[j+1,1,0]]]`, that is, is of form [best-value-so-far, best-from-node#, best-from-product-key, edge-list]. Each edge-list is a list of lists which have form [next-node#, edge-weight, product-key]. Having product 0 be a dummy product simplifies initialization.

```
products = [[0,0,0,""],[1,2,1.10,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.30,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.50,"Red Ferrari"],[11,15,1.40,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.30,"Organic wine"]]
hiDay = max([x[1] for x in products])
graf = [[1, i-1, 0, [[i+1,1,0]]] for i in range(2+hiDay)]

for i, x in enumerate(products):
    b, d, g, p = x[:]
    graf[b][3] += [[d+1, g, i]] # Add an edge for each product

for i, t in enumerate(graf):
    if i > hiDay: break
    valu = t[0]                 # Best value of path to current node
    edges = t[3]                # List of edges out of current node
    for e in edges:
        link, gain, prod = e[:]
        v = valu * gain;
        if v > graf[link][0]:
            graf[link][0:3] = [v, i, prod]

day = hiDay
while day > 0:
    if graf[day][2] > 0:
        print day, ":	", graf[day][0], products[graf[day][2]]
    day = graf[day][1]
```

Optimal sequence of non-overlapping purchases

Solution

Problem

Related problems