壁虎背包优化无法达到正确的结果

Question

试图使用GEKKO来解决背包优化问题，但未能达到令人满意的结果。我有输入数据：

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

我在上找到了一个解决方案示例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 100000n90000 90001n89750 89751n10001 10002n89500 89501n10252 10254n89250 89251n10503 10506n89000 89001n10754 10758n88750 88751n11005 11010n88500 88501n11256 11262n88250 88251n11507 11514n88000 88001n11758 11766n87750 87751n12009 12018n87500 87501n12260 12270n87250 87251n12511 12522n87000 87001n12762 12774n86750 86751n13013 13026n86500 86501n13264 13278n86250 86251n'
# 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])