Предварительная фаза AMPL пытается упростить экземпляр проблемы после ее генерации, и до ее отправки решателю. Presolve запускается автоматически, после ввода пользователем команды solve. Любые упрощения, которые выполняет стадия presolve, отменяются после возвращения решения. О результатах работы presolve сообщается только при изменении параметра show_stats со значения 0 (по умолчанию) на значение 1:
model steelT.mod; data steelT.dat; option show_stats 1; solve; Presolve eliminates 2 constraints and 2 variables. Adjusted problem: 24 variables, all linear 12 constraints, all linear; 38 nonzeros 1 linear objective; 24 nonzeros. MINOS 5.5: optimal solution found. 15 iterations, objective 515033
Можно узнать, какие переменные и ограничения исключены на стадии presolve, через отображение переменных и ограничений со статусом pre:
print {j in 1.._nvars: _var[j].status = "pre"}: _varname[j];
Inv[’bands’,0]
Inv[’coils’,0]
print {i in 1.._ncons: _con[i].status = "pre"}: _conname[i];
Init_Inv[’bands’]
Init_Inv[’coils’]
Можно использовать show и display для проверки удаленных компонентов.
В этом разделе мы рассматриваем операции фазы presolve и варианты управления этой фазой из AMPL. Затем мы объясним, что делает presolve, когда обнаруживает "невозможное" решение.
Действия фазы presolve
Чтобы сгенерировать экземпляр проблемы, AMPL сначала назначает каждой переменной те границы, которые указаны в ее объявлении var, или специальные границы -Infinity и Infinity, если не задана нижняя или верхняя граница. Затем presolve пытается использовать эти границы вместе с линейными ограничениями, чтобы вывести более сложные, жесткие границы, которые могут быть выполнены. Одновременно presolve пытается использовать более жесткие границы для определения переменных и ограничений, которые можно исключить.
Изначально presolve ищет ограничения, которые имеют только одну переменную. Равенства фиксируют переменную, которая затем может быть исключена из задачи. Неравенства определяют границы для переменной, которые могут быть помещены в имеющиеся границы. В примере steelT.mod, presolve устраняет два ограничения, сгенерированные из объявления:
subject to Initial {p in PROD}: Inv[p,0] = inv0[p];
наряду с двумя переменными, зафиксированными этими ограничениями, Presolve продолжает поиск ограничений, которые могут оказаться лишними при текущих ограничениях. Ограничения, устраненные из dietu.mod:
set MINREQ; # нутриенты имеющие минимальные ограничения
set MAXREQ; # утриенты имеющие максимальные ограничения
set NUTR = MINREQ union MAXREQ; # все нутриенты
set FOOD; # виды продуктов
param cost {FOOD} > 0;
param f_min {FOOD} >= 0;
param f_max {j in FOOD} >= f_min[j];
param n_min {MINREQ} >= 0;
param n_max {MAXREQ} >= 0;
param amt {NUTR,FOOD} >= 0;
var Buy {j in FOOD} >= f_min[j], <= f_max[j];
minimize Total_Cost: sum {j in FOOD} cost[j] * Buy[j];
subject to Diet_Min {i in MINREQ}:
sum {j in FOOD} amt[i,j] * Buy[j] >= n_min[i];
subject to Diet_Max {i in MAXREQ}:
sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];
дают пример:
model dietu.mod; data dietu.dat;
option show_stats 1;
solve;
Presolve eliminates 3 constraints.
Adjusted problem:
8 variables, all linear
5 constraints, all linear; 39 nonzeros
1 linear objective; 8 nonzeros.
MINOS 5.5: optimal solution found.
5 iterations, objective 74.27382022
print {i in 1.._ncons: _con[i].status = "pre"}: _conname[i];
Diet_Min[’B1’]
Diet_Min[’B2’]
Diet_Max[’A’]
При дальнейшем исследовании ограничение Diet_Min[’B1’] считается избыточным, поскольку оно генерируется из
subject to Diet_Min {i in MINREQ}: sum{j in FOOD} amt[i,j] * Buy[j] >= n_min[i];
с n_min[’B1’] равным нулю в данных. Очевидно, что это ограничение удовлетворяется любой комбинацией переменных, так как все они имеют неотрицательные нижние границы. Более сложный случай дает Diet_Max[’A’], который генерируется из:
subject to Diet_Max {i in MAXREQ}: sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];
Установив каждую переменную в ее верхнюю границу, в левой части этого ограничения мы получаем верхнюю границу общего количества питательного вещества, которое может представлять любой набор.
В частности, для питательного вещества А:
display sum {j in FOOD} amt[’A’,j] * f_max[j];
sum{j in FOOD} amt[’A’,j]*f_max[j] = 2860
Поскольку файл данных определяет n_max [’A’] как 20000, это еще одно ограничение, которое не может быть нарушено.
После окончания описанных тестов первая часть preSolve завершена.
Вторая часть preSolve состоит из серии проходов через задачу, каждый из которых пытается вывести еще более жесткие границы переменных из текущих границ и линейных ограничений. Мы представляем здесь только один пример результата для задачи, сгенерированной из multi.mod, multi.dat:
set ORIG; # origins
set DEST; # destinations
set PROD; # products
param supply {ORIG,PROD} >= 0; # amounts available at origins
param demand {DEST,PROD} >= 0; # amounts required at destinations
check {p in PROD}: sum {i in ORIG} supply[i,p] = sum {j in DEST} demand[j,p];
param limit {ORIG,DEST} >= 0;
param cost {ORIG,DEST,PROD} >= 0; # shipment costs per unit
var Trans {ORIG,DEST,PROD} >= 0; # units to be shipped
minimize Total_Cost: sum {i in ORIG, j in DEST, p in PROD} cost[i,j,p] * Trans[i,j,p];
subject to Supply {i in ORIG, p in PROD}: sum {j in DEST} Trans[i,j,p] = supply[i,p];
subject to Demand {j in DEST, p in PROD}:
sum {i in ORIG} Trans[i,j,p] = demand[j,p];
subject to Multi {i in ORIG, j in DEST}:
sum {p in PROD} Trans[i,j,p] <= limit[i,j];
model multi.mod;
data multi.dat;
option show_stats 1;
solve;
Presolve eliminates 7 constraints and 3 variables.
Adjusted problem:
60 variables, all linear
44 constraints, all linear; 165 nonzeros
1 linear objective; 60 nonzeros.
MINOS 5.5: optimal solution found.
41 iterations, objective 199500
print {j in 1.._nvars: _var.status[j] = "pre"}: _varname[j];
Trans[’GARY’,’LAN’,’plate’]
Trans[’CLEV’,’LAN’,’plate’]
Trans[’PITT’,’LAN’,’plate’]
print {i in 1.._ncons: _con[i].status = "pre"}: _conname[i];
Demand[’LAN’,’plate’]
Multi[’GARY’,’LAN’]
Multi[’GARY’,’WIN’]
Multi[’CLEV’,’LAN’]
Multi[’CLEV’,’WIN’]
Multi[’PITT’,’LAN’]
Multi[’PITT’,’WIN’]
С помощью команды expand, можно отобразить источник появления упрощений. Например:
expand Demand[’LAN’,’plate’]; subject to Demand[’LAN’,’plate’]: Trans[’GARY’,’LAN’,’plate’] + Trans[’CLEV’,’LAN’,’plate’] + Trans[’PITT’,’LAN’,’plate’] = 0;
Поскольку значение demand[’LAN’,’plate’] в данных равно нулю, это ограничение приводит к тому, что сумма трех неотрицательных переменных равна нулю, в результате чего все три переменные должны иметь верхний предел равный 0 в любом решении. Поскольку для них уже указан нижний предел, равный нулю, переменные могут быть зафиксированы, и ограничение может быть исключено. Остальные исключенные ограничения имеют следующий вид:
expand Multi[’GARY’,’LAN’]; subject to Multi[’GARY’,’LAN’]: Trans[’GARY’,’LAN’,’bands’] + Trans[’GARY’,’LAN’,’coils’] + Trans[’GARY’,’LAN’,’plate’] <= 625;
Они могут быть исключены, потому что сумма верхних границ переменных слева меньше 625. Однако этим переменным изначально не были заданы верхние границы. Вместо этого, вторая часть presolve вывела свои границы. Для этой простой проблемы нетрудно увидеть, как возникают вычисленные границы: количество любого товара, отправляемого по какой-либо одной цепочке, не может превышать спрос на этот товар в пункте назначения. В случае мест назначения LAN и WIN, общая потребность в трех продуктах меньше, чем ограничение в 625 для общего объема поставок из любого источника, что делает ограничение на общий объем поставок избыточным.
Управление эффектами presolve
Для более сложных проблем, исключение переменных и ограничений в preSolve может быть не так легко объяснимо, но может составлять существенную часть результатов работы preSolve.
В результате работы preSolve, время и память, необходимые для решения задачи, могут быть значительно уменьшены. В редких случаях preSolve может существенно повлиять на оптимальные значения переменных - когда существует более одного оптимального решения - или помешать другим подпрограммам предварительной обработки, встроенным в программное обеспечение решателя пользователя. Чтобы отключить preSolve полностью, необходимо установить для параметра presolve значение 0. Чтобы отключить только вторую часть, необходимо установить значение preSolve равное 1. Более высокие значения для этой опции указывают максимальное количество проходов, сделанных во второй части предварительной обработки (по умолчанию 10).
После presolve AMPL сохраняет два набора нижних и верхних границ переменных. Это наборы, которые отражают усеченные границы, вытекающие из ограничений, устраняемые при presolve, и наборы, которые не могут быть устранены presolve. Задача имеет одинаковое решение с любым из наборов границ, но общее время решения может быть значительно меньше во втором случае.
var_bounds
Для непрерывных переменных AMPL обычно передает для решения первый набор границ, но можно указать AMPL передать второй набор, изменив опцию var_bounds на 2 со значения по умолчанию, равного 1. Методы активного подбора (например, симплекс-метод) приводят к появлению вырожденных переменных и следовательно, более вырожденных итераций, которые могут препятствовать прогрессу решения. Для целочисленных переменных AMPL округляет любые дробные нижние границы до следующего более высокого целого значения и любые дробные верхние границы до следующего более низкого целого значения. Однако из-за неточностей в вычислениях, граница может быть вычислена со значением отличающимся от целого числа. Например, нижняя граница, которая должна была равняться 7, может быть рассчитана как 7,00000000001.
presolve_inteps, presolve_intepsmax
В этом случае, чтобы граница не была округлена до 8!, AMPL вычитает значение параметра presolve_inteps из каждой нижней границы и добавляет его к каждой верхней границе перед округлением. Если увеличение этого параметра до значения параметра presolve_intepsmax будет иметь значение для округленных границ любой из переменных, AMPL выдаст предупреждение. Значения по умолчанию для presolve_inteps и presolve_intepsmax составляют 1,0e–6 и 1,0e–5 соответственно.
Можно проверить первый набор границ предварительного решения, используя суффиксы .lb1 и .ub1, а второй набор -.lb2 и .ub2. Исходные границы, которые отправляются решающему устройству только при отключенном предварительном разрешении, задаются как .lb0 и .ub0. Суффиксы .lb и .ub задают связанные значения, которые передаются в решатель, на основе текущих значений параметров presolve и var_bounds.
presolve_eps
Здесь CPLEX применил свою собственную процедуру предварительного разрешения и обнаружил ту же самую невозможность, что и AMPL. (Вы можете увидеть несколько дополнительных строк о «суффиксе» с именем dunbdd. Ситуации неограниченности возникают, когда подразумеваемые нижняя и верхняя границы некоторой переменной или body ограничения равны, по крайней мере, для всех практических целей. Из-за неточности в вычислениях нижняя граница может немного превышать верхнюю. В результате чего, решение AMPL сообщит о проблеме неосуществимости. Чтобы преодолеть эту проблему, нужно сбросить параметр presolve_eps со значения по умолчанию 0 до небольшого положительного значения. Различия между нижней и верхней границами игнорируются, когда они меньше этого значения. Если увеличение текущего значения presolve_eps до значения, не превышающего presolve_epsmax, изменит обработку выполняемую presolve, тогда presolve отобразит сообщение об этом:
Setting $presolve_eps >= 6.86e-07 might help.
Значение по умолчанию для опции presolve_eps равно нулю, а presolve_epsmax равно 1,0e–5.
Похожая ситуация возникает, когда неточность в вычислениях приводит к тому, что подразумеваемая нижняя граница для некоторой переменной или body ограничения выходит немного ниже, чем подразумеваемая верхняя граница. В этом случае невозможность не обнаруживается, но наличие почти равных границ может сделать работу решателя намного сложнее и дольше. Таким образом, всякий раз, когда верхняя граница минус нижняя граница переменной или тела ограничения положительна, но меньше значения параметра presolve_fixeps, тело переменной или ограничения фиксируется в среднем по двум границам. Если увеличить значение presolve_fixeps до значения presolve_fixepsmax, это приведет к изменению результатов presolve. Об этом появится сообщение.
presolve_warnings
Количество отдельных сообщений, отображаемых с помощью presolve, ограничено значением presolve_warnings, которое по умолчанию равно 5. Увеличение параметра show_stats до 2 может вызвать некоторую дополнительную информацию о прогоне предварительного разрешения, включая количество проходов, которые имели значение для результатов, и значения, до которых presolve_eps и presolve_inteps должны быть увеличены или уменьшены, чтобы иметь значение.
Обнаружение невозможности решения в presolve
Если presolve определяет, что нижняя граница какой-либо переменной больше значения ее верхней границы, тогда presolve выводит сообщение об ошибке. Например, вот что произойдет, если мы изменим market["band"] на 500, вместо 5000 для значений:
set PROD; # products
param rate {PROD} > 0; # produced tons per hour
param avail >= 0; # hours available in week
param profit {PROD}; # profit per ton
param commit {PROD} >= 0; # lower limit on tons sold in week
param market {PROD} >= 0; # upper limit on tons sold in week
var Make {p in PROD} >= commit[p], <= market[p]; # tons produced
maximize Total_Profit: sum {p in PROD} profit[p] * Make[p];
# Objective: total profits from all products
subject to Time: sum {p in PROD} (1/rate[p]) * Make[p] <= avail;
model steel3.mod;
data steel3.dat;
let market["bands"] := 500;
solve;
inconsistent bounds for var Make[’bands’]:
lower bound = 1000 > upper bound = 500;
difference = 500
Это простой случай, потому что верхняя граница переменной Make["band"] была явно уменьшена ниже, нижней границы. При более сложных тестах Presolve может найти невозможность, которая не связана ни с одной переменной. В качестве примера рассмотрим ограничение:
subject to Time: sum {p in PROD} 1/rate[p]*Make[p] <= avail;
Если снизить значение avail до 13 часов, то presolve сообщит о том, что это ограничение не может быть выполнено:
let market["bands"]:= 5000; let avail:= 13; solve; presolve: constraint Time cannot hold: body <= 13 cannot be >= 13.2589; difference = -0.258929
body ограничения Time - sum {p in PROD} 1/rate[p]*Make[p], является частью, содержащей переменные. Таким образом, с учетом установленного нами значения avail, ограничение накладывает верхнюю границу 13. С другой стороны, если установить каждую переменную равной ее нижней границе, мы получим нижнюю границу значения в любом возможном решении:
display sum {p in PROD} 1/rate[p]*Make[p].lb2;
sum{p in PROD} 1/rate[p]*(Make[p].lb2) = 13.2589
Сообщение от presolve о том, что body <= 13 не может быть >= 13.2589, сообщает, что верхняя граница body находится в конфликте с нижней границей. Подразумевая, что ни одно решение не может удовлетворить все границы и ограничения задачи.
Presolve сообщает о разнице между двумя границами ограничения Time равной –0,258929 (до шести цифр). Таким образом, в этом случае мы можем догадаться, что 13.258929 - это, наименьшее, значение avail, при котором можно найти реальное решение:
let avail := 13.258929; solve; MINOS 5.5: optimal solution found. 0 iterations, objective 61750.00214
Однако, если мы сделаем значение avail немного меньше, мы снова получим сообщение о неосуществимости:
let avail := 13.258928; solve; presolve: constraint Time cannot hold: body <= 13.2589 cannot be >= 13.2589; difference = -5.71429e-07 Setting $presolve_eps >= 6.86e-07 might help.
Несмотря на то, что нижняя граница равна верхней границе для шести цифр, она превышает верхнюю границу с полной точностью (отрицательное значение разницы).
Набор повторного solve в этой ситуации, говорит AMPL отменить Presolve и отправить решателю, казалось бы, противоречивые границы:
solve; MINOS 5.5: optimal solution found. 0 iterations, objective 61749.99714 option display_precision 10; display commit, Make; : commit Make := bands 1000 999.9998857 coils 500 500 plate 750 750 ;
MINOS заявляет, что нашел оптимальное решение, однако Make["band"] немного меньше его нижней границы commit["band"] ! Здесь MINOS применяет внутренний допуск, который позволяет игнорировать небольшие невозможности. Документация AMPL / MINOS объясняет, как работает этот допуск и как его можно изменить. Каждый решатель применяет допуски выполнимости по-своему, поэтому неудивительно, что другой решатель даст другие результаты:
option solver cplex; option send_statuses 0; solve; CPLEX 8.0.0: Bound infeasibility column ’x1’. infeasible problem. 1 dual simplex iterations (0 in phase I)
