PuLP - Как указать точность решателя

Question

Я постараюсь, чтобы мой вопрос был коротким и простым. Если вам нужна дополнительная информация, пожалуйста, дайте мне знать.

У меня есть MIP, реализованный на Python с пакетом PuLP. (Примерно 100 переменных и ограничений). Математическая постановка задачи взята из исследовательской работы. Эта статья также включает в себя численное исследование. Однако мои результаты отличаются от результатов авторов.

Моя проблемная переменная называется prob

prob = LpProblem("Replenishment_Policy", LpMinimize)

Я решаю проблему с prob.solve()LpStatus возвращается Optimal

Когда я добавляю некоторые из оптимальных (бумажных) результатов в качестве ограничений, я получаю немного лучшую объективную оценку. То же самое касается ограничения объективной функции немного более низким значением. LpStatus остается Optimal,

original objective value: total = 1704.20
decision variable: stock[1] = 370

adding constraints: prob += stock[1] == 379
new objective value: 1704.09

adding constraints: prob += prob.objective <= 1704
new objective value: 1702.81

Я предполагаю, что решатель PuLP приближает решение. Расчет очень быстрый, но, видимо, не очень точный. Есть ли способ улучшить точность решателя, который использует PuLP? Я ищу что-то вроде: prob.solve(accuracy=100%). Я посмотрел на документацию, но не мог понять, что делать. Есть какие-нибудь мысли, в чем может быть проблема?

Любая помощь приветствуется. Благодарю.

Answer 1

Ответ на мой вопрос дал айхан: чтобы указать точность решателя, вы можете использовать fracGap аргумент выбранного решателя.

prob.solve(solvers.PULP_CBC_CMD(fracGap=0.01))

Однако вопрос, который я задал, не соответствовал моей проблеме. Отклонение результатов действительно не было вопросом точности решателя (как отметил Саша в комментариях).

Причина моей проблемы: алгоритм, который я реализовал, состоял в оптимизации параметров политики заказа для политики (Rn, Sn) в условиях нестационарного стохастического спроса. Вышеупомянутый документ: Tarim, SA & Kingsman, BG (2006). Политики моделирования и вычисления (R n, S n) для систем инвентаризации с нестационарным стохастическим спросом. Европейский журнал исследований операций, 174(1), 581-599.

Алгоритм имеет две двоичные переменные delta[t] а также P[t][j], Следующие два ограничения допускают только значения 0 и 1 для P[t][j], пока delta[t] определяется как двоичный файл.

for t in range(1, T+1):
    prob += sum([P[t][j] for j in range(1, t+1)]) == 1

    for j in range(1, t+1):
        prob += P[t][j] >= delta[t-j+1] - sum([delta[k] for k in range(t-j+2, t+1)])

поскольку P[t][j] может принимать значения только 0 или 1, следовательно, будучи двоичной переменной, я объявил это следующим образом:

for t in range(1, T+1):
    for j in range(1, T+1):
        P[t][j] = LpVariable(name="P_"+str(t)+"_"+str(j), lowBound=0, upBound=1, cat="Integer")

Целевое значение для минимизации возвращает: 1704.20

После долгих поисков решения я заметил часть статьи, в которой говорится:

... из этого следует, что P_tj должен принимать двоичное значение, даже если оно объявлено как непрерывная переменная. Следовательно, общее количество двоичных переменных уменьшается до общего числа периодов, N.

Поэтому я изменил cat аргумент P[t][j] переменная к cat="Continuous", Не меняя ничего, я получил более низкую объективную ценность 1702.81, Статус результата показывает в обоих случаях: Optimal

Я все еще не уверен, как все эти аспекты взаимосвязаны, но я думаю, для меня этот твик сработал. Для всех остальных, кто направлен на этот вопрос, вероятно, найдут необходимую помощь с ответом, приведенным в верхней части этого поста.