Gekko Apopt решает, но не оптимизирует

Apopt Gekko решает, но не оптимизирует двоичный список с ограничениями.

Кто-нибудь когда-нибудь попадал в это?

У меня есть код, который берет 2 таблицы из Excel и пытается оптимизировать контейнеры по грузовикам с несколькими ограничениями. Кажется, он отлично работает с ограничениями, но я очень легко вижу, что он не оптимизирует загрузку контейнеров на грузовики ...

Любые идеи?

import numpy as np
from gekko import GEKKO

containers = [[1, 10, 0, 0, 0, 0, 1], [2, 20, 1, 0, 0, 0, 1], [3, 40, 0, 1, 
0, 0, 2], [4, 40, 0, 0, 0, 0, 3], [5, 10, 1, 0, 0, 0, 4], [6, 20, 0, 0, 0, 0, 
1], [7, 20, 0, 0, 0, 0, 1], [8, 40, 0, 0, 0, 0, 1], [9, 10, 1, 0, 0, 0, 1], 
[10, 10, 0, 0, 0, 0, 1], [11, 40, 0, 0, 0, 0, 1], [12, 40, 1, 0, 0, 0, 1], 
[13, 10, 0, 0, 0, 0, 1], [14, 20, 1, 0, 0, 0, 1], [15, 40, 1, 0, 0, 0, 1], 
[16, 40, 0, 0, 0, 0, 1], [17, 20, 0, 1, 0, 0, 1], [18, 10, 0, 0, 0, 0, 1], 
[19, 20, 0, 0, 0, 0, 1], [20, 10, 0, 0, 0, 0, 1], [21, 40, 0, 0, 0, 0, 1], 
[22, 40, 0, 0, 0, 0, 1], [23, 20, 0, 0, 0, 0, 1], [24, 10, 0, 0, 0, 0, 1], 
[25, 20, 0, 0, 0, 0, 1], [26, 40, 0, 0, 0, 0, 1], [27, 40, 0, 0, 0, 0, 1]]
trucks = [[11, 'D2', 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [22, 'D3', 
40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [33, 'E1', 40, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0], [44, 'D4', 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
[45, 'D5', 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [46, 'D6', 40, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [47, 'D7', 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0], [48, 'D8', 40, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [49, 
'D9', 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [50, 'D10', 40, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0], [51, 'D11', 40, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0], [52, 'D12', 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
m=GEKKO()
m.options.SOLVER = 1
match_matrix = []

#Creating the match matrix vars
for i in range(len(trucks)):
    match_matrix.append([])
    for j in range(len(containers)):
        match_matrix[i].append(m.Var(integer=True,lb=0,ub=1))

#Constraint - total loading size not larger than truck size
for i in range(len(trucks)):
    load_size = 0
    truck_size = trucks[i][2]
    for j in range(len(containers)):
        container_size = containers[j][1]
        load_size = load_size + match_matrix[i][j] * container_size
    m.Equation(load_size<=truck_size)

#Constraint - each container will be loaded once (maximum)
for j in range(len(containers)):
    number_of_loads = 0
    for i in range(len(trucks)):
        number_of_loads += match_matrix[i][j]
    m.Equation(number_of_loads<=1)


#Creating the objective
total_containers_size_on_truck = 0
for i in range(len(trucks)):
    for j in range(len(containers)):
        container_size = containers[j][1]
        total_containers_size_on_truck += match_matrix[i][j] * 
        container_size

#solving
m.Obj(-total_containers_size_on_truck)
m.options.SOLVER = 1
m.solve()


#Printing

for i in range(len(trucks)):
    output = "Truck %d (size: %d):" % (i+1, trucks[i][2])
    for j in range(len(containers)):
        if match_matrix[i][j].value[0] == 1:
            output += "%d(%d), " % (j+1, containers[j][1])
    print (output)

Таким образом, решатель решает проблему, но не максимизирует максимальную ..

Любые идеи?


person Cheetaa Tiger    schedule 25.04.2020    source источник
comment
Спасибо, что обратились за помощью по своей проблеме. Не могли бы вы опубликовать код, с которым вы работаете, чтобы мы могли помочь?   -  person John Hedengren    schedule 26.04.2020
comment
Спасибо, что разместили свой код. У вас есть простая таблица, которая могла бы заменить trucks.xlsx, чтобы код мог работать и отображать вашу проблему? Вы можете создать небольшую таблицу с 3 грузовиками с ограничениями по загрузке для каждого.   -  person John Hedengren    schedule 26.04.2020
comment
файл контейнеров drive.google.com/file/ файл грузовиков drive.google.com/file/d/1BMGMypDZqq/file/d/1BMGMypDZqq   -  person Cheetaa Tiger    schedule 26.04.2020
comment
Было бы лучше, если бы вы могли создать образцы данных в исходном вопросе. Я думаю, что большинство людей не захотят загружать документ из Интернета, особенно с возможностью макросов в Excel.   -  person John Hedengren    schedule 29.04.2020
comment
Спасибо за желание помочь! Я только что отредактировал пост :)   -  person Cheetaa Tiger    schedule 29.04.2020
comment
Спасибо за добавление изображений. Еще лучше, если вы можете включить несколько матриц вверху своего сообщения, аналогичных stackoverflow.com/questions/61469170/ и stackoverflow.com/questions/61109450/ Вот несколько советов для создания минимальной воспроизводимой проблемы, чтобы показать проблему, с которой вы столкнулись: stackoverflow.com/help/minimal-reproducible-example В противном случае мне нужно было бы ввести матрицу из вашего изображения.   -  person John Hedengren    schedule 29.04.2020
comment
Это не обязательно должна быть полная матрица, но, возможно, всего 2-3 грузовика, чтобы продемонстрировать, с чем вы имеете дело по проблеме.   -  person John Hedengren    schedule 29.04.2020
comment
Спасибо, что помог мне изучить бизнес здесь .. Я только что отредактировал сообщение - Добавление данных в код списками + минимизация кода. Спасибо еще раз!   -  person Cheetaa Tiger    schedule 29.04.2020
comment
Кроме того, я добавил более 2-3 грузовиков и контейнеров, чтобы продемонстрировать проблему, с которой я столкнулся .. Спасибо :)   -  person Cheetaa Tiger    schedule 29.04.2020


Ответы (1)


Возможно, вам потребуется изменить настройки решателя APOPT, чтобы получить лучшее решение. Вот варианты APOPT, которые я рекомендую для решения вашей проблемы.

m.solver_options = ['minlp_gap_tol 0.5',\
                    'minlp_maximum_iterations 10000',\
                    'minlp_max_iter_with_int_sol 10000']

С этими параметрами задача сходится за 952 итераций со следующим результатом:

--Integer Solution:  -3.10E+02 Lowest Leaf:  -4.80E+02 Gap:   4.30E-01
Iter:   952 I:  0 Tm:      0.01 NLPi:    2 Dpth:   40 Lvs:  498 Obj: -3.10E+02 Gap:  4.30E-01
 Successful solution

 ---------------------------------------------------
 Solver         :  APOPT (v1.0)
 Solution time  :    20.8784000000014      sec
 Objective      :   -310.000000000000     
 Successful solution
 ---------------------------------------------------

Truck 1 (size: 40):13(10), 17(20), 
Truck 2 (size: 40):3(40), 
Truck 3 (size: 40):5(10), 
Truck 4 (size: 40):26(40), 
Truck 5 (size: 40):10(10), 19(20), 
Truck 6 (size: 40):25(20), 
Truck 7 (size: 40):14(20), 24(10), 
Truck 8 (size: 40):20(10), 
Truck 9 (size: 40):6(20), 9(10), 
Truck 10 (size: 40):23(20), 
Truck 11 (size: 40):2(20), 
Truck 12 (size: 40):1(10), 7(20),

Даже при уменьшении допуска зазора MINLP решающая программа продолжает выполнение 10 000 итераций, но не находит лучшего решения. Если это не оптимальное решение, вы можете попробовать дать ему больше итераций, чтобы найти лучшее решение, или дать лучшее первоначальное предположение.

person John Hedengren    schedule 29.04.2020
comment
Спасибо за супербыстрый ответ! Пытался открыть его на 100 КБ, но, к сожалению, он все еще не работает .. Вы можете видеть, что в нем осталось несколько 40-футовых контейнеров, которые по какой-то причине не загружаются ... - person Cheetaa Tiger; 29.04.2020
comment
Не могли бы вы объяснить результат? Я не уверен, на что я смотрю в распечатанных результатах. - person TexasEngineer; 29.04.2020
comment
Я думаю, что вывод: Truck # (size: size): Индекс контейнера (количество), Индекс контейнера (количество), но мне понадобится @Cheetaa Tiger для подтверждения. - person John Hedengren; 29.04.2020
comment
Его Turck # (Размер: общий размер грузовика для загрузки): Индекс контейнера (размер контейнера) Спасибо, ребята - person Cheetaa Tiger; 29.04.2020
comment
Пробовал со 100 тыс. Итераций, получилось немного лучше, но все еще не оптимально. Время решения для меня немного замедляется, думаю, мне нужно будет найти другой движок ... - person Cheetaa Tiger; 29.04.2020
comment
Хорошая идея, чтобы осмотреться. В APOPT есть и другие опции, которые могут ускорить работу. Если ваша проблема является смешанной целочисленной линейной (а не нелинейной), вы увидите большое улучшение с помощью решателя, такого как Gurobi или CPLEX (оба коммерческих решателя). - person John Hedengren; 30.04.2020