google or-tools не может достичь оптимального результата LP, как в примере gurobi

Я пытаюсь решить задачу из классической книги по математическому программированию П. Уильямса с помощью OR-Tools от Google. Тот же пример используется в демонстрации Gurobi: http://www.gurobi.com/resources/examples/food-manufacture-I

Мое решение близко к оптимальному, но не соответствует ответу из образца Гуроби (на самом деле это тот, который указан как правильный в книге).

Я проверил решение OR-tools на предмет ограничений, все выглядит правильно, но не соответствует оптимальному ответу.

Я что-то делаю не так, или это из-за какого-то ограничения алгоритма GLOP OR-tools по сравнению с Gurobi.

Ссылка на мой код GitHub: https://github.com/APA092/optimum_global/blob/master/food_produce.py

from ortools.linear_solver import pywraplp

def main():
    data = [[110, 120, 130, 110, 115],
            [130, 130, 110, 90, 115],
            [110, 140, 130, 100, 95],
            [120, 110, 120, 120, 125],
            [100, 120, 150, 110, 105],
            [90, 100, 140, 80, 135]
        ];

    char = [8.8, 6.1, 2, 4.2, 5];

    solver = pywraplp.Solver('Linear_test', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

#create variables
    buy = [[0 for x in range(len(data[0]))] for y in range(len(data))] 
    produce = [[0 for x in range(len(data[0]))] for y in range(len(data))] 
    store = [[0 for x in range(len(data[0]))] for y in range(len(data))] 

    for i in range(0, len(data)):
        for j in range(0, len(data[0])):
            buy[i][j] = solver.NumVar(0, solver.infinity(), 'buy')
            produce[i][j] = solver.NumVar(0, solver.infinity(), 'produce')
            store[i][j] = solver.NumVar(0, solver.infinity(), 'store')

#create objective
    objective = solver.Objective()
    for i in range(0, len(buy)):
        for j in range(0, len(buy[0])):
            objective.SetCoefficient(buy[i][j], data[i][j]*(-1))
            objective.SetCoefficient(produce[i][j], 150)
            objective.SetCoefficient(store[i][j], -5)
    objective.SetMaximization()

#create constraints
    #production not higher than capacity of machine 1
    constraint1 = [0]*len(produce)
    for i in range(0, 6):
        constraint1[i] = solver.Constraint(0, 200)
        for j in range(0, 2):
            constraint1[i].SetCoefficient(produce[i][j],1)

    #production not higher than capacity of machine 2
    constraint2 = [0]*len(produce)
    for i in range(0, 6):
        constraint2[i] = solver.Constraint(0, 250)
        for j in range(2, 5):
            constraint2[i].SetCoefficient(produce[i][j],1)

    #production not higher than resources available
    constraint3 = [[0 for x in range(len(data[0]))] for y in range(len(data))]
    for i in range(0, len(produce)):
        for j in range(0, len(produce[0])):
            constraint3[i][j] = solver.Constraint(0, solver.infinity())
            constraint3[i][j].SetCoefficient(produce[i][j], -1)
            constraint3[i][j].SetCoefficient(store[i][j], 1)
            constraint3[i][j].SetCoefficient(buy[i][j], 1)

    #storage limited to 1000 units
    constraint4 = [[0 for x in range(len(data[0]))] for y in range(len(data))]        
    for i in range(0, len(produce)):
        for j in range(0, len(produce[0])):    
            constraint4[i][j] = solver.Constraint(0, 1000)
            constraint4[i][j].SetCoefficient(store[i][j], 1)

    #initial storage
    constraint5 = [0]*len(store[0])
    for i in range(0, len(store[0])):
        constraint5[i] = solver.Constraint(500, 500)
        constraint5[i].SetCoefficient(store[0][i],1)
        constraint5[i].SetCoefficient(buy[0][i],-1)
        constraint5[i].SetCoefficient(produce[0][i],1)

    #final storage
    constraint6 = [0]*len(store[0])
    for i in range(0, len(store[0])):
        constraint6[i] = solver.Constraint(500, 500)
        constraint6[i].SetCoefficient(store[4][i],1)
        constraint6[i].SetCoefficient(buy[5][i],1)
        constraint6[i].SetCoefficient(produce[5][i],-1)

    #linking storage and production
    constraint7 = [[0 for x in range(len(data[0]))] for y in range(len(data))]
    for i in range(1,6):
        for j in range(0,len(data[0])):
            constraint7[i][j] = solver.Constraint(0, 0)
            constraint7[i][j].SetCoefficient(store[i-1][j],1)
            constraint7[i][j].SetCoefficient(store[i][j],-1)
            constraint7[i][j].SetCoefficient(buy[i][j],1)
            constraint7[i][j].SetCoefficient(produce[i][j],-1)

    #products characteristics HIGH
    constraint7 = [0]*len(produce)
    for i in range(0, len(produce)):
        constraint7[i] = solver.Constraint(-solver.infinity(), 0)
        for j in range(0, len(produce[0])):
            constraint7[i].SetCoefficient(produce[i][j], char[j]-6)

    #products characteristics LOW
    constraint8 = [0]*len(produce)
    for i in range(0, len(produce)):
        constraint8[i] = solver.Constraint(0, solver.infinity())
        for j in range(0, len(produce[0])):
            constraint8[i].SetCoefficient(produce[i][j], char[j]-3)




    solver.Solve()
    storage_cost = 0
    revenue = 0
    purchase_cost =0

    for i in range(0, len(produce)):
        for j in range(0, len(produce[0])):
            purchase_cost += data[i][j]*buy[i][j].solution_value()
            revenue += 150*produce[i][j].solution_value()
            storage_cost += 5*store[i][j].solution_value()


    profit = revenue - storage_cost - purchase_cost

    print "Profit - " + str(profit)
    print "Revenue - " + str(revenue)
    print "Storage Cost - " + str(storage_cost)
    print "Purchase Cost - " + str(purchase_cost)

person Alexey Parilov    schedule 17.10.2018    source источник
comment
Лучше, если вы вставите в вопрос актуальный код, а не ссылку.   -  person AS Mackay    schedule 17.10.2018
comment
спасибо за совет, добавил   -  person Alexey Parilov    schedule 17.10.2018
comment
Я бы сказал, что маловероятно, что решатель ядра сломан, поскольку существует множество математических гарантий (например, из теории двойственности). Со стороны API это более вероятно, но, вероятно, это проблема чистого моделирования. Проблема может и так достаточно сложна, чтобы затруднить рассуждение вручную. Поэтому я рекомендую сделать обычное дело: уменьшить проблему. Продукты; в дни. Тогда рассуждать об этом намного проще. Конечно, это может сделать некоторые проблемы невидимыми, но, возможно, поможет другое сокращение. Полная отладка модели хлопотна.   -  person sascha    schedule 17.10.2018
comment
Другой подход заключается в удалении одного / или нескольких блоков ограничений, где вы увидите, что 2, 3 или даже более полных удаления ограничений / блоков приведут к решениям, которые уже ниже, чем ваша цель. Тогда легко сказать, что оставшиеся блоки содержат некоторую проблему.   -  person sascha    schedule 17.10.2018
comment
Насколько отличается ваш ответ? Находится ли это в пределах допусков решателя? Другой распространенный прием отладки - это добавление ограничений, которые фиксируют значения решения для некоторых или всех переменных к ожидаемым значениям. Затем, если ваша модель ошибочна, вы получите другие переменные с другими значениями, чем ожидалось, или модель будет неосуществимой, что даст вам больше подсказок.   -  person TimChippingtonDerrick    schedule 18.10.2018
comment
разница в результатах небольшая, но все же заметная. Оптимальный результат OR-tools - 106'605, Гуроби и книга показывают 107'843. Я смоделировал результат с помощью решения Gurobi и похоже, что их цифры не соответствуют требованиям кейса на 100%. Не вдаваясь в подробности, есть ограничение, называемое твердостью, оно должно быть <= 6. В решении Гуроби через несколько месяцев это 6,000244444. Это может быть причиной (правила округления (?)). В качестве следующего шага отправлю им электронное письмо.   -  person Alexey Parilov    schedule 18.10.2018
comment
Coin LP возвращает то же решение, что и Glop.   -  person Laurent Perron    schedule 18.10.2018
comment
Определенно проблема модели, я запустил GUROBI в коде выше, и он возвращает то же значение, что и Glop.   -  person Laurent Perron    schedule 18.10.2018
comment
Всем спасибо за совет. действительно, в constraint3 была ошибка. исправлено, и результат такой, каким он должен быть   -  person Alexey Parilov    schedule 18.10.2018


Ответы (1)


Кажется, вы обнаружите, что переопределяете constraint7.

Для записи патч самого автора -> https://github.com/APA092/optimum_global/commit/54b15836f5860ab56984ed6d139541e961088159

person Mizux    schedule 19.10.2018