Использование пакетов прикладных программ для решения оптимизационных задач.

 

1. Вычислительные алгоритмы для решения задач линейного программирования ( ЛП).

 Благодаря развитию компьютерной техники и разработке эффективных вычислительных методов, задачи ЛП с несколькими тысячами переменных и ограничений сегодня рассматриваются как “небольшие”. Достаточно быстро решаются задачи, имеющие десятки и сотни тысяч переменных.

Современное программное обеспечение (ПО) для решения задач ЛП бывает двух видов:

·        Алгоритмическое ПО рассчитано на нахождение оптимальных решений конкретных задач ЛП. На входе задается список коэффициентов ограничений (A, b, c в стандартной форме) и на выходе выдается результат - оптимальные значения переменных.

·        Системы моделирования позволяют сформулировать задачу ЛП (а в ряде случаев, ЦЛП и НЛП) в естественной и удобной форме, близкой к математической записи и проанализировать ее решение, представить результат в такой же удобной для пользователя форме. Перевод в форму, требуемую для реализации алгоритма, производится автоматически. Запись оптимизационной осуществляется на языке моделирования.

Дадим краткое описание доступного бесплатного ПО, бесплатных демо-версий систем моделирования и коммерческого ПО.

Бесплатное ПО

Пакеты, использующие симплекс-метод:

1. Lp_solve. Написан на C++. Решает задачи ЛП с количеством переменных до 30000 и ограничений — до 50000. Текущая версия 3.0. Условия использования — Lesser GNU Public License. Существует конвертер из формата MPS в формат Lp_solve. Может решать задачи с целочисленными переменными.

2. LP-Optimizer. Решает задачи ЛП и ЦП. Доступны бесплатно исходные тексты на Borland Pascal 7.0, исполняемые файлы для DOS http://www.netcologne.de/~nc-weidenma/lp_dos.zip и OS/2.

3. SoPlex. Объектно-ориентированная реализация прямого и двойственного симплекс-метода. Доступны исходные тексты.

4. SPLP. Составная часть библиотеки программ SLATEC. Написан на Фортране. Решает задачи ЛП с несколькими тысячами переменных и ограничений.

5. GULF. Реализация симплекс-метода для задач ЛП и задач дробно-линейного программирования. Допускает две линейные целевые функции.

Пакеты, реализующие метод внутренних точек:

1. PCx. Разработан Optimization Technology Center при Argonne National Laboratory (http://www.ece.nwu.edu/OTC) и Northwestern University. Доступны исходные тексты на Fortran’е и C, а также исполняемые файлы для Windows и Unix, плюс к этому имеется графический интерфейс на Java (http://www.mcs.anl.gov/otc/Tools/PCx/PCxGUI). Входные данные должны быть подготовлены либо в формате MPS, либо с использованием языка моделирования AMPL.

2. BPMPD. Пакет, реализующий метод внутренних точек для задач линейного и выпуклого квадратичного программирования. Демонстрационная версия решает задачи любой размерности, но не выводит оптимальные значения переменных для задач размерности более 500  500. Имеются исполняемые файлы и DLL под Windows 95/NT и различные исполняемые файлы под разные Unix-системы.

3. HOPDM. Пакет, решает задачи линейного и выпуклого квадратичного программирования, причем обладает некоторыми интересными функциями, такими как “теплый старт”, позволяющий использовать готовые решения и др. Возможности HOPDM, описаны на Web-странице (http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html). Доступны исходные тексты на Фортране (версия 2.13, только ЛП) и C (версия 2.30) по запросу.

4. Существуют системы, основанные на методе внутренних точек, позволяющие решать задачи ЛП в режиме "онлайн", без скачивания программ на локальный компьютер. NEOS Server (http://www-neos.mcs.anl.gov) позволяет запускать оптимизаторы, включая коммерческие, в таком режиме.

 

Системы моделирования:

1.     LPL. Язык математического моделирования для формулирования, хранения и решения задач ЛП и смешанно-целочисленного ЛП (СЦЛП). Имеет возможность использования различных логических ограничений, которые автоматически транслируются в символьном виде в алгебраические ограничения с использованием булевых переменных. ПО и документация доступны для бесплатного использования.

2.     GAMS. Студенческая версия доступна на http://www.gams.com/download. Эта версия ограничивает размеры решаемых задач. На сайте имеется большая библиотека моделей, написанных на GAMS -  http://www.gams.com/modlib/modlib.htm .GAMS подробнее описан ниже, в разделе 6.1.3.

3.     AMPL (http://www.ampl.com/TRYAMPL) Студенческая бесплатная версия AMPL позволяет решать задачи до 300 переменных и 300 ограничений + целевые функции.

Демо-версии коммерческого ПО.

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

Вот некоторые из таких демо-версий:

·        ANALYZE, MODLER, RANDMOD (http://www.cudenver.edu/~hgreenbe/imps/software.html)

·        LINDO, LINGO и What's Best! (http://www.lindo.com/)

·        LOQO со встроенным интерфейсом AMPL (http://www.princeton.edu/~rvdb/loqoexecs.html)

·        MOSEK API и комплект инструментов для MATLAB (http://www.mosek.com/request/download.html)

·        MPL  с CPLEX (http://www.maximal-usa.com/download/)

·        Visual XPRESS  с XPRESS-MP (http://www.dashopt.com/downloads/)

К пакетам, позволяющим решать задачи ЦЛП, можно отнести, помимо описанного выше, LP_Solve.

OPBDP (ftp://ftp.mpi-sb.mpg.de/pub/guide/staff/barth/opbdp/opbdp.html) — реализация на C++ переборного алгоритма для решения задач булевой оптимизации.

Omega (http://www.cs.umd.edu/projects/omega) анализирует системы линейных уравнений с целочисленными переменными. Эта программа не решает задач оптимизации, однако может быть использована для анализа и упрощения моделей ЦЛП.

 

 

2.  Вычислительные алгоритмы для решения задач нелинейного программирования (НЛП).

Каким же образом можно решить практическую задачу НЛП? Где можно найти необходимое программное обеспечение? К настоящему времени разработано достаточно много алгоритмов решения задач НЛП, воспользоваться которыми можно, используя возможности Интернета.

1. Если необходимо просто решить конкретную задачу НЛП, можно обратиться в Optimization Technology Center (http://www.ece.nwu.edu/OTC/). Важнейшей частью этого сайта является NEOS (Network-Enhanced Optimization System), содержащий библиотеку оптимизационного программного обеспечения, оптимизационный сервер (http://www-neos.mcs.anl.gov/) для использования этой библиотеки в сети, а также необходимую информацию о программном обеспечении. Система NEOS позволяет решать задачи ЛП и НЛП.

2. Следующие Веб-сайты предлагают решение задач НЛП пользователей.

·        AMPL (http://www.ampl.com/TRYAMPL) Студенческая бесплатная версия AMPL позволяет решать задачи до 300 переменных и 300 ограничений + целевые функции. Имеется выбор среди 8 решателей для задач НЛП.

·        BARON (http://archimedes.scs.uiuc.edu/cgi/run.pl) Задачи нелинейного целочисленного программирования можно посылать для решения с помощью пакета BARON с простым алгебраическим форматом для записи моделей, используя либо Веб-форму, либо локальный файл.

·        Network-Enabled Optimization System (NEOS) Server (http://www-neos.mcs.anl.gov) предлагает доступ к нескольким десяткам сольверам для решения задач ЛП, НЛП, сетевого и стохастического ЛП. Задачи НЛП принимаются сервером либо в форме программы на С или Фортране, либо модель должна быть записана на одном из языков моделирования, таком как AMPL и GAMS.

·        UniCalc (http://www.rriai.org.ru/UniCalc/calculate.html) Задачи НЛП, записанные на языке алгебраического моделирования UniCalc, могут посылаться для решения, используя интерфейс Веб-формы.

Бесплатное программное обеспечение

Бесплатное программное обеспечение содержится по следующим адресам:

1. Netlib ftp://www.netlib.org/opt/index.html, где имеются следующие алгоритмы:

·        conmax (минимизация функции с нелинейными ограничениями);

·        donlp2 (нелинейная оптимизация для дифференцируемых функций);

·        dqed (метод наименьших квадратов для нелинейных функций при линейных ограничениях);

·        hooke (оптимизация без ограничений и без использования производных);

·        lbfgs (нелинейная оптимизация  при ограничениях вида );

·        lsnno (нелинейная оптимизация  при линейных сетевых ограничениях);

·        praxis (оптимизация без ограничений и без использования производных);

·        simann (оптимизация без ограничений с использованием метода отжига Simulated Annealing);

·        subplex (оптимизация без ограничений);

·        tn (Метод Ньютона для оптимизации без ограничений или с простыми ограничениями вида );

·        varpro (метод наименьших квадратов для сепарабельных функций);

·        ve08 (оптимизация без ограничений для сепарабельной функции).

2. http://plato.la.asu.edu/donlp2.html - Более новая версия алгоритма donlp2, разработанная P. Spellucci (Дармштадт) для решения общей НЛП с ограничениями-равенствами и ограничениями-неравенствами. donlp2 может бесплатно использоваться для некоммерческих и исследовательских целей.

3. Пакеты для задач НЛП с ограничениями :

·        http://www-unix.mcs.anl.gov/~more/tron/ TRON, метод Ньютона (авторы - Lin и Mor);

·        http://www.ece.nwu.edu/~nocedal/lbfgsb.html L-BFGS-B - метод с ограни­ченной памятью.

4. http://www.willnaylor.com/wnlib.html WNLIB (авторы - Bill Chapman и Will Naylor) содержит алгоритмы сопряженного градиента и сопряженных на­правлений для решения задач НЛП;

5. http://www.asset.com/WSRD/abstracts/ABSTRACT_362.html  - Библиотека математических подпрограмм NSWC содержит алгоритм OPTF минимизации функции n переменных и алгоритм HBRD решения системы нелинейных уравнений;

6. http://bedvgm.kfunigraz.ac.at:8001/alex/solvopt/solvopt.html -Алгоритм ло­кальной оптимизации негладких задач НЛП SolvOpt (авторы Alexei Kuntsevich и Franz Kappel). Тексты программ на C и Fortran, а также M-функции для MATLAB.

7. При работе с системой MATLAB (http://www.mathworks.com/) можно использовать следующее программное обеспечение :

·        Optimization Toolbox (http://www.mathworks.com/products/optimization) содержит алгоритмы для задач НЛП.

·        Пакет TOMLAB (http://tomlab.biz);

·        LOQO содержит MATLAB-интерфейс для квадратичного программирования.

·        MCS (http://www.mat.univie.ac.at/~neum/software/mcs) - пакет решения задач глобальной оптимизации, работающий в среде MATLAB;

8. В среде Mathematica (http://www.mathematica.com) могут быть использованы пакеты:

·        MathOptimizer (http://www.wolfram.com/products/applications/mathoptimizer), предназначен для нахождения глобальных и локальных решений общего класса задач НЛП.

·        Global Optimization

(http://www.wolfram.com/products/applications/globalopt) представляет собой множество функций для глобальной нелинейной оптимизации, использующих систему Mathematica;

9. GALAHAD (http://galahad.rl.ac.uk/galahad-www) - решение задачи НЛП большой размерности. Бесплатно распространяется для некоммерческого использования.

10. IPOPT

(http://www-124.ibm.com/developerworks/opensource/coin/Ipopt)

- Алгоритм внутренней точки для задач НЛП большой размерности. Свободно распространяется.