Jazyk algebraického modelování - Algebraic modeling language

Algebraické modelovací jazyky (AML) jsou na vysoké úrovni počítač programovací jazyky pro popis a řešení problémů vysoké složitosti ve velkém měřítku matematický výpočet (tj. ve velkém měřítku optimalizace problémy s typem).[1] Jedna zvláštní výhoda některých algebraických modelovacích jazyků, jako je CÍLE,[1] AMPL,[2] HRY,[1]MathProg,Mosel,[1][3] aOPL je podobnost jejich syntaxe s matematickým zápisem optimalizačních problémů. To umožňuje velmi stručnou a čitelnou definici problémů v oblasti optimalizace, kterou podporují určité jazykové prvky, jako jsou množiny, indexy, algebraické výrazy, výkonné řídké indexy a proměnné zpracování dat, omezení s libovolnými názvy. Algebraická formulace modelu neobsahuje žádné rady, jak jej zpracovat.

AML neřeší tyto problémy přímo; místo toho volá vhodné externí algoritmy k získání řešení. Tyto algoritmy se nazývají řešitelé a zvládne určitý druh matematické úlohy jako:

Základní prvky

Základními prvky AML jsou:

  • tlumočník modelovacího jazyka (samotná AML)
  • odkazy řešitele
  • uživatelská rozhraní (Uživatelské rozhraní)
  • zařízení pro výměnu dat

Principy návrhu

Většina AML dodržuje určité konstrukční zásady:

  • vyvážená kombinace deklarativních a procedurálních prvků
  • otevřená architektura a rozhraní s jinými systémy
  • různé vrstvy s oddělením:

Generování modelu založeného na datech

Většina modelovacích jazyků využívá podobnosti mezi strukturovanými modely a relačními databázemi [4] poskytnutím vrstvy přístupu k databázi, která umožňuje modelovacímu systému přímý přístup k datům z externích zdrojů dat (např. tyto[5]manipulátory stolů pro AMPL). S vylepšením analytických technologií aplikovaných na obchodní procesy se optimalizační modely stávají nedílnou součástí systémů podpory rozhodování; optimalizační modely mohou být strukturovány a vrstveny tak, aby reprezentovaly a podporovaly složité obchodní procesy. V takových aplikacích lze vícerozměrnou datovou strukturu typickou pro systémy OLAP přímo mapovat na optimalizační modely a typické operace MDDB lze převést na agregační a disagregační operace na základním modelu [6]

Dějiny

Algebraické modelovací jazyky nacházejí své kořeny v programech pro generování matic a pro vytváření sestav (MGRW), vyvinutých na konci sedmdesátých let. Některé z nich jsou MAGEN, MGRW (IBM), GAMMA.3, DATAFORM a MGG / RWG. Tyto systémy zjednodušily komunikaci problémových instancí s algoritmy řešení a generování čitelné zprávy o výsledcích.

Časný generátor matic pro LP byl vyvinut kolem roku 1969 v Mathematisch Centru (nyní CWI) v Amsterdamu.[7]Jeho syntaxe byla velmi blízká obvyklé matematické notaci pomocí indexů en sigmas. Vstup pro generátor sestával ze samostatných sekcí pro model a data. Nalezlo uživatele na univerzitách i v průmyslu. Hlavním průmyslovým uživatelem byl výrobce oceli Hoogovens (nyní Tata Steel), kde se používal téměř 25 let.

Velký krok směrem k moderním modelovacím jazykům se nachází v UIMP[8], kde je struktura matematické programování modely převzaté ze skutečného života jsou analyzovány poprvé, aby bylo zdůrazněno přirozené seskupení proměnných a omezení vyplývající z těchto modelů. To vedlo k funkcím datové struktury, které podporovaly strukturované modelování; v tomto paradigmatu jsou všechny vstupní a výstupní tabulky spolu s rozhodovacími proměnnými definovány z hlediska těchto struktur způsobem srovnatelným s použitím indexů a sad, což je pravděpodobně nejpozoruhodnější rys společný pro všechny moderní AML a umožnil v čase oddělení mezi strukturou modelu a jeho daty a korespondenci mezi entitami v modelu MP a daty v relačních databázích. Model by tedy mohl být konečně instancován a vyřešen v různých datových sadách pouhou úpravou jeho datových sad.

Soulad mezi modelovacími entitami a relační datové modely,[4] umožněno bezproblémové generování modelových instancí načítáním dat z podnikových databází. Tato funkce nyní představuje velkou část použitelnosti optimalizace v reálných aplikacích a je podporována většinou známých modelovacích jazyků.

Reference

  1. ^ A b C d Kallrath, Joseph (2004). Modelování jazyků v matematické optimalizaci. Kluwer Academic Publishing. ISBN  978-1-4020-7547-6.
  2. ^ Robert Fourer; David M. Gay; Brian W. Kernighan (1990). „Modelovací jazyk pro matematické programování“. Věda o řízení. 36 (5): 519–554–83. doi:10,1287 / mnsc.36.5.519.
  3. ^ Gueret, Christelle; Prins, Christian; Sevaux, Marc (2002). Aplikace optimalizace s Xpress-MP. Dash Optimization Limited. ISBN  0-9543503-0-8.
  4. ^ A b Gautam Mitra; Cormac Lucas; Shirley Moody; Bjarni Kristjansson (1995). "Sady a indexy v modelování lineárního programování a jejich integrace s relačními datovými modely". Výpočetní optimalizace a aplikace. 4 (3): 262–283.
  5. ^ [1] Obsluha databází a tabulek pro AMPL
  6. ^ Koutsoukis, N .; Mitra, G .; Lucas, C. (1999). „Přizpůsobení on-line analytického zpracování pro rozhodovací modelování: interakce informací a rozhodovacích technologií“. Systémy podpory rozhodování. 26 (1): 1–30. doi:10.1016 / S0167-9236 (99) 00021-4. Citováno 22. listopadu 2017.
  7. ^ Jac. M. Anthonisse, Vstupní systém pro problémy lineárního programování, Statistica Neerlandica 24 (1970), 143-153.
  8. ^ Francis D Ellison; Gautam Mitra (1982). "UIMP: uživatelské rozhraní pro matematické programování" (PDF). Transakce ACM na matematickém softwaru. 8 (3): 229–255. doi:10.1145/356004.356005. Archivovány od originál (PDF) dne 18.01.2014. Citováno 2014-01-16.