pythonoptimizationlinear-programminggekkomixed-integer-programming

Time-based spacing constraints in Gekko


I'm trying to constrain the vector output of "simu_total_volume" below by requiring that solution output elements (x7=1) be spaced apart by s records (weeks) while also controlling for the maximum number of times x7 can be = 1 in total.

The code below seems to work but I'm noticing a reduction in the sum of x7 from 10 (without the spacing requirement) to 8 (with the spacing requirement) despite there being enough space for sum(x7) to = 10 given the constraints. I can also manually arrange the full solution space and here and come up with a more optimal solution in Excel, so I'm not sure why Gekko isn't finding it.

Here are the full details to reproduce locally (tested for accuracy):

import numpy as np
from gekko import GEKKO
m = GEKKO(remote=False)
m.options.NODES = 3
m.options.IMODE = 3
m.options.MAX_ITER = 1000

lnuc_weeks = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

min_promo_price = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,3]

max_promo_price = [3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5, 3.5,3.5, 3.5, 3.5, 3.5, 3.5, 3.5]

base_srp = [3.48, 3.48, 3.48, 3.48, 3.0799, 3.0799, 3.0799, 3.0799,3.0799, 3.0799, 3.0799, 3.0799, 3.0799, 3.0799, 3.0799, 3.0799, 3.0799, 3.0799, 3.0799]

lnuc_min_promo_price = 1.99

lnuc_max_promo_price = 1.99

coeff_fedi = [0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589,0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589, 0.022589]

coeff_feao = [0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995, 0.02929995]

coeff_diso = [0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338, 0.05292338]

sumproduct_base = [0.20560305, 0.24735297, 0.24957423, 0.23155435, 0.23424058,0.2368096 , 0.27567109, 0.27820648, 0.2826393 , 0.28660598, 0.28583971, 0.30238505, 0.31726649, 0.31428312, 0.31073792, 0.29036779, 0.32679041, 0.32156337, 0.24633734]

neg_ln = [[0.14842000515],[0.14842000512],[0.14842000515],[0.14842000512],[-0.10407483058],[0.43676249024],[0.43676249019],[0.43676249024],[0.43676249019],[0.43676249024],[0.43676249019], [0.026284840258],[0.026284840291],[0.026284840258],[0.026284840291], [0.026185109811],[0.026284840258],[0.026284840291],[0.026284840258]]

neg_ln_ppi_coeff = [1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879,1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879, 1.22293879,1.22293879, 1.22293879, 1.22293879, 1.22293879]

base_volume = [124.38, 193.2, 578.72, 183.88, 197.42, 559.01, 67.68, 110.01,60.38, 177.11, 102.65, 66.02, 209.83, 81.22, 250.44, 206.44, 87.99, 298.95, 71.07]

week = pd.Series([13, 14, 17, 18, 19, 26, 28, 33, 34, 35, 39, 42, 45, 46, 47, 48, 50, 51, 52])


n = 19

x1 = m.Array(m.Var,(n), integer=True) #LNUC weeks

i = 0
for xi in x1:
    xi.value = lnuc_weeks[i]
    xi.lower = 0
    xi.upper = lnuc_weeks[i]
    i += 1

x2 = m.Array(m.Var,(n)) #Blended SRP

i = 0
for xi in x2:
    xi.value = 5
    m.Equation(xi >= m.if3((x1[i]) - 0.5, min_promo_price[i], lnuc_min_promo_price))
    m.Equation(xi <= m.if3((x1[i]) - 0.5, max_promo_price[i], lnuc_max_promo_price))
    i += 1
x3 = m.Array(m.Var,(n), integer=True) #F&D
x4 = m.Array(m.Var,(n), integer=True) #FO
x5 = m.Array(m.Var,(n), integer=True) #DO
x6 = m.Array(m.Var,(n), integer=True) #TPR

#Default to F&D
i = 0
for xi in x3:
    xi.value = 1
    xi.lower = 0
    xi.upper = 1
    i += 1

i = 0
for xi in x4:
    xi.value = 0
    xi.lower = 0
    xi.upper = 1
    i += 1

i = 0
for xi in x5:
    xi.value = 0
    xi.lower = 0
    xi.upper = 1
    i += 1

i = 0
for xi in x6:
    xi.value = 0
    xi.lower = 0
    xi.upper = 1
    i += 1

x7 = m.Array(m.Var,(n), integer=True) #Max promos

i = 0
for xi in x7:
    xi.value = 1
    xi.lower = 0
    xi.upper = 1
    i += 1

x = [x1,x2,x3,x4,x5,x6,x7]

neg_ln=[m.Intermediate(-m.log(x[1][i]/base_srp[i])) for i in range(n)]

total_vol_fedi  =[m.Intermediate(coeff_fedi[0]+ sumproduct_base[i] + (neg_ln[i]*neg_ln_ppi_coeff[0])) for i in range(n)]
total_vol_feao  =[m.Intermediate(coeff_feao[0]+ sumproduct_base[i] + (neg_ln[i]*neg_ln_ppi_coeff[0])) for i in range(n)]
total_vol_diso  =[m.Intermediate(coeff_diso[0]+ sumproduct_base[i] + (neg_ln[i]*neg_ln_ppi_coeff[0])) for i in range(n)]
total_vol_tpro  =[m.Intermediate(sumproduct_base[i] + (neg_ln[i]*neg_ln_ppi_coeff[0])) for i in range(n)]

simu_total_volume = [m.Intermediate((
(m.max2(0,base_volume[i]*(m.exp(total_vol_fedi[i])-1)) * x[2][i] +
m.max2(0,base_volume[i]*(m.exp(total_vol_feao[i])-1)) * x[3][i] +
m.max2(0,base_volume[i]*(m.exp(total_vol_diso[i])-1)) * x[4][i] +
m.max2(0,base_volume[i]*(m.exp(total_vol_tpro[i])-1)) * x[5][i]) + base_volume[i]) * x[6][i]) for i in range(n)]


[m.Equation(x3[i] + x4[i] + x5[i] + x6[i] == 1) for i in range(i)]

#Limit max promos
m.Equation(sum(x7)<=10)

#Enforce spacing
s=1
for s2 in range(1, s+1):
    for i in range(0, n-s2):
        f = week[week == week[i] + s2].index
        if len(f)>0:
            m.Equation(x7[i] + x7[f[0]]<=1)

m.Maximize(m.sum(simu_total_volume))

m.options.SOLVER=1

m.solve(disp = True)

Solution

  • Enforce a spacing constraint with a summation over a subset of the periods with a moving window such as:

    m.Equation(sum(x[0:3])<=1)
    m.Equation(sum(x[1:4])<=1)
    m.Equation(sum(x[2:5])<=1)
    

    Here is a test that shows solutions with different spacing constraints with a maximum of 4 out of the 5 selected. The spacing constraints are successively [0,1,2,3]:  

    from gekko import GEKKO
    m = GEKKO(remote=False)
    
    for s in [0,1,2,3]:
        n = 5
        x = m.Array(m.Var,n,integer=True,value=1,lb=0,ub=1)
        m.Equation(sum(x)<=4)
        for i in range(0,n-s):
           m.Equation(sum(x[i:i+s+1])<=1)
           
        m.Maximize(sum(x))
    
        m.options.SOLVER=1
        m.solve(disp=False)
        print(f'spacing: {s} solution: {x}')
    

    The solution is:

    spacing: 0 solution: [[0.0] [1.0] [1.0] [1.0] [1.0]]
    spacing: 1 solution: [[1.0] [0.0] [1.0] [0.0] [1.0]]
    spacing: 2 solution: [[0.0] [1.0] [0.0] [0.0] [1.0]]
    spacing: 3 solution: [[1.0] [0.0] [0.0] [0.0] [1.0]]
    

    There are multiple solutions for the case with spacing 0 and 2 and unique solutions for spacing 1 and 3. The solver returns just one of the solutions for each case. You may need to add an additional objective if there is a preference to select earlier slots.