Кусочно-линейная формулировка AMPL может определять множество полезных функций. Поскольку кусочно-линейная нотация является общей, ее можно использовать для определения многих функций, которые трудно оптимизировать с помощью каких-либо алгоритмов.
Кусочно-линейный элемент AMPL имеет следующий общий вид:
<<breakpoint-list; slope-list>> pl-argument
где, breakpoint-list и slope-list состоят из списка, разделенного запятыми, из одного или нескольких элементов. Элемент может быть отдельным арифметическим выражением или выражением индексации, за которым следует арифметическое выражение. Для slope-list выражение индексации должно быть упорядоченным набором. Элемент расширяется до списка путем однократной оценки арифметического выражения для каждого элемента набора:
minimize Total_Cost: sum {i in ORIG, j in DEST}
<<{p in 1..npiece[i,j]-1} limit[i,j,p];
{p in 1..npiece[i,j]} rate[i,j,p]>> Trans[i,j];
Количество наклонов должно быть на единицу больше, чем количество точек останова, а значение точек останова не должны уменьшаться. Результирующая кусочно-линейная функция строится путем чередования наклонов и точек останова в указанном порядке. При этом первый наклон слева от первой точки останова, а последний наклон справа от последней точки останова. Путем индексации точек останова по пустому набору можно указать один наклон, и в этом случае функция будет линейной.
pl-argument может иметь одну из следующих форм:
var - ref (arg - expr) (arg - expr, zero - expr)
Var-ref (ссылка на ранее объявленную переменную) или arg-expr (арифметическое выражение) указывает точку, в которой должна быть вычислена кусочно-линейная функция.
zero-expr - это арифметическое выражение, указывающее место, где функция равна нулю. Когда zero-expr опущено, функция считается равной нулю в нуле.
Рекомендации при формулирования кусочно-линейных моделей
Как видно из всех наших примеров, терминология AMPL для кусочно-линейных функций переменных ограничивается описанием функций отдельных переменных. В объявлениях модели никакие переменные не могут появляться в списке точек останова, списке наклона и нулевом выражении (если есть), в то время как arg-expr может быть ссылкой только на отдельную переменную. (Однако, кусочно-линейные выражения в таких командах, как display, могут использовать переменные без ограничений.)
Кусочно-линейная функция отдельной переменной остается такой же функцией при умножении или делении на арифметическое выражение без переменных. AMPL также рассматривает сумму или разность кусочно-линейных и линейных функций одной и той же переменной как представление одной кусочно-линейной функции этой переменной. Разделенная кусочно-линейная функция переменных модели представляет собой сумму или разность (с использованием +, - или sum) кусочно-линейных или линейных функций отдельных переменных. Решатели могут эффективно обрабатывать эти разделенные функции, которые присутствуют в наших примерах.
Кусочно-линейная функция является выпуклой, если последовательные наклоны не убывают (вместе с точками останова), и вогнутой, если наклоны не увеличиваются. Двумя видами кусочно-линейной оптимизации, с которыми легче всего справляются решатели, являются минимизация разделенной выпуклой кусочно-линейной функции и максимизация разделенной вогнутой кусочно-линейной функции с учетом линейных ограничений. Можно легко убедиться, что все примеры в этой главе относятся именно к этим типам. AMPL может получить решения в этих случаях путем преобразования в эквивалентную линейную программу, применения любого решателя LP и последующего перевода решения обратно. Все преобразования производятся автоматически при обработке команды solve.
Вне этих двух случаев оптимизацию разделяемой кусочно-линейной функции следует рассматривать как приложение целочисленного программирования, и AMPL должен переводить кусочно-линейные термины в эквивалентные формы целочисленного программирования. Это тоже делается автоматически, для решения с помощью соответствующего решателя. Поскольку целочисленные программы обычно намного сложнее решать, чем аналогичные линейные программы сопоставимого размера, не нужно предполагать, что любую разделенную кусочно-линейную функцию можно легко оптимизировать. Может потребоваться определенное количество экспериментов, чтобы определить, насколько большой экземпляр может обработать ваш решатель. Наилучшие результаты могут быть получены решателями, которые могут принимать опции «специальные упорядоченные множества типа 2». Подробности использования решателей необходимо читать в технической документации решателя.
Аналогично можно описать ситуацию с ограничениями. Однако разделенная кусочно-линейная функция в ограничении может быть обработана посредством линейного программирования только при ограниченном наборе условий:
- Если она выпуклая и находится в левой части ограничения ≤ (или, что то же самое, в правой части ограничения ≥);
Если она вогнутая и находится в левой части ограничения ≥ (или, что то же самое, в правой части ограничения ≤).
Другие кусочно-линейные ограничения необходимо решать с помощью методов целочисленного программирования, и применять ранее предложенные варианты для каждого отдельного случая.
Если имеется доступ к решателю, который может обрабатывать кусочно-линейные функции напрямую, тогда можно отключить преобразование AMPL в форму линейного или целочисленного программирования, установив параметр pl_linearize в "0".
Случай минимизации выпуклой или максимизации вогнутой разделенной кусочно-линейной функции может, в частности, очень эффективно обрабатываться кусочно-линейными обобщениями методов LP. Решатель, предназначенный для нелинейного программирования, также может принимать кусочно-линейные функции, но вряд ли сможет надежно их обработать, если он не был специально разработан для «не дифференцируемой» оптимизации.
Различия между сложным и простым кусочно-линейным случаями могут быть небольшими. Пример транспортировки в этой главе прост, в частности, потому, что стоимость доставки увеличивается вместе с объемом доставки. Тот же пример был бы трудным, если бы экономия на масштабе привела к уменьшению тарифов на доставку вместе с объемом, поскольку тогда мы минимизировали бы вогнутую, а не выпуклую функцию. Мы не можем однозначно сказать, что стоимость доставки должна быть той или иной. Поведение решателей зависит от специфики моделируемой ситуации.
Во всех случаях сложность кусочно-линейной оптимизации постепенно увеличивается с увеличением общего количества кусочков. Таким образом, кусочно-линейные функции затрат наиболее эффективны, когда затраты могут быть описаны или аппроксимированы относительно небольшим количеством частей. Если для точного описания стоимости необходимо более дюжины элементов, возможно, будет лучше использовать нелинейные функции.
