Мы видели, что для представления значений, связанных с компонентом модели, AMPL использует различные суффиксы, добавляемые к именам компонентов. Суффикс состоит из (.), за которой следует (обычно короткий) идентификатор, так что, например, уменьшенная стоимость, связанная с переменной Buy[j], записывается как Buy[j].rc. Значение уменьшенной стоимости для переменных можно посмотреть с помощью команды display Buy.rc.
Существует множество встроенных суффиксов такого рода, которые приведены ниже:
| .astatus |
AMPL статус |
| .init | текущее начальное предположение |
| .init0 | исходное начальное предположение (set by :=, data, or default) |
| .lb | текущая нижняя граница |
| .lb0 | начальная нижняя граница |
| .lb1 | более слабая нижняя граница от presolve |
| .lb2 | более сильная нижняя граница от presolve |
| .lrc | меньшая теневая стоимость (для var> = lb) |
| .lslack | нижняя слабина (val - lb) |
| .rc | Теневая цена |
| .relax | игнорировать ограничение целостности, если положительное |
| .slack | min(lslack, uslack) |
| .sstatus | solver status |
| .status | status |
| .ub | текущая верхняя граница |
| .ub0 | начальная верхняя граница |
| .ub1 | более слабая верхняя граница от presolve |
| .ub2 | более сильная верхняя граница от presolve |
| .urc | большая теневая стоимость # (для var< = ub) |
| .uslack | верхняя слабина (ub - val) |
| .val | текущее значение переменной |
Однако AMPL не может предвидеть все значения, которые решатель может связать с компонентами модели. Значения, распознаваемые как входные или вычисляемые как выходные, зависят от конструкции каждого решателя и его алгоритмов. Чтобы обеспечить открытое представление таких значений, новые суффиксы могут быть определены на время сеанса AMPL либо пользователем для отправки значений в решатель, либо решателем для возврата значений.
В этом разделе представлены как пользовательские, так и определяемые решателем суффиксы, отображаемые решателем CPLEX. Мы покажем, как пользовательские суффиксы могут передавать предпочтения для выбора переменных и направления ветвления в решатель целочисленного программирования. Анализ чувствительности предоставляет пример определяемых решателем суффиксов, которые имеют числовые значения, а диагностика невозможности показывает, как работает символьный (строковый) суффикс.
Определяемые пользователем суффиксы: целочисленное программирование
Большинство решателей распознают различные алгоритмические варианты и настройки, каждая из которых определяется одним значением, которое применяется ко всей решаемой проблеме. Таким образом, можно изменить выбранные настройки, задав строку объявлений, как в следующем примере. Для решателя CPLEX в целочисленной задаче option cplex_options 'nodesel 3 varsel 1 backtrack 0.1';:
model multmip3.mod; data multmip3.dat; option solver cplex; option cplex_options 'nodesel 3 varsel 1 backtrack 0.1'; solve; CPLEX 8.0.0: nodesel 3 varsel 1 backtrack 0.1 CPLEX 8.0.0: optimal integer solution; objective 235625 1052 MIP simplex iterations 75 branch-and-bound nodes
.priority и .direction
Однако некоторые виды параметров решателя являются более сложными, так как для них требуются отдельные значения для отдельных компонентов модели. Эти настройки слишком многообразны, чтобы вместить их в одну строку. Вместо этого интерфейс решателя может быть настроен на распознавание новых суффиксов, которые пользователь определяет специально для целей решателя. Например, для каждой переменной в целочисленной задаче CPLEX распознает отдельный приоритет ветвления и отдельное предпочтительное направление ветвления, представленное целым числом в диапазоне [0, 9999] и [–1, 1] соответственно. Драйвер AMPL CPLEX распознает суффиксы .priority и .direction как задающие эти параметры. Чтобы использовать эти суффиксы, мы начинаем с определения суффикса для текущего сеанса AMPL:
suffix priority IN, integer, >= 0, <= 9999; suffix direction IN, integer, >= -1, <= 1;
Эффект этих операторов состоит в определении выражений в форме name.priority и name.direction, где name обозначает любую переменную, цель или ограничение текущей модели. Аргумент IN указывает, что значения, соответствующие этим суффиксам, должны быть прочитаны решающим устройством, а последующие фразы накладывают ограничения на значения, которые будут приняты.
Новым суффиксам могут быть присвоены значения с помощью команды let или другими доступными в AMPL способами. В текущем примере мы хотим использовать эти суффиксы для назначения значений приоритета, соответствующих двоичным переменным Use[i,j]. Обычно, эти значения выбираются исходя из знаний о проблеме и имеющегося опыта. Вот один из возможных вариантов:
let {i in ORIG, j in DEST}Use[i,j].priority := sum {p in PROD} demand[j,p];
let Use["GARY","FRE"].direction := -1;
Переменные, которым не присвоено значение .priority или .direction, получают значение по умолчанию, равное нулю (как и все ограничения и цели в этом примере):
display Use.direction; Use.direction [*,*] (tr) : CLEV GARY PITT := DET 0 0 0 FRA 0 0 0 FRE 0 -1 0 LAF 0 0 0 LAN 0 0 0 STL 0 0 0 WIN 0 0 0 ;
Со значениями суффикса, назначенными, как показано выше, для поиска решения в CPLEX требуется меньше симплексных итераций и меньше узлов ветвления и границ:
option reset_initial_guesses 1; solve; CPLEX 8.0.0: nodesel 3 varsel 1 backtrack 0.1 CPLEX 8.0.0: optimal integer solution; objective 235625 799 MIP simplex iterations 69 branch-and-bound nodes
(Мы установили параметр reset_initial_guesses равным 1, чтобы оптимальное решение из первого запуска CPLEX не отправлялось во второй.)
Дополнительную информацию о суффиксах, распознаваемых CPLEX, и о том, как определить соответствующие настройки, можно найти в документации по решателю CPLEX. Интерфейсы решателей могут распознавать разные суффиксы для разных целей.
Суффиксы решателя: анализ чувствительности
Когда ключевое слово sensitivity включено в список указаний CPLEX, классические диапазоны чувствительности вычисляются и возвращаются в трех новых суффиксах: .up, .down и .current:
model steelT.mod; data steelT.dat; option solver cplex; option cplex_options 'sensitivity'; solve; CPLEX 8.0.0: sensitivity CPLEX 8.0.0: optimal solution; objective 515033 16 dual simplex iterations (0 in phase I) suffix up OUT; suffix down OUT; suffix current OUT;
Три строки в конце списка выходных данных команды solve показывают суффиксные команды, которые выполняются AMPL в ответ на результаты решателя. Эти операторы выполняются автоматически. Пользователю не нужно вводить их. Аргумент OUT в каждой команде говорит, что это суффиксы, значения которых будут записаны решающим устройством (в отличие от предыдущего примера, где аргумент IN указал суффиксные значения, которые решатель должен прочитать).
Суффиксы чувствительности интерпретируются следующим образом. Для переменных: суффикс .current указывает коэффициент целевой функции в текущей задаче, в то время как .down и .up дают наименьшее и наибольшее значения целевого коэффициента, для которого текущий базис(решение) LP остается оптимальным:
display Sell.down, Sell.current, Sell.up; : Sell.down Sell.current Sell.up := bands 1 23.3 25 1e+20 bands 2 25.4 26 1e+20 bands 3 24.9 27 27.5 bands 4 10 27 29.1 coils 1 29.2857 30 30.8571 coils 2 33 35 1e+20 coils 3 35.2857 37 1e+20 coils 4 35.2857 39 1e+20 ;
Для ограничений интерпретация аналогична за исключением того, что она применяется к постоянному члену ограничения (так называемое значение правой части):
display Time.down, Time.current, Time.up; : Time.down Time.current Time.up := 1 37.8071 40 66.3786 2 37.8071 40 47.8571 3 25 32 45 4 30 40 62.5 ;
Можно использовать общие синонимы (_var ... и т.д.) для отображения таблицы диапазонов для всех переменных или ограничений, аналогично таблицам, создаваемым в автономной версии CPLEX. (Значения -1e+20 в столбце .down и 1e+20 в столбце .up соответствуют тому, что CPLEX называет -infinity и +infinity в своих данных.)
Определенные решателем суффиксы: диагностика неосуществимости
Для линейной программы, которая не имеет выполнимого решения, можно попросить CPLEX найти неприводимое недопустимое подмножество (или IIS). IIS это набор ограничений и границ переменных, которые недостижимы, но становятся возможными при удалении какого-либо одного ограничения или границы. Если IIS существует и может быть найден, он может дать ценные подсказки относительно источника невозможности. Пользователь включает IIS finder, при изменении параметра iisfind со значения по умолчанию "0" на "1" (для относительно быстрой версии) или 2 (для более медленной версии, которая имеет тенденцию находить IIS меньшего размера).
В следующем примере показано, как обнаружение IIS может быть применено к проблеме неосуществимой диеты. После того, как решение обнаружит, что не существует выполнимого решения, оно повторяется с указанием iisfind 1:
model diet.mod; data diet2.dat; option solver cplex; solve; CPLEX 8.0.0: infeasible problem. 4 dual simplex iterations (0 in phase I) constraint.dunbdd returned suffix dunbdd OUT; option cplex_options ’iisfind 1’; solve; CPLEX 8.0.0: iisfind 1 CPLEX 8.0.0: infeasible problem. 0 simplex iterations (0 in phase I) Returning iis of 7 variables and 2 constraints. constraint.dunbdd returned suffix iis symbolic OUT; option iis_table ’\ 0 non not in the iis\ 1 low at lower bound\ 2 fix fixed\ 3 upp at upper bound\ ’;
И снова AMPL показывает суффиксные операторы, которые были выполнены автоматически. Нас интересует новый суффикс с именем .iis, который является символическим или строковым. Связанная характеристика iis_table, также устанавливаемая драйвером решателя и автоматически отображаемая при решении, отображает строки, которые могут быть связаны с .iis, и дает краткое описание их значения.
Можно использовать display для просмотра возвращенных значений .iis:
display _varname, _var.iis, _conname, _con.iis; : _varname _var.iis _conname _con.iis := 1 "Buy[’BEEF’]" upp "Diet['A']" non 2 "Buy[’CHK’]" low "Diet['B1']" non 3 "Buy[’FISH’]" low "Diet['B2']" low 4 "Buy[’HAM’]" upp "Diet['C']" non 5 "Buy[’MCH’]" non "Diet['NA']" upp 6 "Buy[’MTL’]" upp "Diet['CAL']" non 7 "Buy[’SPG’]" low . . 8 "Buy[’TUR’]" low . . ;
Эта информация указывает на то, что IIS состоит из четырех нижних и трех верхних границ переменных, плюс ограничения, обеспечивающие нижнюю границу для B2 и верхнюю границу для NA в рационе. Вместе эти ограничения не имеют реального решения, но удаление любого из них позволит найти решение остальным.
Если удаление границ не представляет интереса, пользователь может перечислить только ограничения в IIS. print печатает краткий список:
print {i in 1.._ncons: _con[i].iis <> "non"}: _conname[i];
Diet['B2']
Diet['NA']
В этом случае можно сделать вывод, что во избежание нарушения ограничения выделенного бюджета, может потребоваться снизить в рационе содержание витамина В2, либо принять больше натрия, либо и то и другое вместе. Тем не менее, необходимы дальнейшие эксперименты, чтобы определить, насколько меньше или больше, и какие другие изменения, возможно, придется принять, чтобы получить выполнимость.
(Линейная программа может иметь несколько неприводимых невыполнимых подмножеств, но алгоритм поиска IIS CPLEX обнаруживает только один IIS одновременно.)
Определенные решателем суффиксы: направленная неограниченность
Для неограниченной линейной программы, в которой действует минимум -Infinity или максимум +Infinity, решатель может вернуть набор возможных решений вида X + αd, где α ≥ 0. По возвращении из CPLEX выполнимое решение X задается значениями переменных, а направленная неограниченность d задается дополнительным значением, связанным с каждой переменной через определяемый решателем суффикс .unbdd.
Применение направленной неограниченности можно найти в модели trnloc1d.mod и скрипте trnloc1d.run для декомпозиции Benders, примененной к комбинации складского местоположения и транспортной проблеме. Модель, данные и сценарий доступны на веб-сайте AMPL. Мы не будем пытаться описать всю схему декомпозиции здесь, а скорее сконцентрируемся на подзадаче, полученной путем фиксации бинарных переменных Build[i], которые указывают склады, которые должны быть построены, на пробные значения build[i]. В своей двойной форме эта подзадача:
var Supply_Price {ORIG} <= 0;
var Demand_Price {DEST};
maximize Dual_Ship_Cost: sum {i in ORIG} Supply_Price[i] * supply[i] * build[i] + sum {j in DEST} Demand_Price[j] * demand[j];
subject to Dual_Ship {i in ORIG, j in DEST}: Supply_Price[i] + Demand_Price[j] <= var_cost[i,j];
Когда все значения build[i] установлены в ноль, склады не создаются, и основная подзадача невозможна. В результате двойная формулировка подзадачи, которая всегда имеет выполнимое решение, должна быть неограниченной.
Мы решаем подзадачу, собирая ее компоненты в «проблему» AMPL, а затем направляем AMPL для решения только этой проблемы. Когда этот подход применяется к двойной подзадаче из командной строки AMPL, CPLEX возвращает направление неограниченности:
model trnloc1d.mod;
data trnloc1.dat;
problem Sub: Supply_Price, Demand_Price, Dual_Ship_Cost, Dual_Ship;
let {i in ORIG} build[i]:= 0;
option solver cplex, cplex_options ’presolve 0’;
solve;
CPLEX 8.0.0: presolve 0
CPLEX 8.0.0: unbounded problem.
25 dual simplex iterations (25 in phase I)
variable.unbdd returned
6 extra simplex iterations for ray (1 in phase I)
suffix unbdd OUT;
Сообщение суффикса указывает, что .unbdd был создан автоматически. Можно использовать этот суффикс для отображения направления неограниченности, что в данном случае просто:
display Supply_Price.unbdd; Supply_Price.unbdd [*] := 1 -1 4 -1 7 -1 10 -1 13 -1 16 -1 19 -1 22 -1 25 -1 2 -1 5 -1 8 -1 11 -1 14 -1 17 -1 20 -1 23 -1 3 -1 6 -1 9 -1 12 -1 15 -1 18 -1 21 -1 24 -1 ; display Demand_Price.unbdd; Demand_Price.unbdd [*] := A3 1 A6 1 A8 1 A9 1 B2 1 B4 1 ;
Скрипт для декомпозиции Benders trnloc1d.run многократно решает подзадачу с различными значениями build[i], сгенерированными из основной задачи. После каждого решения результат проверяется на неограниченность, и соответственно строится расширение основной задачи.
Ниже представлены основные этапы главного цикла:
repeat {
solve Sub;
if Dual_Ship_Cost <= Max_Ship_Cost + 0.00001 then break;
if Sub.result = "unbounded" then {
let nCUT := nCUT + 1;
let cut_type[nCUT] := "ray";
let {i in ORIG} supply_price[i,nCUT] := Supply_Price[i].unbdd;
let {j in DEST} demand_price[j,nCUT] := Demand_Price[j].unbdd;
} else {
let nCUT := nCUT + 1;
let cut_type[nCUT] := "point";
let {i in ORIG} supply_price[i,nCUT] := Supply_Price[i];
let {j in DEST} demand_price[j,nCUT] := Demand_Price[j]; }
solve Master;
let {i in ORIG} build[i] := Build[i];
}
Попытка использовать .unbdd в этом контексте терпит неудачу, однако:
commands trnloc1d.run;
trnloc1d.run, line 39 (offset 931): Bad suffix .unbdd for Supply_Price
context: let {i in ORIG} supply_price[i,nCUT] := >>> Supply_Price[i].unbdd; <<<
Сложность заключается в том, что AMPL сканирует все команды в цикле повторения, прежде чем начать выполнение любой из них. В результате он сталкивается с использованием .unbdd до того, как любая неосуществимая подзадача сможет определить этот суффикс. Для того, чтобы этот скрипт запускался как задумано, необходимо поместить оператор suffix unbdd OUT; в сценарии перед циклом повторения, так, что бы .unbdd был определен во время сканирования цикла.
Определение и использование суффиксов
Новый суффикс AMPL определяется оператором, состоящим из ключевого слова suffix, за которым следует имя суффикса suffix-name, а затем один или несколько необязательных параметров, которые указывают, какие значения могут быть связаны с суффиксом и как его можно использовать. Например, мы видели определение:
suffix priority IN, integer, >= 0, <= 9999;
для суффикса priority с определителями in-out, type и bound.
Оператор suffix заставляет AMPL распознавать суффиксные выражения вида component-name.suffix-name, где component-name ссылается на любую объявленную в настоящее время переменную, ограничение или цель (или проблему, как определено в следующем разделе). Определение суффикса действует до следующей команды reset или до окончания текущего сеанса AMPL. suffix-name подчиняется тем же правилам, что и другие имена в AMPL. Суффиксы имеют отдельное пространство имен, поэтому суффикс может иметь то же имя, что и параметр, переменная или другой компонент модели. Необязательные параметры оператора suffix могут появляться в любом порядке. Их формы и эффекты описаны ниже.
Необязательный параметр type в суффиксном выражении указывает, какие значения могут быть связаны с суффиксными выражениями, причем все числовые значения являются значениями по умолчанию:
|
Тип суффикса |
Допустимые значения |
| none specified | любые числовые значения |
| integer | целые числовые значения |
| binary | 0 или 1 |
| symbolic | строки символов, перечисленные в suffix-name_table |
Все числовые суффиксные выражения имеют начальное значение "0". Их допустимые значения могут быть дополнительно ограничены одним или двумя связанными параметрами вида:
>= arith-expr <= arith-expr
где arith-expr - любое арифметическое выражение, не включающее переменные.
Для каждого символьного symbolic суффикса AMPL автоматически определяет связанный числовой суффикс suffix-name_num. Затем необходимо создать параметр AMPL suffix-name_table, чтобы определить связь между значениями .suffix-name и .suffix-name_num, как в следующем примере:
suffix iis symbolic OUT; option iis_table '\ 0 non не входит в iis\ 1 low в нижней границе\ 2 fix фиксированный\ 3 upp в верхней границе\ ';
Каждая строка таблицы состоит из целочисленного значения, строкового значения и необязательного комментария. Каждое строковое значение связано со смежным целочисленным значением и любыми более высокими целочисленными значениями, которые меньше целого числа в следующей строке. Присвоение строкового значения выражению. suffix-name эквивалентно присвоению связанного числового значения выражению .suffix-name_num. Последним выражениям изначально присваивается значение "0", и они подчиняются любому типу и привязанным параметрам. (Обычно строковые значения символьных суффиксов используются в командах и сценариях AMPL, а числовые значения используются при взаимодействии с решателями). Необязательный параметр in-out определяет, как значения суффиксов взаимодействуют с решателем:
|
in-out |
обработка значений суффиксов |
| IN | написанный AMPL перед вызовом решателя, а затем прочитанный решателем |
| OUT | записано решателем, затем прочитано AMPL после завершения решателя |
| INOUT | для чтения и записи |
| LOCAL | ни читать, ни записывать |
| INOUT | значение по умолчанию, если ключевое слово in-out не указано |
Ранее мы наблюдали, что суффиксным выражениям можно присваивать или переназначать значения с помощью оператора let:
let Use["GARY","FRE"].direction := -1;
Здесь только одной переменной присваивается суффиксное значение, но часто существуют суффиксные значения для всех переменных в индексированной коллекции:
var Use {ORIG,DEST} binary;
let {i in ORIG, j in DEST}
Use[i,j].priority := sum {p in PROD} demand[j,p];
В этом случае присвоение суффиксных значений может быть объединено с объявлением переменной:
var Use {i in ORIG, j in DEST} binary,
suffix priority sum {p in PROD} demand[j,p];
В общем, одна или несколько фраз в объявлении var могут состоять из ключевого слова suffix, за которым следует предварительно определенное suffix-name и выражение для оценки связанных суффиксных выражений.
