Пытаясь решить задачи оптимизации в программировании, вы должны найти правильный алгоритм для работы, поскольку они часто предназначены для конкретных типов и категорий задач. Одной из таких категорий алгоритмов являются решатели. Это тип математической программы, единственной целью которой является решение или оптимизация задач, представленных серией уравнений.

Давайте посмотрим на один конкретный тип; решатель смешанно-целочисленного линейного программирования (MILP). Эти решатели работают с действительными числами, но уравнения ограничены линейными равенствами и неравенствами, такими как приведенные ниже.

Самое важное уравнение — это ваша целевая функция, которую решатель попытается либо максимизировать, либо минимизировать в зависимости от того, что вы ищете. Например, возьмем функцию оптимизации ниже:

Если мы попытаемся максимизировать эту функцию, соблюдая ограничения, определенные в предыдущих уравнениях, нам придется попробовать различные назначения для x, y и z, пока не будет найдено максимальное целевое значение. Результатом для приведенного выше будет x = 6, y = 1 и z = 1 для максимального выхода 1 из целевой функции.

Это называется линейным программированием (ЛП), но это только половина решателя MILP. Часть со смешанными целыми числами (MI) возникла из-за необходимости ввести в задачу либо двоичные (0 или 1), либо целые (целые числа) переменные. Это может быть общим требованием, особенно когда вам нужно использовать ограничения, такие как ступенчатая функция ниже:

MILP решит этот тип проблемы, сначала решив LP и назначив вещественное число переменной MI. Затем он запустит отдельный алгоритм (например, ветвь и граница), чтобы присвоить новое значение этой переменной и повторно запустить LP-решатель. Этот процесс будет повторяться до тех пор, пока не будут назначены все переменные MI и не будет найден оптимальный ответ (возможно, потребуется попробовать все перестановки). Обратите внимание, что повторный запуск решателя LP не означает, что он начинается с нуля, он просто повторно оценивает уравнения, на которые повлияло назначение конкретной переменной MI.

Введение переменных MI в данную задачу не должно происходить легкомысленно, особенно если вам нужно добавить их много, так как это делает задачу NP-Hard (недетерминированное полиномиальное время). NP-сложно — это классификация сложности, данная задачам программирования, которые не могут быть решены детерминистически за полиномиальное время или, выражаясь простым языком, могут быть неразрешимы за любой разумный промежуток времени.

С базовым пониманием MILP, зачем вам его использовать? Любая проблема, которая может быть смоделирована с помощью линейных неравенств, по большей части, и не настолько проста, чтобы было достаточно более простого алгоритма, выиграет от его использования. Это немного широко, поэтому давайте будем более конкретными. Общие приложения включают оптимизацию распределения ресурсов, например, минимизацию производственных или трудовых затрат, оптимизацию бизнес-операций путем нахождения оптимального количества единиц для продажи, чтобы максимизировать прибыль, или как логистически выполнить работу за минимальное количество времени (источник).

Лично меня особенно интересует финансовое применение решателей MILP. В финансах существует множество математических правил, которые довольно хорошо переводятся в линейные неравенства. Некоторые из них включают максимальное распределение активов и обязательств, минимизацию налогов и оптимизацию государственных пособий и налоговых льгот. Объединение всего этого привело к созданию сложной системы финансового планирования под названием Allswealth. Это огромная система уравнений, построенная на всех канадских финансовых правилах и предназначенная для оптимизации финансов на протяжении всей жизни.

Вот пример для Canada’s Old Age Security (OAS). Его правила заключаются в том, что вы можете получать 626,49 долларов в месяц (не облагается налогом), когда вам исполнилось 65 лет и старше, если ваш налогооблагаемый доход составляет менее 129 581 долларов. Если ваш доход превышает 79 054 доллара США, он будет частично возвращен в размере 15% от каждого доллара сверх этого порога. Существует также правило, в котором говорится, что вы можете отложить начало вашего OAS на срок до 5 лет и получать надбавку в размере 0,6% за каждый просроченный месяц к вашей уплаченной сумме, но это не будет рассматриваться для краткости. Существуют и другие правила, касающиеся приемлемости, но мы не будем заострять на них внимание.

Давайте переведем эти правила в линейные неравенства! Обратите внимание, что предполагается, что налогооблагаемый доход (ti) имеет другие уравнения в системе, которая регулирует его назначение.

  1. Для начала разобьем налогооблагаемый доход (ti) на различные части, на которые влияют пороговые значения.

2. Назначим количество OAS (oas)

3. Введите двоичную переменную (z). Это необходимо, так как алгоритм оптимизации будет «играть» с приведенными выше уравнениями и избегать добавления чего-либо в (b) в уравнении 1, учитывая, что это окажет негативное влияние на уравнение 2. и ничто не мешает (c ) просто включить все значение (ti).

Мы хотим, чтобы (z) действовал как логический оператор, сообщающий нам, используем ли мы (c), и если это так, мы устанавливаем нижний предел (oas) равным 0, поскольку налогооблагаемый доход (ti) будет выше максимальный порог.

Как мы видели ранее, такого рода ступенчатая функция не может быть достигнута с помощью линейных неравенств и должна быть бинарной переменной, которая будет подчиняться следующим ограничениям:

4. Добавьте еще одно уравнение для силы (oas) равной 0, когда (z) равно 1.

5. Добавьте переменную OAS к уже существующим уравнениям дохода (здесь не показаны), чтобы вознаграждение ощущалось.

6. Повторите этот процесс для каждого налогового года, чтобы сумма OAS учитывалась на протяжении всей жизни пользователя.

С помощью этих уравнений мы описали, как добавить поддержку OAS к уже существующей системе уравнений, описывающих будущие финансы. Теперь эта система способна рассмотреть потенциальное снижение чьего-либо налогооблагаемого дохода за любой конкретный год (путем использования необлагаемых налогом источников дохода, таких как TFSA) в обмен на увеличение их пособий OAS. Это сила использования MILP для финансов; использование оптимизации для принятия сложных финансовых решений, которые на первый взгляд могут показаться простыми, но имеют сложные последствия, такие как двухтактные отношения в отношении увеличения налогооблагаемого дохода.

Это был всего лишь пример MILP, но если вы хотите узнать больше, вы можете прочитать эту отличную статью от Brilliant, в которой более подробно рассматривается проблема и даже объясняется, как решатель подходит к поиску решения. Или, если вам нужен еще один пример того, что MILP может сделать в финансах, перейдите к этому сообщению в блоге Allswealth, чтобы прочитать о том, как он оптимизирует RRSP и TFSA, когда вклады не могут быть максимальными ни в том, ни в другом.