Общие правила объявления ограничений
Общий вид формы объявления ограничения имеет следующий вид:
constraint declaration:
[ subject to ] name aliasopt indexingopt
[ := initial_dual ] [ default initial_dual ]
[ : constraint expression ] [ suffix-initializations ] ;
Ключевое слово subject to в объявлении ограничения может быть опущено, но обычно его лучше оставлять для ясности. Необязательный параметр := initial_dual указывает начальное предположение для двойной переменной (множитель Лагранжа), связанной с ограничением. default и := являются взаимоисключающими, а default используется для определения начальных значений, не указанных в разделе данных.
Формы ограничений
Объявления ограничений должны указывать ограничение в одной из следующих форм:
constraint expression:
expr <=, =, >= expr
cexpr <=, >= expr <=, >= cexpr
Генерация коэффициента по столбцам
Чтобы включить генерацию коэффициента по столбцам для ограничения, одно из выражений может иметь одну из следующих форм:
to_come + expr
expr + to_come
to_come
Условия для этого ограничения, указанные в объявлении var, помещаются в местоположение to_come. Узлы - это особые ограничения, которые могут отправлять или принимать поток из дуг. Их объявления начинаются с ключевого слова node вместо subject. Узлы чистой перевалки не имеют ограничивающего значения. Они должны иметь net_in "приток" равный net_out "оттоку". Другие узлы являются источниками или приемниками. Они указывают ограничения в одной из форм выше, за исключением того, что они могут не упоминать to_come, и ровно одно выражение должно иметь одну из следующих форм:
net_in + expr
net_out + expr
expr + net_in
expr + net_out
net_in
net_out
Ключевое слово net_in заменяется выражением, представляющее суммарный сетевой поток в узле. Поток в узле выражается фразами объявлений arc как to (исходящий поток) за вычетом from (входящий поток). Аналогичная запись производится для net_out минус net_in.
Каждая необязательная фраза инициализации суффикса имеет вид:
suffix-initialization:
suffix-sufname expr
необязательно ставится перед ним запятая, где sufname - ранее объявленный суффикс.
Основные AMPL ограничения состоят из числовых выражений, связанных логическими операторами <=, >= или =. Эти выражения ограничения могут быть связаны с унарными и двоичными логическими операторами AMPL. Общий вид записи ограничения имеет следующий вид:
constraint-expr1 or constraint-expr2
Выполняется, если хотя бы один из операндов удовлетворен.
constraint-expr1 and constraint-expr2
Выполняется, если оба операнда удовлетворены.
not constraint-expr
Выполняется, если операнд не удовлетворен.
Объявление ограничений начинается с ключевых (необязательных) слов subject to, за которыми следует имя ограничения и двоеточие. AMPL предполагает, что любое объявление, не начинающееся с ключевых слов (var, param, minimize, maximize), является ограничением. После двоеточия следует алгебраическое описание ограничения в терминах ранее определенных наборов, параметров и переменных. Например, для производственной модели имеется ограничение доступного времени:
subject to Time:
sum{p in PROD} (1/rate[p]) * Make[p] <= avail;
Имя ограничения, как и имя целевой функции, не используется больше где-либо в алгебраической модели. Однако, оно фигурирует в альтернативных «столбчатых» формулировках и используется в командной среде AMPL для указания значения теневой цены ограничения и других сопутствующих величин. Большинство ограничений в моделях линейного программирования определяются как индексированные коллекции, задавая индексное выражение после имени ограничения. Ограничение Time, например, обобщается чтобы сказать, что время всего производства не может превышать время, доступное на каждой стадии:
subject to Time {s in STAGE}:
sum{p in PROD} (1/rate[p,s]) * Make[p] <= avail[s];
или для каждой недели t:
subject to Time {t in 1..T}: sum{p in PROD} (1/rate[p]) * Make[p,t] <= avail[t];
Другое ограничение говорит о том, что производство, продажи и запасы должны составлять баланс для каждого продукта p в каждую неделю t:
subject to Balance {p in PROD, t in 1..T}: Make[p,t] + Inv[p,t-1] = Sell[p,t] + Inv[p,t];
Объявление ограничения может указывать любое допустимое выражение индексации, которое определяет набор. Eсть одно ограничение для каждого элемента этого набора.
Индексное выражение в объявлении ограничения должно указывать фиктивный индекс (как s, t и p в предыдущих примерах) для каждого измерения индексного набора. Затем, когда AMPL обрабатывает ограничение, соответствующее конкретному элементу набора индексации, фиктивные индексы получают свои значения от этого элемента. Такое использование фиктивных индексов позволяет одному выражению ограничения представлять множество ограничений.
Используя более сложные выражения индексации, можно более точно указать ограничения, которые будут включены в модель. Рассмотрим, например, следующий вариант ограничения времени производства:
subject to Time {t in 1..T: avail[t] > 0}: sum {p in PROD} (1/rate[p]) * Make[p,t] <= avail[t];
Это говорит о том, что если avail[t] имеет в данных значение 0 в одной из недели t, это следует интерпретировать как «отсутствие ограничений по времени, на неделе t, а не как «отсутствие доступного времени на неделе t. В более простом случае, когда существует только одно ограничение по времени, не проиндексированное в течение нескольких недель, можно указать ограничение следующим образом:
subject to Time {if avail > 0}: sum{p in PROD} (1/rate[p]) * Make[p] <= avail;
Выражение псевдо индексации {if avail > 0} приводит к тому, что генерируется одно ограничение с именем Time, если условие avail > 0 истинно, и вообще не генерируется никаких ограничений, если условие ложно. (Те же обозначения могут использоваться для условного определения других компонентов модели). Алгебраическое описание ограничения AMPL может состоять из любых двух линейных выражений, разделенных оператором равенства или неравенства:
linear-expr <= linear-expr
linear-expr = linear-expr
linear-expr >= linear-expr
Несмотря на то, что в математических описаниях линейного программирования принято ставить все термины, содержащие переменные, слева от оператора и все другие термины справа (как в ограничении времени), AMPL не предъявляет таких требований (как видно из ограничения Balance).
Удобство и удобочитаемость должны определять, какие термины размещать на каждой стороне оператора. AMPL заботится о канонизации ограничений, таких как объединение линейных элементов, включающих одну и ту же переменную, и перемещение переменных с одной стороны ограничения на другую.
Например, в multmip3.mod из книги AMPL для каждого источника i пункта назначения j мы хотим, чтобы общее количество отправлений sum{p in PROD}Trans[i,j,p] равнялось либо нулю, либо находилось между minload и limit [i, j]. Это достигается в рамках целочисленного программирования путем введения вспомогательных двоичных переменных Use [i, j]:
var Trans{ORIG,DEST,PROD} >= 0;
var Use{ORIG,DEST} binary;
И добавляя следующие ограничения:
subject to Multi{i in ORIG, j in DEST}: sum{p in PROD} Trans[i,j,p] <= limit[i,j] * Use[i,j];
subject to Min_Ship{i in ORIG, j in DEST}: sum{p in PROD}Trans[i,j,p] >= minload * Use[i,j];
Те же ограничения могут быть установлены с использованием оператора or следующим образом:
subject to Multi_Min_Ship{i in ORIG, j in DEST}: sum{p in PROD}Trans[i,j,p] = 0 or minload <= sum{p in PROD}Trans[i,j,p] <= limit[i,j];
В результате требуется меньше переменных и ограничений, а формулировка ограничения намного ближе к его естественной формулировке.
В другом примере переменные Assign [ i1, i2, j ] определены для представления количества людей типа (i1,i2), назначенных локации j. Следующие объявления определяют дополнительное ограничение для данного примера в терминах целочисленного программирования:
param upperbnd{(i1,i2) in ISO, j in REST}:= min(ceil((number2[i1,i2] / card{PEOPLE}) * hiDine[j]) + give[i1,i2], hiTargetTitle[i1,j] + giveTitle[i1],
hiTargetLoc[i2,j] + giveLoc[i2], number2[i1,i2]);
var Lone{(i1,i2) in ISO, j in REST} binary;
subj to Isolation1{(i1,i2) in ISO, j in REST}: Assign2[i1,i2,j] <=
upperbnd[i1,i2,j] * Lone[i1,i2,j];
subj to Isolation2a {(i1,i2) in ISO, j in REST}: Assign2[i1,i2,j] +
sum{ii1 in ADJACENT[i1]: (ii1,i2) in TYPE2}Assign2[ii1,i2,j] >= 2 * Lone[i1,i2,j];
subj to Isolation2b{(i1,i2) in ISO, j in REST}: Assign2[i1,i2,j] >= Lone[i1,i2,j];
Используя оператор or, то же самое можно сказать более ясно и кратко:
subj to Isolation {(i1,i2) in ISO, j in REST}: Assign2[i1,i2,j] = 0
or Assign2[i1,i2,j] + sum {ii1 in ADJACENT[i1]: (ii1,i2) in TYPE2} Assign2[ii1,i2,j] >= 2;
Используя оператор not, можно указать допустимую область значений переменных решения, которая не может являться допустимой:
var x; minimize Obj: x; subject to OpenCons: not (x <= 2);
У цели есть инфимум 2, но нет минимума, который удовлетворяет ограничению. Та же задача возникает, если использовать строгое неравенство < или >, в частности, выражение x>2 в этом случае. Поскольку решатели CP работают только с дискретными переменными, они свободно допускают выражения, имеющие такие формы.
Следующая запись индексного выражения удаляет элемент NB_20R из ограничения:
subject to MBbound {i in NB, j in PD:i!='NB_20R'}: MG[i,pd] >= some parameter;
exists & forall
Операторы or и and имеют итеративные версии exists и forall соответственно.
exists {indexing} constraint-expr
Итеративная форма or, выполняется, если операнд удовлетворен хотя бы для одного элемента набора индексации.
exists{i in ORIG} demand[i] > 10
истинно, если спрос хотя бы в одном пункте превышает 10.
Следующая запись говорит о том, что AC[j,i] должно быть > 0 по крайней мере для одного j в X:
subject to Constraint2{j in X: ord(j) mod 2 = 1 and forall {i in Y} AC[j,i] > 0}: sum{i in Y}y[i,j] = x[j];
forall {indexing} constraint-expr
Итеративная форма and, выполняется, если операнд удовлетворяется для всех элементов набора индексации.
forall{i in ORIG}demand[i] > 10
Верно, если спрос в каждом пункте превышает 10.
Следующая запись говорит о том, что AC [ j, i ] должно быть > 0 для всех j в X:
subject to Constraint1 {i in Y: forall {j in X} AC[j,i] > 0}: sum{j in X}y[i,j] = 2;
Таким образом, ограничение AMPL может быть любой логической комбинацией равенств и неравенств.
subject to C_V: Vmin <= V <= Vmax;
Ограничения в виде двойных неравенств
AMPL также допускает ограничения двойного неравенства. Допустимые формы для такого ограничения:
const-expr <= linear-expr <= const-expr
const-expr >= linear-expr >= const-expr
Где, const-expr не должно содержать переменных. Эффект заключается в определении верхней и нижней границ значения линейного выражения.
subject to Diet {i in NUTR}: n_min[i] <= sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];
Эта запись говорит о том, что среднее количество питательного вещества i, поставляемого всеми продуктами, должно быть больше или равно n_min[i], а также меньше или равно n_max[i].
Если модели требуются переменные с лева или c права const-expr, необходимо определить два разных ограничения в отдельных объявлениях. AMPL не поддерживает объединение этих двух ограничений в одно двойное неравенство (поскольку это приводит к различным нежелательным осложнениям).
Для большинства приложений линейного программирования не нужно беспокоиться о форме ограничений. Ограничения можно писать наиболее удобным способом, они будут распознаваться как правильные линейные ограничения в соответствии с правилами изложенными в «Линейность выражений». Однако существуют ситуации, в которых выбор формулировки будет определять, распознает ли AMPL модель как линейную. Например: нам необходимо ограничить модель производства таким образом, чтобы ни один продукт p не мог занимать в общем объеме производства долю более определенной пользователем. Для этого, нужно определить параметр max_frac для представления доли в виде дроби и записать следующее ограничение:
subject to Limit {p in PROD}: Make[p] / sum {q in PROD} Make[q] <= max_frac;
Однако, данное ограничение является не линейным для AMPL, потому что его левое выражение содержит деление на сумму переменных. Для линеаризации данного ограничения необходимо записать так:
subject to Limit{p in PROD}: Make[p] <= max_frac * sum{q in PROD} Make[q];
тогда AMPL распознает его как линейное. AMPL на стадии presolve упрощает ограничения. Он подготавливает модель и данные для передачи решателю. Например, AMPL может исключить переменные, зафиксированные в значении, объединить ограничения для одной переменной с простыми границами для других переменных. Или удалить ограничения, которые подразумеваются другими ограничениями. В случае необходимости можно игнорировать эту предварительную фазу presolve.
Условные операторы if-then–else в ограничениях
Другой тип логического выражения, - условное выражение if-then-else. Которое возвращает одно из двух различных арифметических значений в зависимости от того, является ли логическое выражение истинным или ложным.
Общая форма условного выражения if-then-else:
if a then b else c
где а является логическим выражением. Если значение а равно true, условное выражение принимает значение b. Если а ложно, выражение принимает значение c. Если c равно нулю, часть else c может быть отброшена. Чаще всего b и c являются арифметическими выражениями, но они также могут быть строковыми или множественными выражениями, если оба они являются выражениями одного вида. Поскольку then и else имеют меньший приоритет, чем любые другие операторы, условное выражение необходимо заключить в скобки (как в примере выше), если только оно не встречается в конце оператора.
Рассмотрим два вида ограничения баланса в многопериодной модели производства:
subject to Balance0{p in PROD}: Make[p,first(WEEKS)] + inv0[p] = Sell[p,first(WEEKS)] + Inv[p,first(WEEKS)];
subject to Balance {p in PROD, t in WEEKS: ord(t) > 1}: Make[p,t] + Inv[p,prev(t)] = Sell[p,t] + Inv[p,t];
Ограничение Balance0 задано для первой недели. inv0[p] используется когда t является первой неделей, а Inv[p, prev(t)] используется в остальных периодах. Мы хотели бы объединить эти ограничения в одной декларации. Это можно сделать так:
if t = first(WEEKS) then inv0[p] else Inv[p,prev(t)]
Поместив это выражение в объявление ограничения, мы можем записать:
subject to Balance{p in PROD, t in WEEKS}: Make[p,t] + (if t = first(WEEKS) then inv0[p] else Inv[p,prev(t)]) = Sell[p,t] + Inv[p,t];
Эта совмещенная форма описания условия сообщает об ограничениях баланса запасов более кратко и непосредственно, чем две отдельные декларации.
AMPL также использует конструкцию if-then-else для программирования, подобно условным операторам во многих языках программирования. Конструкция выполняет тот или иной блок операторов в зависимости от истинности некоторого логического выражения.
Описанное в этом разделе if-then-else является не утверждением, а выражением, значение которого определяется условно. Поэтому оно принадлежит внутренней части объявления, и располагается в месте, где выражение необходимо оценить.
Еще один из примеров использования if-then-else в ограничениях:
s.t. Constraint1 {t in 1..T }: if (GRID_2_LOAD[t]<=CONTRACTUAL_PEAK) then Total_Cost_v[t]=(GRID_2_LOAD[t])*PRICE[t]);
s.t. Constraint2 {t in 1..T}: if( GRID_2_LOAD[t]>CONTRACTUAL_PEAK) then (Total_Cost_v[t]=(GRID_2_LOAD[t])*my_alpha*PRICE[t]);
Если для модели необходимо написать ограничение вида:
s.t. Trial{k in V, i in PD}: x[0,2*n+1,k] = if 1 then y[i,k] = 0;
такая запись вызовет ошибку. Эту запись можно преобразовать в:
s.t. Trial{k in V, i in PD}: x[0,2*n+1,k] = 1 ==> y[i,k] = 0;
линеаризовав которое, мы получим:
s.t. Trial{k in V, i in PD}: y[i,k] <= M * (1-x[0,2*n+1,k]);
где param M - некоторый верхний предел значения y[i,k] для любых i и k.
Логические ограничения
Ограничение вида:
subject to PRO['o1','G1','p1','CINTAS',1,1]: PRASS1['o1','G1', 'p1', 'CINTAS',1,1] != 1 || PROD['o1','G1','p1','CINTAS',1,1] > 0;
Где PRASS1 - binary, PROD - real, PRO является логическим ограничением, потому что в нем используется || ("or") оператор для объединение 2-х ограничений в одно общее.
Большинство решателей отклоняют все логические ограничения, однако принимают вместо них «Индикаторные ограничения».
Индикаторные ограничения. Оператор импликации.
AMPL имеет еще один тип условного оператора - оператор импликации ==>. Варианты его применения изложены ниже:
logical-expr ==> constraint-expr1
Оператор выполняется, если результат logical-expr равен true, а constraint-expr1 выполнено, или если logical-expr равен false. logical-expr может быть любым constraint-expr.
logical-expr ==> constraint-expr1 else constraint-expr2
Выполняется, если logical-expr равен true, constraint-expr1 выполнено, или если logical-expr равен false, а constraint-expr2 выполнено.
logical-expr <==> constraint-expr
Выполняется, если logical-expr равен true, а constraint-expr выполнено, или если logical-expr равен false, а constraint-expr не выполнено.
Кроме того, <== имеет то же значение, что и ==>, за исключением случаев, когда переставлены роли constraint-expr1 и constraint-expr2.
Допуская использование переменных по обе стороны от операторов импликации, эти формы значительно расширяют разнообразие условных ограничений, которые AMPL может удобно выразить. Например, ограничение Multi_Min_Ship может быть записано:
subject to Multi_Min_Ship{i in ORIG, j in DEST}: sum{p in PROD}Trans[i,j,p] > 0 ==> minload <= sum {p in PROD} Trans[i,j,p] <= limit[i,j];
При использовании оператора импликации с двоичными переменными, возможны следующие типы выражений:
binary - variable = 0 ==> constraint binary-variable = 0 ==> constraint1 else constraint2 binary-variable = 1 ==> constraint binary-variable = 1 ==> constraint1 else constraint2
Индикаторные ограничения для нескольких переменных
В случае, когда необходимо ограничить значения выборочных переменных, например мы имеем комплексное условие: X[1] = 0, либо X[3] = 0, либо X[1], X[3] = 0.
В этом случае необходимо определить параметр U, значение которого > любого значения, которое X[1] или X[3] могут принят в решении, а также объявить двоичные (ноль-единица) переменные Z[1] и Z[3], которые будут обладать тем свойством, что Z[1] = 0 вынуждает X[1] = 0, а Z[3] = 0 вынуждает X[3] = 0.
Затем потребуются следующие ограничения, чтобы заставить хотя бы одно из X[1] и X[3] быть равным нулю:
X[1] <= U * Z[1]
X[3] <= U * Z[3]
Z[1] + Z[3] <= 1
Если используются решатели CPLEX, Gurobi или Xpress, тогда можно вместо этих неравенств использовать ограничения с использованием оператора импликации ==>.
Z[1] = 0 ==> X[1] = 0
Z[3] = 0 ==> X[3] = 0
Список решателей, которые поддерживают оператор импликации
Однако нужно помнить, что оператор импликации поддерживается не всеми решателями. Список решателей, которые поддерживают оператор импликации:
Действия с ограничениями
Отображение выполняющихся ограничений
В случае, когда необходимо отобразить все ограничения неравенства, которые выполняются, нужно просто отобразить все ограничения с нулевым резервом. Например,
display {i in 1.._ncons: _con[i].lb < _con[i].ub and abs(_con[i].slack) < 0.000001} _conname[i];
Условие _con[i].lb <_con[i].ub удаляет ограничения на равенство, а условие abs (_con[i].slack) < 0,000001 выбирает только те ограничения, для которых величина резерва меньше чувствительности точности решения. Можно заменить последнее условие на _con[i].slack = 0, но поскольку решатели используют небольшой допуск при проверке выполнимости, это может привести к тому, что будут пропущены некоторые ограничения, которые на самом деле должны учитываться.
Отображение не выполняющихся ограничений
Другое дело - нарушенные ограничения. Когда решающая программа сообщает «об отсутствии допустимого решения», она может вернуть последнее найденное недопустимое решение. Или решающая программа может не вернуть никакого решения, и в этом случае все переменные останутся в своих начальных значениях. Если начальные значения не были установлены, все переменные останутся со своими значениями по умолчанию, равными 0.
В AMPL ограничение нарушается текущими значениями переменных, если у него отрицательный резерв. Итак, можно перечислить все нарушенные ограничения следующим образом:
display {i in 1.._ncons: _con[i].slack<-0.000001} _conname[i]
или
display {i in 1.._ncons: _con[i].slack<-1e-5} (_conname[i], _con[i].lb, _con[i].body, _con[i].ub);
Аналогичным образом можно отобразить все переменные, текущие значения которых выходят за их границы:
display {j in 1.._nvars: _var[j].slack < -0.000001} _varname[j];
или
display {j in 1.._nvars:_var[j].slack < -1e-5} (_varname[j], _var[j].lb, _var[j], _var[j].ub);
Если эти команды выполняются после запуска решателя, то текущие значения задаются недопустимым решением, возвращенным решателем, или начальными значениями, если решающая программа не вернула решение.
Запись ограничений, которые имеют не 0 двойные значения
В том случае, когда необходимо записать(запомнить) ограничения, которые имеют не 0 двойные значения после получения решения можно использовать следующую запись:
set alpha {S1, {-1, 1}};
set beta {S1, {-1, 1}};
for {s in S1} {
let selectedCell := s;
for {d in {-1, 1}} {
let direction := d;
solve;
let alpha[s, d] := {cell in CELL_IDS : SUpperBound[cell] != 0};
let beta[s, d] := {cell in CELL_IDS : SLowerBound[cell] != 0};
}
}
Использование атрибута очередь/приоритет упорядоченных наборов для упорядочения расчета ограничений
Следующий пример показывает, как можно использовать атрибут очередь/приоритет упорядоченных наборов для упорядочения расчета ограничений:
set Groups ordered = {"A","B","C"};
set Stacks = {"X","Y"};
param H = 3;
param T = 5;
var X{1..T, 1..card(Groups), Stacks, 1..H};
subject to Orden{g in Groups, s in Stacks, h in 2..H}: sum{q in ord(g)..card(Groups)} X[T,q,s,h-1] >= X[T,ord(g),s,h];
expand Orden;
или:
var X{1..T, Groups, Stacks, 1..H};
subject to Orden{g in Groups, s in Stacks, h in 2..H}: sum{q in ord(g)..card(Groups)} x[T,member(q,Groups),s,h-1] >= x[T,g,s,h];
для случая, когда необходимо, чтобы вторым индексом X было имя группы, а не число.
Плавающее ограничение для значения 1 из 3-х переменных
Следующая запись позволяет описать ограничение, которое запрещает назначать 1 для 3-х последовательных по t значений x{I,J}. Для случая, когда смены заданы в виде строки, а не в виде числа:
set I;
set J ordered;
var x {I, J};
s.t. ConsecShifts {i in I, j in J:j! = last(J) and j!=prev (last(J),J)} : x[i, j] + x[i, next(j)] + x[i, next(j, 2)] <= 1;
X != Y
Если по условиям задачи наложено ограничение, что бы значения 2-х переменных не равнялись друг другу, тогда можно записать ограничение следующего вида:
X <= Y - 1; X >= Y – 1;
