Линейные выражения

Линейоность арифметических выражений

Арифметическое выражение является линейным для переменной, если значение переменной увеличивается или уменьшается на некоторую фиксированную величину. Выражение, которое является линейным по всем переменным, называется линейным выражением.
Строго говоря, это аффинные выражения, а линейное выражение - это аффинное выражение с постоянным элементом ноль. Для простоты рассуждений мы проигнорируем это различие. AMPL распознает в качестве линейного выражения любую последовательность элементов формы:

  constant-expr

  variable-ref

  (constant-expr) * variable-ref

при условии, что каждый constant-expr является арифметическим выражением, которое не содержит переменных, тогда как var-ref является ссылкой (возможно, подписанной) на переменную. Скобки вокруг constant-expr могут быть опущены, если результат одинаков в соответствии с правилами приоритета операторов. Следующие примеры ограничений из многопериодной производственной модели, представляют собой линейные выражения:

avail[t]
Make[p,t] + Inv[p,t-1]
sum {p in PROD} (1/rate[p]) * Make[p,t]
sum {a in AREA[p]} Sell[p,a,t] + Inv[p,t]

Целевая функция модели,

sum {p in PROD, t in 1..T}(sum {a in AREA[p]} revenue[p,a,t] * Sell[p,a,t] - prodcost[p] * Make[p,t] - invcost[p] * Inv[p,t])

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

(1/rate[p]) * Make[p,t]
может быть записан в линейной программе как
Make[p,t] / rate[p]

Порядок умножения не имеет значения, поэтому variable-ref не обязательно должно находиться в конце объявления. Например,

revenue[p,a,t] * Sell[p,a,t]
эквивалентно
Sell[p,a,t] * revenue[p,a,t]

В качестве примера, объединяющего эти принципы, представьте, что revenue[p,a,t] выражено в долларах за метрическую тонну, а Sell выражено в тоннах. Если мы определим коэффициенты пересчета:

param mt_t = 0.90718474; # metric tons per ton
param t_mt = 1 / mt_t; # tons per metric ton
тогда оба выражения:
sum{a in AREA[p]} mt_t * revenue[p,a,t] * Sell[p,a,t]
и
sum {a in AREA[p]} revenue[p,a,t] * Sell[p,a,t] / t_mt

являются линейными при описании общего дохода.

Для продолжения примера, если затраты также выражены в долларах за метрическую тонну, целевую функцию можно записать в следующем виде:

mt_t * sum {p in PROD, t in 1..T}
(sum {a in AREA[p]} revenue[p,a,t] * Sell[p,a,t] - prodcost[p] * Make[p,t] - invcost[p] * Inv[p,t])
или так:
sum {p in PROD, t in 1..T}
(sum {a in AREA[p]} revenue[p,a,t] * Sell[p,a,t] - prodcost[p] * Make[p,t] - invcost[p] * Inv[p,t]) / t_mt

Умножение и деление могут входить в состав оператора суммирования для получения линейной суммы слагаемых. Обратите внимание, что в первой форме mt_t умножает всю сумму {p в PROD, t в 1..T}, в то время как во второй t_mt делит только слагаемое, следующее за sum{p в PROD, t в 1..T}, потому что оператор «/» имеет более высокий приоритет, чем оператор суммы. Однако для этих примеров результат одинаков.

Условия линейности if-then-else

Оператор if-then-else дает линейный результат, если выражения, следующие после then и else, являются линейными, и в логическом выражении между if и else отсутствуют переменные:

Make[j,t] +(if t = first(WEEKS) then inv0[j] else Inv[j,prev(t)])

Нелинейность функций

Переменные в линейном выражении не могут выступать в качестве операндов для любых других операторов или в аргументах других функций. Это правило применяется к итеративным операторам, таким как max, min, abs, forall, exists, а также к «ˆ» и стандартным числовым функциям, таким как sqrt, log, cos и т.д.

Следующие выражения не являются линейными:

subject to Inv_Limit {p in PROD, t in 1..T}: Inv[p,t] <= min {tt in 1..T} Make[p,tt];
subject to Max_Change {t in 1..T}: abs(sum {p in PROD} Inv[p,t-1] - sum {p in PROD} Inv[p,t]) <= max_change;

Нелинейность mod и div

Операторы mod и div не являются линейными, даже если правый операнд является константой.

Подводя итог, линейное выражение может быть любой суммой терминов в формах:

  constant-expr

  var-ref

  (constant-expr) * (linear-expr)

  (linear-expr) * (constant-expr)

  (linear-expr) / (constant-expr)

  if logical-expr then linear-expr else linear-expr

где, constant-expr - любое арифметическое выражение, которое не содержит ссылок на переменные, а linear-expr - любое другое (более простое) линейное выражение. Скобки могут быть опущены, если результат совпадает с правилами приоритета операторов. AMPL автоматически выполняет преобразования, которые преобразуют выражение в простую сумму линейных элементов.

Линеаризация оператора импликации

Не все решатели поддерживают оператор импликации ==>. Его можно заменить простым неравенством. Например:

  1. Выражение:
offered[j,i] = 1 ==> Zjli[j,l,i] <= Yiu[i]
можно заменить:
Zjli[j,l,i] <= Yiu[i] + U * (1-offered[j,i])

где U - верхняя граница Zjli[j,l,i] - Yiu[i]. Для этого в AMPL необходимо определить param U и установить для U большое значение, которое гарантированно будет больше Zjli[j,l,i] - Yiu[i] для любых j, l и i

  1. X[i] >= 1 ==> Y[i] >= 1,

где, X[i] и Y[i] >= 0, integer

Поскольку переменные принимают целочисленные значения, >0 это эквивалентно неравенству >=1, а условие, которое необходимо линеаризовать эквивалентно:

  X[i] = 0 или Y[i]>= 1

Затем нужно определить новую двоичную (ноль-один) переменную B[i] и записать эквивалентное условие с использованием двух линейных ограничений:

  X[i] <= xu[i] * B[i]

  Y[i]> = B[i]

где xu[i] - это верхний предел значения X[i], который необходимо определить на основе знаний о задаче. Если используется CPLEX, Gurobi или Xpress, вместо линеаризации можно записать это в AMPL как ограничение индикатора:

  B[i] = 0 ==> X[i] = 0 else Y[i] >= 1

Приведенный выше анализ также применим к случаю, когда X[i] - непрерывная переменная. Однако, если Y[i] - непрерывная переменная, тогда можно заменить Y[i]>= B[i] на Y[i] >= epsilon * B[i] или Y[i]>= 1 на Y[i] >= epsilon, где epsilon - некоторое достаточно маленькое значение, например, .00001. (Оно должно быть достаточно маленьким, чтобы, когда Y[i] = epsilon в решении, это не вызывало бы существенного изменения результата. Однако, epsilon не должно быть настолько маленьким, чтобы предел выполнимости решателя рассматривал epsilon так же, как 0.

Импликация вида:

subject to testing_b{i in OB}: oo[i]==1 ==> ooo[i]=1;
subject to testing_c{i in OB}: oo[i]==0 ==> ooo[i]=0;
может быть преобразована в:
subject to testing{i in OB}: ooo[i]==1 ==> oo[i]>=1 else oo[1]=0;

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

s.t. Constraint1 {t in 1..T }: z=1 ==>
  GRID_2_LOAD[t]<=CONTRACTUAL_PEAK;
s.t. Constraint1 {t in 1..T }: z=1==>
  Total_Cost_v[t]=(GRID_2_LOAD[t])*PRICE[t]);
s.t. Constraint1 {t in 1..T }: z=0==>
  GRID_2_LOAD[t]>=CONTRACTUAL_PEAK+ epsilon;
s.t. Constraint1 {t in 1..T }: z=0==>
  Total_Cost_v[t]=(GRID_2_LOAD[t])*PRICE[t]);

Обратите внимание, что во втором условии используется эпсилон. При строгом неравенстве оптимизация в целом не определена четко. Например, могут быть целевые функции, для которых цель становится все ближе и ближе к оптимальной по мере приближения GRID_2_LOAD[t] к CONTRACTUAL_PEAK, но для которых цель не является оптимальной, когда GRID_2_LOAD[t] = CONTRACTUAL_PEAK.

Линеаризация выражений

ABS

В случае, когда необходимо установить ограничения для ABS(X) + ABS(Y) <= 3 (ограничение состоит из выпуклой кусочно-линейной функции слева от ограничения <=), его можно преобразовать в линейную формулировку, используя только непрерывные переменные. Для этого, имеется несколько возможностей:

№1

  1. Использовать кусочно-линейную нотацию AMPL, чтобы явно выразить функцию ABS как кусочно-линейную функцию с крутизной -1 слева от 0 и +1 справа от 0:
var X; var Y;
subj to absConstr: <<0;-1,+1>> X + <<0;-1,+1>> Y <= 3;

AMPL эту запись автоматически преобразует в линейную формулировку перед отправкой задачи решателю.

№2

  1. Представить каждую переменную как разность двух неотрицательных переменных, а абсолютное значение - как сумму этих переменных:
var Xpos >= 0; var Xneg >= 0; var X = Xpos - Xneg;
var Ypos >= 0; var Yneg >= 0; var Y = Ypos - Yneg;
subj to absConstr: (Xpos + Xneg) + (Ypos + Yneg) <= 3;

AMPL использует этот подход при преобразовании в линейную формулировку.

Получить дополнительную информацию по линеаризации можно по следующему адресу: https://www.leandro-coelho.com/how-to-linearize-max-min-and-abs-functions/

А также по адресу: https://groups.google.com/g/ampl/c/r9zZnAHseUQ

№3

  1. Вместо abs(X) подставить новую переменную, которая >= X и >= -X, и аналогично для abs(Y):
var X; var Y;
var Xabs >= 0; var Yabs >= 0;
subj to absConstr: Xabs + Yabs <= 3;
subj to XabsGE: Xabs >= -X;
subj to XabsLE: Xabs >= X;
subj to YabsGE: Yabs >= -Y;
subj to YabsLE: Yabs >= Y;

max

a = max (b, c)

a = max (b, c)

эквивалентно

a >= b
a >= c
а <= b + M * z
a <= c + M * (1-z)

где z - двоичная (ноль-один) переменная, а M - параметр, который больше, чем разница между значениями b и c для любого возможного решения.

a = max (0, pe[j] – C[j])

max(0, pe[j] – C[j]) ->

Чтобы линеаризовать функцию max, необходимо:

  1. Определить новые переменные:
var maxpeCE {T}> = 0;

2. добавить дополнительное ограничение:

subject to maxpeCEdefn{j in T}: maxpeCE[j] >= pe[j] - CE[j];

Поскольку maxpeCE [ j ] имеет значение >= 0, а также >= pe[j] - CE[j], оно должно быть >= max(0, pe[j] - CE[j]). Если цель сводится к минимуму, maxpeCE[j] всегда будет равняться max(0, pe[j] - CE[j]) в оптимальном решении.

Ознакомиться с дополнительной информацией по линеаризации можно по следующему адресу: https://www.leandro-coelho.com/how-to-linearize-max-min-and-abs-functions/

https://groups.google.com/g/ampl/c/r9zZnAHseUQ

Min 

а = min(x,y)

эквивалентно:

z=0==> y>=x;
z=1==> y<=x;
z=0==>a=x;
z=1==>a=y;

Ознакомиться с дополнительной информацией по линеаризации можно по следующему адресу: https://www.leandro-coelho.com/how-to-linearize-max-min-and-abs-functions/

https://groups.google.com/g/ampl/c/r9zZnAHseUQ

X(continuous) * Y(binary)

Вообще говоря, если X и Y являются переменными в модели, и необходимо иметь дело с их произведением Z = X * Y, такое математическое действие приведет к формулировке квадратичной задачи (которая может создать проблемы с выпуклостью, если ее элементы появляются в ограничениях). Однако есть особый случай, когда хотя бы один из X и Y является двоичной переменной, и когда вторая переменная имеет ограничения. Согласно данных условий, их произведение может быть линеаризовано следующим образом:

Пусть X двоичная переменная, а переменная Y имеет следующие границы: L ≤ Y ≤ U, где L и U - заранее известны. Введем новую переменную Z. (Примечание по программированию: независимо от того, является ли Y действительным, целочисленным или двоичным, Z можно рассматривать как вещественное значение.) Добавьте следующие четыре ограничения:

Z ≤ Ux
Z ≥ Lx
Z ≤ Y − L(1−X)
Z ≥ Y−U(1−X);

Рассмотрим сначала случай, когда X = 0, это означает что результат: Z=X*Y равен 0.

Первая пара неравенств говорит: 0 ≤ Z ≤ 0, заставляя Z = 0;

Вторая пара неравенств говорит: Y – U ≤ Z ≤ Y−L; и Z = 0 удовлетворяет этим неравенствам.

Теперь рассмотрим случай, когда: X=1, так что результат получается Z = Y. Первая пара неравенств превращается в L ≤ Z ≤ U, что удовлетворяется если Z = Y. Вторая пара говорит
Y ≤ Z ≤ Y заставляя Z = Y;

Ознакомиться с дополнительной информацией по линеаризации можно по следующему адресу:

  1. https://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html
  2. http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-continuous-and-binary.html
  3. https://or.stackexchange.com/questions/7293/how-to-linearize-the-product-of-two-integer-variables
  4. https://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html
if-then-else, constant-expr, linear-expr, var-ref, param, sum, set X{Y}, div, mod, abs(x), max(x; y; ...), min(x; y; ...), Встроенные функции, Функции пользователя, logical-expr, Линеаризация
Каковы ваши чувства?