Как показал наш пример "резки", ключ к написанию понятного и эффективного сценария для чередования двух (или более) моделей заключается в работе с именованными проблемами, которые представляют различные подмножества компонентов модели. В этом разделе мы более подробно опишем, как формулировка проблемы AMPL используется для определения, использования и отображения именованных проблем. В заключение, мы также представляем аналогичную идею, названную средами, которая облегчает переключение между наборами параметров AMPL.
Иллюстрации в этом разделе взяты из сценария резки и из некоторых других примеров сценариев на веб-сайте AMPL. Объяснение логики этих сценариев выходит за рамки этой справочной документации.
Определение именованных проблем
В любой момент сеанса AMPL существует текущая current проблема, состоящая из списка переменных, целей и ограничений. Текущая проблема по умолчанию называется Initial и включает в себя все переменные, цели и ограничения, определенные до сих пор. Однако пользователь может определить другие «именованные» проблемы, состоящие из подмножеств своих отдельных компонентов, и сделать их актуальными по мере необходимости. Когда проблема становится актуальной, все ее компоненты становятся активными, в то время как все переменные, цели и ограничения другой "неактивной" проблемы становятся неактивными. Можно объявить проблему с помощью специального слова problem, которое определяет имя проблемы и список ее компонентов. Таким образом, записью:
problem Cutting_Opt: Cut, Number, Fill;
определяется новая проблема с именем Cutting_Opt, в которой содержатся все переменные Cut, целевая функция Number и все ограничения Fill из модели:
# модель минимизации количества нарезаемых рулонов
param roll_width > 0; # ширина первоначальных рулонов
set WIDTHS; # набор длинн нарезаемых рулонов
param orders {WIDTHS} > 0; # количество кусочков каждой ширины
param nPAT integer >= 0; # количество шаблонов
set PATTERNS = 1..nPAT; # набор шаблонов
param nbr {WIDTHS,PATTERNS} integer >= 0; # объявление шаблонов
# Проверка: для каждого шаблона ширина его частей не должна превышать ширину рулона нарезки
check {j in PATTERNS}: sum {i in WIDTHS} i * nbr[i,j] <= roll_width;
var Cut {PATTERNS} integer >= 0; # количество рулонов нарезаных по каждому из шаблонов
minimize Number: sum {j in PATTERNS} Cut[j]; # минимизировать количество обрезаемых рулонов
subject to
Fill {i in WIDTHS}: sum {j in PATTERNS} nbr[i,j] * Cut[j] >= orders[i];
# для каждой ширины: количество нарезанных рулонов >= общее количество заказанных рулонов
# Модель генерации шаблона
param price {WIDTHS} default 0.0; # Стоимость резки
var Use {WIDTHS} integer >= 0; # Количество кусков каждой ширины в шаблоне
# Минимизировать стоимость нарезки шаблона
minimize Reduced_Cost: 1 - sum {i in WIDTHS} price[i] * Use[i];
subject to
# Ширина нарезанных из шаблона кусочков <= ширина рулона
Width_Limit: sum {i in WIDTHS} i * Use[i] <= roll_width;
В то же время Cutting_Opt становится текущей проблемой. Любые фиксированные переменные Cut разблокируются, в то время как все остальные объявленные переменные фиксируются в своих текущих значениях. Целевая функция Number восстанавливается, если она была ранее удалена, тогда как все другие объявленные целевой функции удаляются. Аналогичным образом все удаленные ограничения Fill восстанавливаются, тогда как все остальные объявленные ограничения удаляются.
Для более сложных моделей список компонентов проблемы обычно включает несколько наборов переменных и ограничений, как в этом примере из stoch1.run (один из примеров с веб-сайта AMPL):
problem Sub: Make, Inv, Sell, Stage2_Profit, Time, Balance2, Balance;
Указав индексное выражение после имени проблемы, можно определить индексированную коллекцию проблем, например, в multi2.run (другой пример с веб-сайта AMPL):
problem SubII {p in PROD}: Reduced_Cost[p],
{i in ORIG, j in DEST} Trans[i,j,p],
{i in ORIG} Supply[i,p], {j in DEST} Demand[j,p];
Для каждого p в наборе PROD определена задача SubII[p]. Его компоненты включают в себя цель Reduced_Cost[p], переменные Trans[i,j,p] для каждой комбинации i in ORIG и j in DEST, а также ограничения Supply[i,p] и Demand[j,p] для каждого i in ORIG и каждого j в DEST, соответственно.
Форма и интерпретация объявления проблемы, естественно, напоминают формы других операторов AMPL, которые определяют списки компонентов модели. Объявление начинается с ключевого слова problem, имени проблемы, ранее не использовавшегося для какого-либо другого компонента модели, необязательного индексного выражения (для определения индексированной коллекции проблем) и двоеточия. После двоеточия следует список переменных, целей и ограничений, разделенных запятыми, которые необходимо включить в задачу. Этот список может содержать элементы любой из следующих форм, где «компонент» относится к любой переменной, цели или ограничению:
- Имя компонента, например Cut или Fill, которое относится ко всем компонентам с таким именем.
- Подписное имя компонента, например Reduced_Cost [p], которое относится только к этому компоненту.
- Выражение индексации, за которым следует подписанное имя компонента, например {i in ORIG} Supply[i,p], которое ссылается на один компонент для каждого элемента набора индексирования.
Чтобы избежать необходимости повторения выражения индексации, когда несколько компонентов индексируются одинаковым образом, условие проблемы также позволяет использовать выражение индекса, за которым следует список компонентов в скобках:
{i in ORIG} Supply1[i,p], {i in ORIG} Supply2[i,p],
{i in ORIG, j in DEST} Trans[i,j,p],
{i in ORIG, j in DEST} Use[i,j,p]
эквивалентна:
{i in ORIG} (Supply1[i,p], Supply2[i,p]),
{j in DEST} (Trans[i,j,p], Use[i,j,p]))
Как показывают эти примеры, список в скобках может содержать любой элемент, допустимый в списке компонентов, даже индексное выражение, за которым следует другой список в скобках.
Этот тип рекурсии также встречается в команде display AMPL, но он является более общим, чем формат списка, разрешенный для данной команды. Всякий раз, когда переменная, цель или ограничение объявляются, они автоматически добавляются к текущей проблеме (или ко всем текущим проблемам, если в самой проблеме указан индексированный набор проблем). Таким образом, в нашем примере режущего материала все компоненты модели выше, сначала помещаются по умолчанию в задачу Initial. Затем при запуске сценария:
model cut.mod; # загрузка модели
data cut.dat; # загрузка данных
option solver cplex, solution_round 6; # округление решения до 6 значащих цифр
option display_1col 0, display_transpose -10; # скрыть столбцы со всеми 0 значениями
problem Cutting_Opt: Cut, Number, Fill; # Объявление именованной проблемы Cutting_Opt
option relax_integrality 1; # вкдючение режима игнорирования цнлочисленности переменных
problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; # Объявление именованной проблемы Pattern_Gen
option relax_integrality 0; # откдючение режима игнорирования цнлочисленности переменных
let nPAT := 0; # количество шаблонов
for {i in WIDTHS} { # для каждой ширины кусков
let nPAT := nPAT + 1; # количество шаблонов + 1
let nbr[i,nPAT] := floor (roll_width/i); # шаблон = ширина рулона / количество кусков заданной ширины
let {i2 in WIDTHS: i2 <> i} nbr[i2,nPAT] := 0; # значения шаблонов с другой шириной кусков = 0
}
repeat {
solve Cutting_Opt; # Решить проблему Cutting_Opt
let {i in WIDTHS} price[i] := Fill[i].dual; # присвоить price[i] значения двойной цены Fill[i].dual
solve Pattern_Gen; # Решить проблему Pattern_Gen
if Reduced_Cost < -0.00001 then{# если значение Reduced_Cost < 0.00001 тогда
let nPAT := nPAT + 1; # количество шаблонов + 1
let {i in WIDTHS} nbr[i,nPAT] := Use[i]; # значение шаблона nbr[i,nPAT] = Use[i]
}
else break; # в противном случае остановить
}
display nbr, Cut;
option Cutting_Opt.relax_integrality 0;
solve Cutting_Opt;
display Cut;
компоненты делятся на задачи Cutting_Opt и Pattern_Gen. В качестве альтернативы, можно объявить пустые проблемы и затем заполнить их элементы через объявления AMPL. Ниже показано, как это будет сделано для модели выше . Этот подход иногда яснее и проще для более простых приложений.
problem Cutting_Opt;
param nPAT integer >= 0, default 0;
param roll_width;
set PATTERNS = 1..nPAT;
set WIDTHS;
param orders {WIDTHS} > 0;
param nbr {WIDTHS,PATTERNS} integer >= 0;
check {j in PATTERNS}: sum {i in WIDTHS} i * nbr[i,j] <= roll_width;
var Cut {PATTERNS} >= 0;
minimize Number: sum {j in PATTERNS} Cut[j];
subject to Fill {i in WIDTHS}: sum {j in PATTERNS} nbr[i,j] * Cut[j] >= orders[i];
problem Pattern_Gen;
param price {WIDTHS};
var Use {WIDTHS} integer >= 0;
minimize Reduced_Cost: 1 - sum {i in WIDTHS} price[i] * Use[i];
subject to Width_Limit:
sum {i in WIDTHS} i * Use[i] <= roll_width;
Любое использование drop / restore или fix / unfix также изменяет текущую проблему. Команда drop позволяет удалить ограничения или цели из текущей проблемы, а команда restore - добавить ограничения или цели. Аналогично, команда fix удаляет переменные из текущей проблемы, а команда unfix добавляет переменные. Например, multi1.run использует следующие операторы problem:
problem MasterI: Artificial, Weight, Excess, Multi, Convex; problem SubI: Artif_Reduced_Cost, Trans, Supply, Demand; problem MasterII: Total_Cost, Weight, Multi, Convex; problem SubII: Reduced_Cost, Trans, Supply, Demand;
что бы определить именованные задачи для фаз I и II ее процедуры разложения. Напротив, multi1a.run указывает:
problem Master: Artificial, Weight, Excess, Multi, Convex; problem Sub: Artif_Reduced_Cost, Trans, Supply, Demand; что бы сначала определить проблемы, а затем: problem Master; drop Artificial; restore Total_Cost; fix Excess; problem Sub; drop Artif_Reduced_Cost; restore Reduced_Cost;
когда придет время преобразовать проблемы в форму, подходящую для второго этапа. Поскольку имена Master и Sub используются во всей процедуре, одного цикла в скрипте достаточно для выполнения обеих фаз.
В качестве альтернативы, объявление redeclare problem может дать новое определение проблемы. Указанные выше команды drop, restore, и fix можно заменить, например, на:
redeclare problem Master: Total_Cost, Weight, Multi, Convex; redeclare problem Sub: Reduced_Cost, Trans, Supply, Demand;
Однако, как и другие объявления, это нельзя использовать в составном операторе (if, for или repeat) и поэтому не может быть использовано в примере multi1a.run.
Команда reset позволяет отменить любые изменения, внесенные в определение проблемы. Например:
reset problem Cutting_Opt;
сбрасывает определение Cutting_Opt в списке компонентов формулировки problem, которая его недавно определила.
Использование именованных проблем
Далее мы опишем альтернативы для изменения текущей проблемы. Любое изменение, как правило, приводит к тому, что разные цели и ограничения исключаются, а разные переменные фиксируются, в результате чего для решателя возникает другая проблема оптимизации.
Однако, на значения, связанные с компонентами модели, не влияет простое изменение текущей проблемы. Все ранее объявленные компоненты доступны независимо от текущей проблемы, и они сохраняют одинаковые значения, если они не были явно изменены с помощью операторов let или data или решения в случае переменных и значений цели и связанных величин (таких как двойные значения, провисания и снижение затрат). Любая формулировка проблемы, которая относится только к одной проблеме (а не к индексному набору проблем), делает эту проблему актуальной. Например, в начале сценария резки мы хотим, чтобы сначала одна, а затем другая объявленная проблема была текущей, чтобы мы могли настроить определенные параметры в среде проблем.
Постановка задачи в cut1.run:
problem Cutting_Opt: Cut, Number, Fill; option relax_integrality 1; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; option relax_integrality 0;
служит как для определения новых проблем, так и для их актуализации. Аналогичные утверждения в cut2.run проще:
problem Cutting_Opt; option relax_integrality 1; problem Pattern_Gen; option relax_integrality 0;
Эти операторы служат только для актуализации именованных проблем, поскольку проблемы уже были определены в заявках о проблемах в cut2.mod.
Объявление problem может также ссылаться на проиндексированный набор проблем, как в приведенном выше примере multi2.run:
problem SubII {p in PROD}: Reduced_Cost[p], ...
Эта форма определяет потенциально много проблем, по одной для каждого элемента набора PROD. Последующие операторы проблемы могут сделать элементы коллекции текущими по одному, как в следующем цикле:
for {p in PROD} {
problem SubII[p];
...
}
или в утверждении, таком как problem SubII["coils"], которое относится к конкретному элементу. Как видно из предыдущих примеров, решение может также включать имя проблемы, и в этом случае указанная проблема становится текущей, а затем отправляется решателю. Таким образом, эффект оператора solve Pattern_Gen, точно такой же, как и эффект problem Pattern_Gen, который следует за solve.
Отображение именованных проблем
Команда, состоящая из одного слова problem, сообщает, какая проблема является текущей:
model cut.mod; data cut.dat; problem; problem Initial; problem Cutting_Opt: Cut, Number, Fill; problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; problem; problem Pattern_Gen;
Текущая проблема всегда Initialal, пока не были определены другие именованные проблемы.
Команда show может дать список объявленных проблем, которые были определены:
ampl: show problems; problems: Cutting_Opt Pattern_Gen
Можно также использовать show, чтобы увидеть переменные, цели и ограничения, которые составляют конкретную проблему или проиндексированный набор проблем:
ampl: show Cutting_Opt, Pattern_Gen; problem Cutting_Opt: Fill, Number, Cut; problem Pattern_Gen: Width_Limit, Reduced_Cost, Use;
или использовать команду expand, чтобы увидеть явные цели и ограничения текущей проблемы после замены всех значений данных:
ampl: expand Pattern_Gen; minimize Reduced_Cost: -0.166667*Use[20] - 0.416667*Use[45] - 0.5*Use[50] - 0.5*Use[55] - 0.833333*Use[75] + 1; subject to Width_Limit: 20*Use[20] + 45*Use[45] + 50*Use[50] + 55*Use[55] + 75*Use[75] <= 110
Команды show и expand более подробно описаны здесь.
Пример использования именованных проблем
С помощью именованных проблем можно передавать полученные при решении 1 проблемы переменные в параметры 2 проблемы:
s.t. AAC {(i,j) in Links2}:
P1[j, i] = Aa[i,j] * SCA[i]; #model 1 constraint
s.t. CC {(i,j) in Links3}:
sum {k in VNFs} t[i,k] * f <= P1[j,i].val; #model 2 constraint
Выражение «P1[j,i].val» представляет текущее значение переменной P1[i,j]. Таким образом, если P1 появляется только как переменная в модели 1, и если вы сначала решаете модель 1, то P1[j,i].val будет оптимальным значением P1[j,i] из решения модели 1.
В качестве альтернативы можно определить «param p1val {Links3};» и определить ограничение в модели 2 как:
s.t. CC {(i,j) in Links3}:
sum {k in VNFs} t[i,k] * f <= p1val[j,i]; #model 2 constraint
Затем, решив модель 1, нужно использовать оператор присваивания AMPL, чтобы установить значения p1val:
let {(i, j) в Links3} p1val [j, i]: = P1 [j, i];
Это является более общим, потому что вы можете иметь любое выражение после : =, а не только имя переменной.
