Как объединить 2 ограничения для минимизации затрат и увеличения емкости с помощью DOcplex.mp в Python

Question

У меня есть следующие OF, чтобы минимизировать затраты на цепочку поставок:

mdl.minimize(mdl.sum((cs+ch+cf+cv*d[j])*q[j] for j in arcs) + mdl.sum(α*(eh+et*d[j])*q[j] for j in arcs) + mdl.sum(β*(gh+gt*d[j])*q[j] for j in arcs) + mdl.sum(X[f]*cjf for f in comb))

Где cs, ch, cf, cv, eh, et, gh, gt, cjf, α and β - это ряд постоянных параметров.

d[j] - это расстояние между исходной i и конечной j, которые объединены в список arcs или кортежей.

q[j] - это переменная потока между исходной i и конечной j in arcs.

X[f] - это двоичная переменная для открытия объекта в пункте назначения j с емкостью f, возможные комбинации j и f перечислены в comb.

Первый constraint 1 гарантирует, что поток q[i,j] из источника i не превышает его максимальную доступность материала dQ в i. D[(i, j)] - это двоичный параметр, равный 1, если расстояние между исходной i и конечной точкой j меньше или равно пороговому значению, иначе значение D[(i, j)] равно 0. (Этот параметр помогает нам ограничить расстояние транспортировки.)

for i in I: mdl.add_constraint(mdl.sum(q[(i, j)]*D[(i, j)] for j in J) <= Qi[i])

Второй constraint 2 гарантирует, что поток q[i,j] к пункту назначения j равен пропускной способности открытого объект в пункте назначения j с мощностью f.

for j in J: mdl.add_constraint(mdl.sum(q[(i, j)]for i in I) == mdl.sum(X[(j,f)] for f in F))

Но тогда нам нужен другой constraint 3, который обеспечивает сумму мощностей f в объектах, открытых в направления j должны быть как можно ближе к общей потребности в мощностях E. Допустим, есть потребность в энергии в размере 100 МВт E = 100, тогда мы хотим снизить стоимость OF предложения, но также убедиться, что мы достигли спроса E. В противном случае минимизация затрат будет равна 0. Это ограничение можно сформулировать следующим образом:

mdl.add_constraint(mdl.sum(X[j,f]for j in J for f in F) == E)

К сожалению, это решение невозможно. Если мы заменим == на <=, то это выполнимо, но при минимальных затратах, а емкость далеко не максимальная. Нам не нужно, чтобы это было строгим ограничением, но мы хотим максимально приблизиться к E, открыв несколько пунктов назначения в пунктах назначения j с разной емкостью f. (Например, у нас может быть один пункт назначения с 20 МВт, один с 5 МВт, два по 30 МВт и еще один с 15 МВт, чтобы достичь 100 МВт, открыв 5 пунктов назначения)

Один из способов - заставить модель открыться N количество локаций j, однако у нас набор из 128 локаций. Чтобы найти минимальную стоимость и максимальную емкость из диапазонов сценария ios от N=1 до N=128, нам нужно запустить эту модель 128 раз.

Помимо вышеупомянутого ограничения у нас есть 3 дополнительных ограничения:

• Мы можем выбрать только пункт назначения j, чтобы построить объект и открыть его только с одной вместимостью f.
• Сумма пунктов назначения j до open больше 0.
• Нет отрицательного потока q между исходными i и местами назначения j

Есть ли способ:

• Сделать constraint 3 менее привязанным, но все же попытаться достичь E при минимальных затратах?
• Измените форму OF, чтобы объединить минимальную стоимость с максимальной емкостью?

Важно отметить, что мы не хотим запускать модель 128 раз. Мы хотим, чтобы модель выбирала пункты назначения j для открытия объекта и соответственно выбирала мощность f, чтобы минимизировать общую стоимость поставки и максимизировать установленную мощность. В нашем случае e также было бы очень маловероятно открыть только одно направление j, чтобы удовлетворить весь спрос E. Вместо этого у нас было бы несколько j с меньшей f емкостью, которые в сумме приближаются к E.

Answer 1

Вы можете попробовать использовать многоцелевую функцию CPLEX в docplex.

См. Основной пример c в https://www.linkedin.com/pulse/making-optimization-simple-python-alex-fleischer/

from docplex.mp.model import Model

mdl = Model(name='buses')

nbbus50 = mdl.integer_var(name='nbBus50')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')

cost = mdl.continuous_var(name='cost')
co2emission = mdl.continuous_var(name='co2emission')

mdl.add_constraint(nbbus50*50+nbbus40*40 + nbbus30*30 >= 200, 'kids')
mdl.add_constraint(co2emission==nbbus50+nbbus40*1.1+nbbus30*1.2)
mdl.add_constraint(cost==nbbus40*500 + nbbus30*400+nbbus50*625)
                
sense="min"
exprs=[cost,co2emission]
priorities=[1,2]
weights=[1,1]
mdl.set_multi_objective(sense, exprs, priorities, weights, abstols=None, reltols=None, names=None)

mdl.solve(lex_mipgaps = [0.001, 0.05], log_output=True)

for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

print("The minimum cost is ",cost.solution_value);
print("CO2 emission is ",co2emission.solution_value);

'''
which gives

nbBus50  =  4.0
nbBus40  =  0
nbBus30  =  0
The minimum cost is  2500.0
CO2 emission is  4.0

'''

Answer 2

Вы также можете рассмотреть более простой API, а именно Model.minimize_static_lex, которому вы передаете список выражений, которые вы хотите минимизировать в лексикографеi c упорядочивание:

#mdl.set_multi_objective(sense, exprs, priorities, weights, abstols=None, reltols=None, names=None)
mdl.minimize_static_lex(exprs=[cost, co2emission])
mdl.solve(lex_mipgaps=[0.001, 0.05], log_output=True)

Answer 3

Это «многокритериальная оптимизация». Два возможных способа достижения этого описаны ниже.

Первый подход - получить комбинированную единую целевую функцию. Это проще, если оба термина работают в одном направлении, например, оба сводят к минимуму термины. Итак, для вашего «ограничения 3» попробуйте использовать в цели термин для обозначения дефицита относительно спроса, поэтому дефицит будет примерно таким:

Shortfall == E - mdl.sum (X [j, f] для j в J для f в F)

Затем добавьте недостачу в цель и используйте некоторые весовые коэффициенты для двух условий, например:

w * Cost + (1-w) * Дефицит

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

Вариантом этого подхода было бы придание одному термину гораздо большего веса, чем другому, так что этот термин будет доминировать над задача. Затем решатель попытается свести к минимуму этот более важный член (например, дефицит), а другой член поможет выбрать варианты с меньшими затратами для достижения этого. На практике это часто не работает так хорошо, как люди ожидают - добавление очень больших и очень маленьких членов в цель может вызвать числовые проблемы в решателе и часто реальные различия в объективных значениях разных решения в любом случае могут потеряться в допусках решателя. Например, мы видели, как некоторые люди использовали относительные веса 1 миллион к одному, но все еще использовали разрыв оптимальности 1e-6; в этом случае второй член эффективно теряется в шуме, потому что многие (возможно, очень разные) альтернативы выглядят почти одинаково для решателя и попадают в допустимые пределы, и поэтому они эффективно игнорируются.

многоцелевое решение, которое немного сложнее, но не полагается на некоторые неприятные весовые коэффициенты. По сути, вам нужно решить вашу проблему дважды - один раз, чтобы найти максимальную емкость, которую вы можете предоставить, а затем исправить это с помощью ограничения во второй проблеме и минимизировать стоимость предоставления этой емкости.

На практике вы можете скорректируйте этот пуристический подход и примите решения в своей второй модели, достаточно близкие к достижению максимальной производительности. Так, например, вы можете зафиксировать общую емкость вашей второй модели как минимум 99% от расчетной максимальной емкости, достижимой для первой модели. Это отражает случаи, когда, возможно, существует только несколько (дорогих) способов достижения абсолютной максимальной емкости, но можно получить значительную экономию, если мы исследуем решения, близкие к этому максимуму.

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