Обзор и анализ на уеб-базирани софтуерни системи за оптимизация

Даниел Вътов

Цел на обзора

Направеното проучване на софтуерни системи, подпомагащи изследователите в областта на еднокритериалната оптимизация има две направления. От една страна е търсено сходство между функциониращи такива системи и идеите за проектираната, в рамките на научноизследователския проект, уеб-базирана система (с работно име УебОптим). Чрез анализ на вече съществуващи подобни системи, може да се получи ценна информация за това какъв е най-удачният модел на софтуерен дизайн за системата УебОптим. От друга страна са разглеждани и системи, доста различни като софтуерен дизайн от УебОптим. При тях са търсени отговори на конкретни въпроси, като например по какъв начин се добавя функционалност от 3-ти лица, какви формати на входни/изходни данни се поддържат и др. За целите на анализа на проучените софтуерни системи за оптимизация са използвани следните критерии:

Проучен софтуер

В анализа са включени следните софтуерни системи, които по някои от своите качества се доближават до идеите за проектираната софтуерна уеб-базирана система УебОптим:

pigale

http://pigale. /

Pigale е алгоритмична библиотека с десктоп редактор, специализирани за работа с равнинни графи. Поради това, че е десктоп софтуер, функциите за сигурността не са засегнати в дизайна. Софтуерната архитектура се различава от стандартната за този тип приложения, с това че има TCP сървър, през който може да се ползва библиотеката.

Oid

http://userhome. brooklyn. cuny. edu/skingan/matroids/software. html

Алгоритмична библиотека за работа с матроиди и графична среда за използване на алгоритмите от библиотеката. Както е посочено и от самите разработчици (автори и на алгоритмите), начинът за повторно използване на разработените алгоритми е като библиотека от Java класове или на ниво програмен код.

GraPHedron

http://www. /

Уеб-базирана система за автоматично генериране на предположения (conjecture) от теорията на графите. Системата е разработена като част от дисертационния труд на автора й. Специализирана е в прилагането на алгоритъм/алгоритми за точно определена целева област. Поради ограничената публичност няма възможност да се направи точна преценка на възможностите й.

WolframAlpha

http://www. /

Позволява търсене върху масив от структурирани данни с прилагането на модели и алгоритми, налични в Mathematica.

Coin OR Optimization Services

https://projects. coin-or. org/OS

Предоставя обобщена програмна рамка, състояща се от множество стандарти за представянето на оптимизационни задачи, резултати и настройки на решатели. Поддържа комуникация в разпределена среда между клиенти и решатели.

Neos

http://www-neos. mcs. anl. gov/

Основни характеристики на софтуерната система Neos

колекция от решатели всеки със свой формат на входни данни входните данни могат да са компресирани данните могат да се пращат по TCP, по пощата, XML-RPC, kestrel API

kestrel представлява интерфейс за доставяне на модели директно от интегрираните среди за моделиране на AMPL [1] и GAMS [2]

поддържа опашка на входящите задачи

Статистика

Решени задачи за 2009 година:

Брой модели според езици за моделиране:

AMPL – GAMS - 78562

Брой модели според метод на доставяне в сървъра:

Уеб – XML-RPC –kestrel –email - 4

Екип

разработчици и поддръжка на основната функционалност - 40 сътрудници в специфични области - 20

Заключение

Бяха разгледани различни като архутектура, обхват и сложност програмни продукти, за да се определят основните направления при разработването на софтуер в областта на математическата оптимизация. От разгледаните системи само Neos сървъра и Coin OR Optimization Services отговарят на определението за уеб-базирана система за оптимизация. Липсата на подобен тип системи може да се обясни с трудното им използване от потребители без необходимата подготовка. Подходът за преодоляване на тази пречка се изразява в предоставянето на интуитивен потребителски интерфейс, който да улесни въвеждането на входните данни. Такъв интерфейс е разработен в тези програмни продукти, при които се решават малко на брой типове задачи. За всеки тип задача се предоставя екран за въвеждане на необходимата информация (GraPHedron, pigale, Oid). Когато системата предоставя по-обобщен интерфейс за входни данни (WolframAlpha), има възможности за обработка на естествен език за по-прости задачи или за описание на задачата с формален език, когато проблемът е с по-голяма сложност. Почти всички системи позволяват използването им от отдалечени клиенти, както и предоставят интерфейс, подходящ за автоматизирано използване.

Изводът е че, при разработване на съвременните системи за оптимизация се отива в една от двете крайности – изграждат се системи, които поддържат много решатели и с тях могат да се решават различни и сложни оптимизационни проблеми или системи, които осигуряват по-интуитивен потребителски интерфейс, ориентирани към неопитни в областта на оптимизацията потребителите, но предназначени за решаване на един или няколко оптимизационни проблема. За да се развиват системи, които да успяват да обединят тези две противоречащи си цели, са необходими значителни ресурси. Нашата основна задача ще бъде да се изгради уеб-базирана система, която до известна степен да отговаря и на двете цели с възможностите на ограничените ресурси на проекта.

Литература

J. Czyzyk, M. Mesnier, and J. Moré, The NEOS Server, в http://puter. org/cise/cs1998/c3toc. htm IEEE Journal on Computational Science and Engineering, 5, 1998, 68-75, обсъжда се дизайнът и имплементацията NEOS сървъра. W. Gropp and J. Moré, Optimization Environments and the NEOS Server, в Approximation Theory and Optimization, M. D. Buhmann and A. Iserles, eds., Cambridge University Press, 1997, 167-182, разглежда се NEOS сървъра като среда за решаване на задачи, която опростява формулирането на оптимизационни задачи и осигурява достъп до изчислителни ресурси. E. Dolan, The NEOS Server 4.0 Administrative Guide, Technical Memorandum ANL/MCS-TM-250, Mathematics and Computer Science Division, Argonne National Laboratory, May 2001, разглеждат се имплементацията и използването на сървъра в детайли. Може да бъде свалена от http://www-neos. mcs. anl. gov/neos/ftp/admin. ps. gz. M. Ferris, M. Mesnier, and J. Moré, NEOS and Condor: Solving optimization problems over the Internet, разглежда се използването на Condor, разпределена система за управление на ресурси, като доставчик на изчислителни ресурси за NEOS. Може да бъде свалена от http://www. mcs. anl. gov/home/more/papers/neos-condor. ps. gz. E. D. Dolan, R. Fourer, J.J. Moré, and T. S. Munson The NEOS Server: Version 4 and Beyond, разглежда се развитието на сървъра през 2001, включително и Kestrel интерфейса. Може да бъде свалена от http://www-neos. mcs. anl. gov/neos/ftp/v4.pdf. E. D. Dolan and T. S. Munson, The Kestrel Interface to the NEOS Server, описва се използването на Kestrel интерфейса. Може да бъде свалена от http://www-neos. mcs. anl. gov/neos/ftp/kestrel. ps или http://www-neos. mcs. anl. gov/neos/ftp/kestrel. pdf. E. D. Dolan, J.-P. Goux, R. Fourer, and T. S. Munson, Kestrel: An Interface from Modeling Systems to the NEOS Server, дават се детайли за дизайна и използването на Kestrel интерфейса. Може да бъде свалена от http://www-neos. mcs. anl. gov/neos/ftp/kestrel2.pdf.