More Efficient Dynamic Programming of Product Sales

user_15205599 0
Viewed 114

I'm working on a dynamic programming problem and the problem requires selling a product over T time periods and maximizing the total actual sale amount. The total number of products is N and I plan to sell some products over different periods n0,n1,⋯,nT−1 and ∑ni=N. But the actual sale amount Si and sale price Pi are based on the below formulas. Assume that α=0.001 and π=0.5

  1. Initialize P=0. Then for i=0,1,…,T−1
  2. Compute new Pi=⌈0.5∗(Pi+ni)⌉
  3. At time i we sell Si = ⌈(1−αP^π)*ni⌉ products

For example, assume we already know $n_i$ for all periods, the trading will be below

    P = 0
    T = 4
    N = 10000
    alpha = 1e-3
    pi = 0.5
    S = np.zeros(T,dtype='i')
    n  = np.array([5000,1000,2000,2000])
    print(n)
    total = 0
    for i in range(T):
        P = math.ceil(0.5*(P + n[i]))
        S[i] = math.ceil((1 - alpha*P**pi)*n[i])
        total += S[i]
        print('at time %d, M = %d and we trade %d shares' %(i,M,S[i]))
    print('total sold =', total)

My idea is that this problem is dealing with quantity instead of price. Therefore, we should focus on something related to quantity, such as the moving average of the quantity. I'm still considering how to program it. Could someone provide ideas about dynamic programming? Thank you very much. The below is some of my crude codes.

def DPcrude(N,T,alpha,pi,S):
    for k in range(1, T):
        t = T - k - 1
        for n in range(0,N+1):
            best = -1

            for sell in range(0,n):
                newprice = 
                salenow = 
                salelater = 
                candidate = salenow + salelater
                if candidate > best:
                    best = candidate
            S[t,a,n] = best

N = 1000
T = 10
pi = .5
alpha = 1e-2
dynamic-programming algorithm python
2 Answers

Your current method has complexity O(N^T). Dynamic programming can be used to reduce this to O(T.N^3) which should be more efficient for values of T of 4 and higher.

Note that the problem has the following properties:

  1. A higher price results in fewer sales
  2. A higher price at a particular time results in higher prices later (if the same subsequent choices for ni are made)

This means that you can solve with dynamic programming the subproblem of what is the lowest price that can be achieved for each number of sales:

  1. with exactly t time periods
  2. with the ni for the t time periods summing to n

To compute this subproblem requires looping over the choices for the number in the final time period, and combining choices from previous subproblems.

Note that solving the subproblem gives an array of up to N results, where entry k in the array gives the lowest price for getting exactly k sales.

There are O(T.N) subproblems, and each subproblem requires O(N^2) to solve for a total complexity of O(T.N^3).

user_11393930

You will not be able to apply dynamic programming to this problem, unless you're able to apply some mathematical wizardry to put some bounds on the effects of the price P.

Dynamic programming relies on the problem having the optimal substructure property. From wikipedia:

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

However, your problem does not exhibit this property- if we calculate the optimal solution for T intervals and N items, we cannot use that solution for T+1 intervals and N+K items, because the price in the T+1 problem is dependent on the T interval price. A sub-solution with a higher price P (for the last interval) but suboptimal profits overall may still be used to construct the optimal profit for T+1, because of the increased price P. This prevents us from appling dynamic programming.

user_62210240
Related