Облачные инструменты оптимизации

На этой странице вы познакомитесь с другими инструментами оптимизации, способными производить расчет с десятками тысяч переменных. Познакомитесь с бесплатными облачные сервисами. Узнаете, как составить файл с заданием для расчета в облачном сервисе Neos.
Возможность облачных вычислений на удаленных серверах предоставляют многие порталы: как широко известные Microsoft Azure, Google, Amazon, IBM, Яндекс, … так и существенно менее известные ( Neos, GAMS, AMPL, Gurobi, …). Ресурсы предоставляются не только на коммерческой основе, но и бесплатно (для решения относительно небольших задач и обучения).
  Привлекательность облачных сервисов обусловлена как возможностью использовать для решения своих задач удаленные (облачные) вычислительные мощности, что позволяет радикально снизить требования к техническим характеристикам собственного компьютера, так и возможностью отказаться от развертывания и поддержки на своем компьютере различного специализированного ПО.

Рассмотрим подробнее вопросы облачной оптимизации.

   Штатный инструмент MS Excel «Поиск решения (Solver) - всего лишь один из множества инструментов оптимизации.
   Инструменты оптимизации (солверы) разрабатываются многими компаниями и научными коллективами. Зачастую эти инструменты сугубо коммерческие, но все же чаще имеется возможность бесплатного использования таких инструментов.
   На сегодняшний день общее количество даже наиболее известных инструментов оптимизации превышает полусотню. Большая их часть ориентирована не на задачи линейной оптимизации, а на разного рода сложные научные задачи общей (нелинейной) оптимизации. Ведь постоянно возникают специфические проблемы науки или управления, которые очень плохо решаются стандартными солверами, поэтому требуют разработки новых инструментов.
Однако большинство бизнес-задач могут быть решены с помощью одного-двух подходящих солверов.


Как правило, различные виды оптимизаторов - это универсальные инструменты, не требующие какого-то специфического программного обеспечения. Большинство из них слабо ориентированы на Excel, поэтому исходные данные и формулы для оптимизации должны быть представлены в текстовом формате.
Составить задание можно в любом текстовом редакторе любой операционной системы и в нем же (или прямо в браузере) просмотреть результаты. И это - огромная ценность.
Однако человеку, привыкшему к удобству представления данных в Excel, бывает сложно использовать эти инструменты.
  Зато с помощью таких инструментов можно решать бесплатно и в любой момент гораздо более объемные задачи, чем с помощью интегрированного в MS Office «Поиска решения». ("Поиск решения" решает задачи до 200 переменных и до 100 ограничений.)
  Конечно, ограничения (разные) есть и в других солверах. Но вы не всегда сможете даже заметить эти ограничения. Так свободно распространяемый солвер COIN-OR CBC позволяет решать задачи с 100 тысями целочисленных переменных. И этого достаточно для очнь многих бизнес-задач.

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

Наиболее известен сегодня бесплатный облачный сервис-агрегатор NEOS (neos-server.org), который дает возможность обратиться к множеству различных оптимизаторов.

NEOS

Сайт https://neos-server.org представляет собой бесплатный интернет-сервис для решения численных задач оптимизации.
Сервер NEOS Висконсинского университета (University of Wisconsin) обеспечивает доступ к более 60 внедренным solver’ам, каждый из которых имеет больше десятка категорий оптимизации. Серверы, производящие вычисления, располагаются в США, в Австрии и Португалии. Однако, у этого бесплатного сервиса вычислительные мощности не слишком велики. Сложность задач ограничена, чтобы пользователи не мешали друг другу. Но фактически задачи оптимизации могут быть довольно большими, так как разрешенная длительность поиска оптимума - 8 часов.

Для работы с сервисом нужно (желательно) зарегистрироваться. Регистрационные данные затем указываются везде, включая инструменты установленные локально.
Задание оформляется в виде текстового файла и отправляется через веб на сервер. В браузере можно посмотреть и результаты расчетов. Отчеты о решенных задачах оттправляются на указанную при регистрации электронную почту. Так что решения всех задач всегда сохраняются.
В журнале отчета могут быть приведены только данные о значении целевой функции, а полные результаты приводятся в конце отчета в виде ссылки.

Ниже приведен пример составления задания в формате GAMS для решения кейса Кондитерская фабрика Алиса.

Как составить текстовый файл задания в формате GAMS

Сначала необходимо дать название зданию. Назовем задание Confectionery Model (Кондитерская модель). С помощью команды $title запишем:
$title Confectionery factory model (CF)
Затем нужно описать, что вычисляется в задаче и записать ключевые слова. Блок начинается с команды $onText и заканчивается командой $offText Мы хотим вычислить максимальную прибыль, составив оптимальный план производства. Ключевыми словами будут линейное программирование и название целевой функции (maximum revenue\profit plan)
$onText
Maximum revenue\profit plan for confectionery factory.
Keywords: linear programming, maximum revenue\profit plan
$offText
Теперь необходимо перечислить все переменные и параметры, которые есть в нашем кейсе. Описание начинаем со служебного слова Set и перечисляем все данные, вводя обозначения.
Пусть n — продукты, которые выпускает фабрика (перечислим названия продуктов через запятую), а f — сырье, из которого продукты изготовлены (перечисляем название всех видов сырья через запятую). Обратите внимание на синтаксис: расшифровка имени переменоой пишется в одинарных кавычках 'products' переперечисленные продукты и сырьё ограничены скобками / ... / и в самом конце ставится точка с запятой ";"
Set
  n 'products' / NutRinging, ParadiseTaste, GoldenBar, SiberianSquirrel, LateEvening, FirstForfeit /
  f 'raw material' / DarkChocolate, LightChocolate, Sugar, Caramel, Nuts /;
Далее начинаем вводить числовые данные. Первый параметр — удельная прибыль ( profit ). Обозначим b(n), запишем единицу измерения (руб/кг), и перечислим значения удельной прибыли для каждого продукта:
Parameter b(n) 'profit (rur\kg)'
   / NutRinging 257.5, ParadiseTaste 214.0, GoldenBar 191.5,
   SiberianSquirrel 214.5, LateEvening 199.5, FirstForfeit 262.0 /;
Второй параметр — отпускная цена ( revenue ). Обозначим d(n), запишем единицу измерения (руб/кг), и перечислим значения отпускной цены для каждого продукта:
Parameter d(n) 'revenue (rur\kg)'
   / NutRinging 1020, ParadiseTaste 765, GoldenBar 900,
   SiberianSquirrel 895, LateEvening 945, FirstForfeit 1000 /;
Третий параметр — остатки склада сырья ( stock ). Обозначим s(f), запишем единицу измерения (кг), и перечислим значения остатков склада для каждого вида сырья:
Parameter s(f) 'stock (kg)'
   / DarkChocolate 58200, LightChocolate 7450, Sugar 19000, Caramel 22800, Nuts 39000 /;
Теперь необходимо ввести данные о составе сырья в каждом виде продукта. Ввести эти данные нужно в табличном виде.
Обозначим a(f,n) зависимость между продуктом и соответствующим сырьем. Нужно явно указать, что это таблица и дать название этой таблице.
Table a(f,n) 'the composition of the product' Таблица данных кейса Кондитерская фабрика
Определим переменные. Это будет план производства - количество продуктов, которые нужно произвести. Обозначим план выпуска x(n), наименование кг.
Positive Variable x(n) 'quantity of products produced (kg)';
Определим целевую функцию. Это Прибыль (Free Variable profit)
Free Variable profit, revenue;
Запишем уравнения связывающие переменные. Сначала укажем, что это блок уравнение Equation. Затем введем обозначия: nb(f) — сколько сырья будет израсходовано для производства продуктов (спрос на сырьё), выручки (переменная ocr), которую фабрика получит после продажи произведенных продуктов и прибыли ocp. Мы можем в одинарных ковычках записать название величины для своего удобства или формулу расчета, чтобы помнить, что вычислялось в задаче. Напишем формулы расчета, чтобы затем скопировать из, и записать ниже без ковычек. При определении выручки в одинарных ковычках запишем наименование и уравнение для её вычисления. Чтобы рассчитать выручку, нужно вес произведенного продукта умножить на его отпускную цену и сложить эти произведения (складываем n раз - столько, сколько продуктов производим). Расчет прибыли аналогичен расчету выручки. Поэтому в выражении для расчета выручки заменим отпускную цену d(n) на удельную прибыль b(n). В коде это выглядит так:
Equation
nb(f) 'demand of raw material' ocr 'revenue =e= sum(n, d(n)*x(n))' ocp 'profit =e= sum(n, b(n)*x(n))';
Теперь запишем сами уравнения. Сначала вычислим, сколько сырья потребуется на производство продуктов, и сравним его с остатками склада по каждому виду сырья. Для расчета количества сырья по каждому виду продукции умножим количество продуктов, которые нужно произвести x(n) на a(f,n). А затем сравним полученные результаты с остатками склада по каждому виду сырья s(f). В идеальном случае расход сырья должен быть равен остатку склада. Уравнения для расчета прибыли и выручки скопируем из предыдущего блока. При записи уравнений кавычки не нужны. Зато в конце строки после каждого уравнения нужно поставить точку с запятой:
nb(f).. sum(n, a(f,n)*x(n)) =l= s(f); ocr.. revenue =e= sum(n, d(n)*x(n)); ocp.. profit =e= sum(n, b(n)*x(n));
В конце нужно написать, что нужно провести моделирование, указав имя программы, которое было записвно в начале после команды $title и указать уравнения, которые нужно согласовать между собой:
Model cf 'Confectionery factory model' / all /;
И в последней стоке файла указать цель и как ее достигнуь: решить (указать сокращеное название файла cf), максимизируя прибыль с помощью линейного программирования:
solve cf maximizing profit using lp;
Для того, чтобы не переписывать всю программу еще раз добавим еще одну строку, закомментировав ее с помощью *. В этой строке попросим найти максимум выручки.
Тогда выполнив одно решение (например, посчитав максимум прибыли), мы можем поставить звездочку в начале строки, где просим разчитать максимум прибыли, и убрать звездочку в строке, где просим расчитать максимум выручки. После этих минимальных изменений, отправив задание еще раз, мы получим решение, в котором находится максимум выручки.
*solve cf maximizing revenue using lp;
Всё, файл создан. Набрать его можно в любом текстовом редакторе и сохранить под любым именем, но с расширением gms, например, alisa.gms.
Посмотрите готовый файл:
Текстовый файл с заданием кейса На кондитерской фабрике

Как отправить задание

Чтобы отправить задание alisa.gms на облачный сервер, нужно на начальной страничке сервера NEOS (https://neos-server.org) кликнуть команду Submit a job to NEOS.
Начальная страница сайта NEOS
В подменю выбираем конкретный движок. Для той формы задачи, которая представлена в файле ***.gms, следует выбрать CPLEX [GAMS].
Выбор вида задачи оптимизации на странице сайта NEOS
На открывшейся страничке CPLEX оптимайзера внизу находим
Выбор  формы  для отправки задачи оптимизации на странице сайта NEOS
и заполняем форму Web Submission Form.

  Во-первых, выбираем файл с заданием.
Для этого нажмите Выберите файл, найдите нужный файл в проводнике. После этого название файла появится рядом с кнопкой Выберите файл, файл загрузился.
Форма для отправки файла с заданием   Во-вторых, имеет смысл запросить файл листинга выполненного задания
Return GAMS listing file ( расширение этого файла lst), который содержит основную информацию. На всякий случай можно попросить и лог-файл с диагностикой Return log file. Форма для вывода результата   В-третьих, укажите адрес электронной почты, на который нужно прислать результаты и щелкнете Submit to NEOS. Клавиша для отправки файла с заданием    Short Priority указывать не обязательно, обычно задача и так выполняется быстро и в очереди заданий не стоит. Но если вы не уверены, что задача решится за 5 минут, Short Priority запрашивать точно не нужно.
Сервер проверит ошибки и в случае их отсутствия сообщит в новом окне, что задание принято. Через несколько секунд или минут, в зависимости от очереди заданий у сервера и сложности вашей задачии, сервер выдаст результат. Простые задачи с малым количеством переменных не требуют более нескольких секунд времени.

Как выглядит полученное решение

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

   Решение задачи оптимизации содержится в блоке:
LOWER LEVEL UPPER MARGINAL NutRinging . 69303.030 +INF . ParadiseTaste . . +INF -144.272 GoldenBar . . +INF -19.073 SiberianSquirrel . 40424.242 +INF . LateEvening . 35490.358 +INF . LateEvening . . +INF -92.294
Значения параметра MARGINAL - это приведенные стоимости продуктов из отчета об устойчивости, который был получен при решении задачи с помощью Поиска решений MS Excel.
   А этот блок листинга - таблица ограничений отчета об устойчивости с теневыми ценами (значения параметра MARGINAL):
LOWER LEVEL UPPER MARGINAL DarkChocolate -INF 57907.466 58200.000 . LightChocolate -INF 7450.000 7450.000 1626.501 Sugar -INF 19000.000 19000.000 405.041 Caramel -INF 22800.000 22800.000 604.545 Nuts -INF 38060.165 39000.000 .
Необходимо отметить, что формат заданий на оптимизацию несколько отличается у солверов разных производителей. Различаются и требования к формату вводимых данных. Однако, уровень сложности формы заданий хоть в специфических форматах движков оптимизации, хоть в форме программы на языке Phyton, практически не различается. Можно пользоваться тем, что нравится или чем владеете.

Конечно, отчет о результатах для задачи в тысячу переменных смотрится не очень вдохновляюще. :)
Но есть и обнадеживающие тенденции. Буквально в последние годы инструменты оптимизации поворачиваются лицом к Excel и в плане более удобного чтения данных прямо из файлов Excel и в плане удобных интерфейсов «Excel – сервисы оптимизации».

OpenSolver

OpenSolver ( https://opensolver.org ) – этo надстройка к MS Excel, полностью бесплатная, содержит линейный, целочисленный и нелинейный оптимизатор с открытым исходным кодом. Разрешено свободное модифицирование инструмента для собственных целей.

  На странице OpenSolver можно выбрать версию для Windows или Mac в модификациях только линейная оптимизация (Linear) или линейная + нелинейная оптимизация (Advanced).

  Фактически OpenSolver содержит распространенные и известные оптимизационные движки (разрешенные к бесплатному использованию), а некоторые другие ( например, Gurobi) может использовать при наличии у пользователя лицензии (в том числе бесплатной). Панель OpenSolver
Скачать OpenSolver здесь.

Как установить OpenSolver

Надстройка не устанавливается инсталлятором, ее нужно распаковать в удобное место (очень желательно в какую-то стандартную папку, путь к которой не содержит символов кириллицы или юникода) и подгружается либо прямым запуском файла opensolver.xlam, либо подключением из меню подключения надстроек Excel

Файл\Параметры\Надстройки -> кнопка «Обзор» + выбор файла opensolver.xlam + галочка на OpenSolver

Появляется панель надстройки там же, где и штатный Поиск решения в меню Данные
Панель запуска OpenSolver в MS Excel
Надстройка OpenSolver проста в использовании. В ней нет ограничений на число переменных и условий, так как использует в основном свободно распространяемые солверы.

Первый этап решения вашей задачи - построение модели. Для этого используется кнопка Model.

Описание панели OpenSolver-Model

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


Блок Constraints (Ограничения).


    Для того, чтобы добавить ограничение
  1. Выделите курсором команду Add new constraint.
  2. Введите отдельно левую и правую часть ограничения, а знак между ними.
  3. Нажмите кнопку Add constraint.
Как добавть ограничения

    Для того, чтобы исправить ограничение
  1. Щелкните ограничение в окне.
  2. Сделайте необходимые исправления.
  3. Нажмите кнопку Update constraint
Как изменить ограничение

    Для того, чтобы удалить ограничение
  1. Щелкните ограничение в окне.
  2. Нажмите на клавишу Delete selected constraint.
Как удалить ограничение в OpenSolver
Для решения большинства задач необходимо отметить галочкой поле Make unconstrainted variable cells non-negative (Сделать переменные без ограничений неотрицательными).
  Если вы используете именованные диапазоны (задают через меню Формулы\Задать имя), то OpenSolver предлагает показывать такие имена в установках ограничений. Для этого используется команда Show named ranges in constraint list. Если отметить этот пункт, то OpenSolver дописывает эти имена после диапазона ячеек в скобках.


Блок Sensitivity Analysis.

Как вывести отчет об устойчивости на отдельный лист Как вывести отчет об устойчивости на тот же лист

Блок Solver Engine.

Блок Solver Engine
В этом блоке необходимо прямо выбрать движок оптимизации, нажав на кнопку Solver Engine...
Появится панель OpenSolver - Choose Solver, на которой нужно выделить подходящий вам движок, или оставить рекомендуемый COIN-OR CBC (Linear solver).
   Движок CBC (COIN-OR CDC(Linear solver)) вполне достаточен для решения любых линейных задач.
Необходимо выбрать движок
Показанные в списке движки могут быть недоступны.
В версии надстройки «OpenSolver2.9.4_ AdvancedWin» имеются доступные по умолчанию Bonmin, Couenne, Nomad - движки нелинейной оптимизации.
Движок Gurobi будет доступен только если установить доступную версию этого движка с сайта производителя.
Движки с именем Neos… вызываются прямо из облачного сервиса, поэтому без подключения к интернет не работают.
Чтобы эта опция работала корректно, нужно в меню Model\Option\Email… указать свой регистрационный адрес на NEOS или любой действующий мэйл.
Время решения задачи с использованием движков Neos... удлиняется за счет связывания с облачным сервером.
   После того, как все данные задачи внесены (модель построена), нажмите кнопку Save Model.
Затем запустите решение задачи.

Как запустить решение задачи в OpenSolver.

Для того, чтобы запустить оптимизацию нажмите кнопку Solve.
Панель запуска задачи оптимизации в OpenSolver
Либо полную, со всеми ограничениями, либо с игнорированием целых ограничений (Solve relaxation), что весьма удобно для пользователя.
Так как решение целочисленных задач оптимизации гораздо более длительно по времени, чем решение обычных задач линейной оптимизации, то опция игнорировать целые ограничения существенно сокращает время расчетов. Поэтому имеет смысл сначала попробовать решить задачу «Поиском решения» или другим движком оптимизации без условия целочисленности, а затем, в случае успеха, пробовать решать задачу с целочисленными ограничениями.
Команда Show/Hide Model подсвечивает или снимает подсветку диапазонов данных, фигурирующих в установках модели.
Собственно, подсветка не особенно удобна, поскольку накрывает данные полупрозрачными фигурами, блокируя их изменение с клавиатуры. Представляется более простым самостоятельно выделять цветом «играющие» диапазоны ячеек. Но для контроля введенных параметров опция может быть полезна.

Команда Quick solve позволяет быстро провести оптимизацию, если в данных произошли небольшие изменения.

Команда OpenSolver разворачивает список возможных технических отчетов об оптимизации (лог результатов со временем счета, ошибки и проч…).

   Следует отметить, что надстройка OpenSolver подхватывает и показывает сохраненные установки «Поиска решения», кроме технических.
Так как применение надстройкой облачных сервисов оптимизации не отличается от использования встроенных движков, надстройка позволяет использовать облачные сервисы оптимизации так же легко, как и локальный инструмент.

Отчет об устойчивости в OpenSolver.

Отчет об устойчивости выглядит и формируется практически так же, как в «Поиске решения». С тем отличием, что в отчете «Поиска решения» ограничения, наложенные прямо на переменные, не отображаются вообще, а в OpenSolver – отображаются в таблице Constraints.
   Здесь приведен отчет об устойчивости для решения кейса Кондитерская фабрика Алиса, в котором задано условие: минимальный объем производства всех конфет должен быть не ниже 5000 кг. По этому отчету можно понять, что увеличение нижней границы производства для «Райского вкуса» до 5000+30674,8 кг будет сопровождаться потерями в прибыли 144,27 руб на каждый дополнительный кг. Если нижнюю границу поднять выше, до 50 тыс кг, например, теневая цена ограничения возрастет (по модулю).
Отчет об устойчивости в OpenSolver

Google Docs

Существует вариант надстройки OpenSolver для популярных облачных таблиц из Google Docs.

1

Откройте список приложений Google

например, в Chrome/Сервисы и кликнете Таблицы
 Список приложений Google в Chrome

2

Загрузите ваш файл

Для этого:
   — На панели Таблицы создайте пустой файл
 Создание пустого файла в Таблицах Google
После этого появится новая таблица.
   — Нажмите команды Файл и Импортировать
 Как импортировать свой файл в Таблицы Google
Откроется панель Импорт.
   — На панели Импорт кликните Загрузка
 Панель Импортировать  в Таблицах Google
Теперь вы можете либо перетащить мышкой свой файл, либо выбрать его через кнопку Выбрать файл на устройстве.

3

Подключите OpenSolver

Для этого:
   — В окне Новая таблица или в окне с вашим файлом нажмите команды Дополнения и Установить дополнения
 Как установить дополнительные программы в Таблицах Google
   — Появится окно Google Workspace Marketplace. Наберите в строке Поиск, начало названия нужной программы open и в выпадающем списке выберите OpenSolver
 Как найти OpenSolver в Google Workspace Marketplace
   — После этого поиск выдаст ярлык программы OpenSolver.
 Ярлык OpenSolver в Google Workspace Marketplace
   — Кликните по ярлыку программы OpenSolver. Появится новое окно, в котором нажмите кнопку Установить
 кнопка Установить программы OpenSolver в Google Workspace Marketplace
После этого OpenSolver будет установлен после вашей автроризации в Google.

4

Запустите OpenSolver

Для этого:
   — В меню Дополнения выберите OpenSolver, а затем Open sidebar
 Запуск OpenSolver в Таблицах GoogleDocs

5

Работа с OpenSolver

Окно OpenSolver в Таблицах GoogleDocs внешне мало чем, отличается от штатного интерфейса OpenSolver.
 Панель OpenSolver в Таблицах GoogleDocs
Однако, в нем сначала нужно выделить диапазон ячеек, а потом нажать кнопку Add или Update у нужного окошка ввода.

В этой надстройке также имеется возможность выбора варианта оптимизатора. В ней, в том числе, можно выбрать один из оптимизаторов с сайта NEOS.
 Выбор движка надстройки OpenSolver в Таблицах GoogleDocs
Движок оптимизации Google Apps Script Linear Optimization Service,который используется по умолчанию, позволяет решать довольно большие задачи (тысячи переменных). Однако, оптимизация проходит довольно медленно. Поэтому возможность использования облачного оптимизатора NEOS COIN-OR Cbc может оказаться полезной.
Необходимо отметить, что движок Satalia(последний в списке) требует подписки.

5

Ограничения OpenSolver в Таблицах GoogleDocs

Установки OpenSolver for Google Sheet запоминаются и сохраняются для каждой страницы документа google-таблиц. Впрочем, наличие даже самого простого инструмента оптимизации в Таблицах Google – замечательно полезная вещь.

LibreOffice и OpenOffice

LibreOffice и OpenOffice (libreoffice.org, openoffice.org) - это родственные проекты бесплатных кроссплатформенных аналогов MS Office, ответвившиеся от одного корня и потому очень схожие.
Решатель находится по адресу Calc/Сервис/Решатель.
В Решателе LibreOffice имеются и нелинейные движки оптимизации, в OpenOffice – только движок линейной оптимизации.
Отчета о чувствительности нет в обоих Решателях.
Несмотря на очевидные недостатки и тот и другой Решатели могут быть использованы для поиска оптимального решения в задаче с большим числом переменных. Причем, сам файл может быть сформирован в Excel, а потом открыт в Calc\LibreOffice, например, оптимизирован Решателем и сохранен в том же формате Excel.
В бесплатных аналогах Excel имеются не все функции MS Excel, но актуальные при оптимизации функции присутствуют.

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