Гекко не может найти решение небольшой проблемы - PullRequest
Новая
       20

Гекко не может найти решение небольшой проблемы

4 голосов
/ 28 апреля 2020

Я делаю некоторые тесты с библиотекой Gekko из python, и у меня есть небольшая проблема, в которой я знаю решение. Полный код выглядит следующим образом: 

from gekko import GEKKO

P = [[3.0,3.55,5.18,7.9,5.98],
    [1.56,1.56,2.48,3.15,2.38],
    [1.49,4.96,6.4,9.4,6.5]]

M = [[1,2,3,4,5],
     [6,7,8,9,10],
     [11,12,13,14,15]]

mm = M
pp = P
c1 = [300,200,150,250,180]
qtde = [10,10,10]
flex = [0.2,0.2,0.2]

m = GEKKO(remote=False)
ni = 3
nj = 5
x = [[m.Var(lb=0,integer=True) for j in range(nj)] for i in range(ni)]

s = 0
expr = []
for i in range(ni):
    for j in range(nj):
        s += x[i][j]*pp[i][j]
    expr.append(s)
    s = 0

for i in range(ni):
    for j in range(nj):
        if mm[i][j] == 0:
            m.Equation(x[i][j] == 0)


for i in range(len(flex)):
    if flex[i] == 0:
        m.Equation(sum([x[i][j] for j in range(nj)]) >= qtde[i])
    else:
        m.Equation(sum([x[i][j] for j in range(nj)]) >= qtde[i])
        m.Equation(sum([x[i][j] for j in range(nj)]) <= (1+flex[i])*qtde[i])


b = m.Array(m.Var,nj,integer=True,lb=0,ub=1)
iv = [None]*nj



for j in range(nj):
   iv[j] = m.sum([pp[i][j]*x[i][j] for i in range(ni)])
   m.Equation(iv[j] >= b[j]*c1[j])


m.Obj(m.sum(expr))

m.options.SOLVER=1 # switch to APOPT
m.solver_options = ['minlp_gap_tol 1.0e-2',\
                    'minlp_maximum_iterations 50000',\
                    'minlp_max_iter_with_int_sol 50000',\
                    'minlp_branch_method 1',\
                    'minlp_integer_leaves 2']


m.solve()    

for j in range(nj):
    m.Equation((1 - b[j])*iv[j] == 0)

m.options.SOLVER=1
m.solve()

Код завершается с ошибкой: Exception: @error: Solution Not Found. Что странно, поскольку существует ясное решение: 

x = [[0,0,12,0,0],
     [0,0,12,0,0],
     [0,0,12,0,0]]

Более странным является тот факт, что даже если я сильно увеличу значение переменной qtde (например, qtde = [40,40,40]), алгоритм не могу найти решение. Есть ли какая-то ошибка в том, как я пишу ограничения?

1 Ответ

4 голосов
/ 28 апреля 2020

Иногда решатели нуждаются в помощи с более точным начальным предположением или выборочными границами, чтобы избежать проблемных c решений. Вот кое-что, что помогает решить проблему только с одним решающим вызовом. 

lower = [0,0,4,0,0]
for i in range(ni):
    for j in range(nj):
        x[i][j].value = 5
        x[i][j].lower = lower[j]
        x[i][j].upper = 20

Я всегда получаю сообщение infeasible solution, если я устанавливаю нижнюю границу на ноль для всех единиц генерации. Похоже, решатель застревает при пробном решении всех нулей или когда все находятся ниже определенного порога. В этом случае я должен был ограничить средний блок выше 4, чтобы получить успешное решение, в то время как остальные находятся на нуле. Вот полный код: 

from gekko import GEKKO

P = [[3.0,3.55,5.18,7.9,5.98],
    [1.56,1.56,2.48,3.15,2.38],
    [1.49,4.96,6.4,9.4,6.5]]

M = [[1,2,3,4,5],
     [6,7,8,9,10],
     [11,12,13,14,15]]

mm = M
pp = P
c1 = [300,200,150,250,180]
qtde = [10,10,10]
flex = [0.2,0.2,0.2]

m = GEKKO(remote=False)
ni = 3
nj = 5
x = [[m.Var(integer=True) for j in range(nj)] for i in range(ni)]

# Fix x at values to check the feasibility of the initial guess
#x = [[m.Param() for j in range(nj)] for i in range(ni)]

lower = [0,0,4,0,0]
for i in range(ni):
    for j in range(nj):
        x[i][j].value = 5
        x[i][j].lower = lower[j]
        x[i][j].upper = 20

s = 0
expr = []
for i in range(ni):
    for j in range(nj):
        s += x[i][j]*pp[i][j]
    expr.append(s)
    s = 0

for i in range(ni):
    for j in range(nj):
        if mm[i][j] == 0:
            m.Equation(x[i][j] == 0)


for i in range(len(flex)):
    if flex[i] == 0:
        m.Equation(sum([x[i][j] for j in range(nj)]) >= qtde[i])
    else:
        m.Equation(sum([x[i][j] for j in range(nj)]) >= qtde[i])
        m.Equation(sum([x[i][j] for j in range(nj)]) <= (1+flex[i])*qtde[i])


b = m.Array(m.Var,nj,value=0.5,integer=True,lb=0,ub=1)
iv = [None]*nj



for j in range(nj):
   iv[j] = m.sum([pp[i][j]*x[i][j] for i in range(ni)])
   m.Equation(iv[j] >= b[j]*c1[j])


m.Obj(m.sum(expr))

for j in range(nj):
    m.Equation((1 - b[j])*iv[j] <= 1e-5)

print('Initial guess: ' + str(x))

# solve as NLP first to see iterations
#m.solver_options = ['minlp_as_nlp 1']
#m.options.SOLVER = 1
#m.solve(debug=0)



# solve as MINLP
m.options.SOLVER=1 # switch to APOPT
m.solver_options = ['minlp_gap_tol 1.0e-2',\
                    'minlp_maximum_iterations 50000',\
                    'minlp_max_iter_with_int_sol 50000',\
                    'minlp_branch_method 1',\
                    'minlp_integer_leaves 2']

m.options.SOLVER=1
m.solve(disp=False)

print('Final solution: ' + str(x))

При идеальном решателе начальное предположение не потребуется, и границы могут быть установлены от 0 до infinity. Некоторые проблемы труднее решить, например, проблемы со смешанными целочисленными переменными и при использовании условий дополнительности. Ваша проблема имеет и то и другое, поэтому я не удивлен, что решатель борется без первоначального предположения или соответствующих границ.

...