GEKKO背包优化达不到正确的结果

Question

尝试用GEKKO解决背包优化问题，但无法得到满意的结果。我有输入数据：

input_data = '30 100000\n90000 90001\n89750 89751\n10001 10002\n89500 89501\n10252 10254\n89250 89251\n10503 10506\n89000 89001\n10754 10758\n88750 88751\n11005 11010\n88500 88501\n11256 11262\n88250 88251\n11507 11514\n88000 88001\n11758 11766\n87750 87751\n12009 12018\n87500 87501\n12260 12270\n87250 87251\n12511 12522\n87000 87001\n12762 12774\n86750 86751\n13013 13026\n86500 86501\n13264 13278\n86250 86251\n'

我在 https://apmonitor.com/me575/index.php/Main/KnapsackOptimization

上找到了一个解决方案示例

from gekko import GEKKO

# parse the input
lines = input_data.split('\n')
firstLine = lines[0].split()
item_count = int(firstLine[0])
capacity = int(firstLine[1])

v = []
w = []

for i in range(1, item_count+1):
    line = lines[i]
    parts = line.split()
    v.append(int(parts[0])) 
    w.append(int(parts[1]))
    
# Create model
m = GEKKO(remote = False)
x = m.Array(m.Var,item_count,lb=0,ub=1,integer=True)
m.Maximize(m.sum([v[i]*x[i] for i in range(item_count)]))    
m.Equation(m.sum([w[i]*x[i] for i in range(item_count)]) <= capacity)
m.options.SOLVER = 1
m.solve()

value = int((m.options.objfcnval)*-1)
taken = []

for i in range(item_count):
    taken.append(int(x[i].value[0]))

我得到了以下结果：

value
>>> 99998
str(taken)
>>> '[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]'

但最优结果是：

>>> 99798
>>> '[0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0]'

请帮助我了解如何让 GEKKO 求解器正确完成工作？

Answer 1

尝试增加求解器容差。

m.options.RTOL = 1e-10
m.options.OTOL = 1e-10

m.solver_options = ['minlp_gap_tol 1.0e-5',\
                    'minlp_maximum_iterations 10000',\
                    'minlp_max_iter_with_int_sol 10000',\
                    'minlp_integer_tol 1e-8']

该解决方案需要更长的时间，但给出了正确的解决方案。

from gekko import GEKKO

input_data = '30 100000\n90000 90001\n89750 89751\n10001 10002\n89500 89501\n10252 10254\n89250 89251\n10503 10506\n89000 89001\n10754 10758\n88750 88751\n11005 11010\n88500 88501\n11256 11262\n88250 88251\n11507 11514\n88000 88001\n11758 11766\n87750 87751\n12009 12018\n87500 87501\n12260 12270\n87250 87251\n12511 12522\n87000 87001\n12762 12774\n86750 86751\n13013 13026\n86500 86501\n13264 13278\n86250 86251\n'

# parse the input
lines = input_data.split('\n')
firstLine = lines[0].split()
item_count = int(firstLine[0])
capacity = int(firstLine[1])

v = []
w = []

for i in range(1, item_count+1):
    line = lines[i]
    parts = line.split()
    v.append(int(parts[0])) 
    w.append(int(parts[1]))

print('v: ')
print(v[0:3])
print('w: ')
print(w[0:3])
print('capacity:')
print(capacity)
# Create model
m = GEKKO(remote = False)

m.options.RTOL = 1e-10
m.options.OTOL = 1e-10

m.solver_options = ['minlp_gap_tol 1.0e-5',\
                    'minlp_maximum_iterations 10000',\
                    'minlp_max_iter_with_int_sol 10000',\
                    'minlp_integer_tol 1e-8']

x = m.Array(m.Var,item_count,lb=0,ub=1,integer=True)

#sol1 = [1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
#sol2 = [0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0]
#for i,xi in enumerate(x):
#    xi.value = sol1[i]
m.Maximize(m.sum([v[i]*x[i] for i in range(item_count)]))
s = m.Var()
m.Equation(s==m.sum([w[i]*x[i] for i in range(item_count)]))
m.Equation(s <= capacity)
m.options.SOLVER = 1
m.solve()

value = int((m.options.objfcnval)*-1)
taken = []

for i in range(item_count):
    taken.append(int(x[i].value[0]))

print(taken)
print(s.value[0])

GEKKO背包优化达不到正确的结果

GEKKO knapsack Optimization can't reach the right result

python

optimization

knapsack-problem

gekko