Rozšířené matematické programování - Extended Mathematical Programming

Algebraické modelovací jazyky jako CÍLE, AMPL, HRY „MPL a další byly vyvinuty s cílem usnadnit matematický popis problému a propojit abstraktní formulaci se systémy správy dat na jedné straně a vhodnými algoritmy pro řešení na straně druhé. Pro širokou škálu aplikací byly vyvinuty robustní algoritmy a jazykové rozhraní pro modelování matematické programování problémy jako lineární programy (LP), nelineární programy (NP), smíšené celočíselné programy (MIP), smíšené programy doplňkovosti (MCP) a další. Vědci neustále aktualizují typy problémů a algoritmy, které chtějí použít k modelování v konkrétních doménových aplikacích.

Rozšířené matematické programování (EMP) je rozšíření k jazykům algebraického modelování, které usnadňuje automatické přeformulování nových typů modelů převedením modelu EMP do zavedených tříd matematického programování, které se řeší pomocí vyspělých algoritmů řešení. Lze vyřešit řadu důležitých tříd problémů. Konkrétní příklady jsou variační nerovnosti, Nashovy rovnováhy disjunktní programy a stochastické programy.

EMP je nezávislý na použitém modelovacím jazyce, ale v současné době je implementován pouze v GAMS. Nové typy problémů modelovaných pomocí EMP jsou přeformulovány pomocí řešení GAMS JAMS na dobře zavedené typy problémů a přeformulované modely jsou předány vhodnému řešiteli GAMS, který má být vyřešen. Jádrem EMP je soubor s názvem emp.info kde jsou do modelu přidány anotace potřebné pro přeformulování.

Rovnovážné problémy

Rovnovážné problémy modelují otázky vznikající při studiu ekonomické rovnováhy v matematicky abstraktní formě. Mezi problémy rovnováhy patří variační nerovnosti, problémy s Nashovými rovnováhami a problémy s vícenásobnou optimalizací s rovnovážnými omezeními (MOPEC). Použijte klíčová slova EMP k přeformulování těchto problémů jako smíšené problémy s doplňkovostí (MCP), třída problémů, pro které existuje vyspělá technologie řešitele. Vyřešte nově přeformulovanou verzi klíčového slova EMP problému pomocí řešení PATH nebo jiných her GAMS MCP řešitelé.

Příklady použití EMP k řešení problémů s rovnováhou zahrnují výpočet Cournot – Nash – Walrasovy rovnováhy ..,[1] modelování přidělování vody,[2][3] dlouhodobé plánování rozšíření přenosové linky elektrické sítě,[4] modelování averze k riziku agenti na trzích s tepelnou elektřinou s nejistým přílivem do vodních nádrží [5] a modelování variační nerovnosti na trzích s energií [6]

Hierarchická optimalizace

Problémy s hierarchickou optimalizací jsou matematické programy s dalším optimalizačním problémem v jejich omezeních. Jednoduchým příkladem je dvouúrovňové programování problém, který optimalizuje cíl na vyšší úrovni nad omezeními, která zahrnují další problém s optimalizací na nižší úrovni. Bilevel programování se používá v mnoha oblastech. Jedním z příkladů je návrh optimálních daňových nástrojů. Daňový nástroj je modelován na vyšší úrovni a clearingový trh je modelován na nižší úrovni. Obecně může být problém na nižší úrovni problém s optimalizací nebo a variační nerovnost. K usnadnění přeformulování problémů s hierarchickou optimalizací je k dispozici několik klíčových slov. Problémy s optimalizací dvouúrovňových modelů modelované pomocí EMP jsou přeformulovány na matematické programy s rovnovážnými omezeními (MPEC) a poté jsou řešeny jedním z řešitelů GAMS MPEC (NLPEC nebo KNITRO ).

Disjunktivní programování

Matematické programy zahrnující binární proměnné a definice disjunkce pro modelování diskrétních voleb se nazývají disjunktivní programy. Disjunktivní programy mají mnoho aplikací, včetně objednávání úkolů ve výrobním procesu, organizování složitých projektů časově úsporným způsobem a výběru optimální trasy v okruhu. V rámci EMP jsou implementovány postupy pro rozšíření lineárního a nelineárního disjunktivního programování. Lineární disjunktivní programy jsou přeformulovány jako smíšené celočíselné programy (MIP) a nelineární disjunktivní programy jsou přeformulovány jako smíšené celé číslo nelineární programy (MINLP). Jsou řešeny pomocí řešiče LogMIP 2.0 a případně dalších podřízených řešitelů GAMS.

Mezi příklady použití EMP pro disjunktivní programování patří problémy s plánováním v chemickém průmyslu[7]

EMP pro stochastické programování

EMP SP je stochastické rozšíření rámce EMP. Deterministický model s pevnými parametry se transformuje do stochastického modelu, kde některé z parametrů nejsou pevné, ale jsou reprezentovány pravděpodobnostními distribucemi. To se provádí pomocí anotací a konkrétních klíčových slov. Jednoduché a společné diskrétní a parametrické rozdělení pravděpodobnosti jsou možné. Kromě toho existují klíčová slova pro očekávaná hodnota, hodnota v riziku (VaR) a podmíněná hodnota v riziku (CVaR). Proměnné, které jsou měřítkem rizika, mohou být obsaženy v objektivní rovnici nebo v omezeních. EMP SP usnadňuje optimalizaci jednoho opatření rizika nebo kombinace opatření rizika (například vážený součet očekávané hodnoty a CVaR). Modelář se navíc může rozhodnout, že bude obchodovat s rizikovými opatřeními. Je také možné modelovat omezení, která platí pouze s určitými pravděpodobnostmi (náhodná omezení). V současné době lze s EMP SP použít následující řešitele GAMS: DE, DECIS, JAMS a LINDO. Ke zpracování předběžně vzorkovaného lze použít jakýkoli řešič GAMS deterministický ekvivalent problém.

Viz také

Reference

  1. ^ Outrata, JV, Ferris, MC, Červinka, M a Outrata, M (2015). „O rovnováze Cournot – Nash – Walras a jejich výpočtu“. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)
  2. ^ Britz, W, Ferris, MC a Kuhn, A (2013). „Modelování institucí přidělujících vodu na základě více optimalizačních problémů s rovnovážnými omezeními“. Environmentální modelování a software. 46: 196–207. doi:10.1016 / j.envsoft.2013.03.010.CS1 maint: více jmen: seznam autorů (odkaz)
  3. ^ Bauman, A, Goemans, C, Pritchett, J a McFadden, DT (2015). „Modelování nedokonale konkurenčních vodních trhů v západních USA“. Vybraný papír připravený k prezentaci na výročním zasedání Asociace zemědělské a aplikované ekonomiky v roce 2015 a Západní zemědělské ekonomické asociace, San Francisco, CA, 26. – 28. Července.CS1 maint: více jmen: seznam autorů (odkaz)
  4. ^ Tang, L; Ferris, MC (2015). „Hierarchický rámec pro modely dlouhodobého plánování napájení“. Transakce IEEE na energetických systémech. 30 (1): 46–56. Bibcode:2015ITPSy..30 ... 46T. doi:10.1109 / TPWRS.2014.2328293.
  5. ^ Philpott, A, Ferris, MC and Wets, R (2016). „Rovnováha, nejistota a riziko v hydro-termálních elektrických systémech“. Matematické programování, řada B.. 157 (2): 483–513. doi:10.1007 / s10107-015-0972-4.CS1 maint: více jmen: seznam autorů (odkaz)
  6. ^ Gabriel, SA, Conejo, AJ, Fuller, JD, Hobbs, BF a Ruiz (2013). Modelování komplementarity na energetických trzích. International Series in Operations Research & Management Science. 180. Springer New York, s. 181–220 a 323–384.CS1 maint: používá parametr autoři (odkaz)
  7. ^ Grossmann, IE (2012). "Pokroky v modelech matematického programování pro celopodnikovou optimalizaci". Počítače a chemické inženýrství. 47: 2–18. doi:10.1016 / j.compchemeng.2012.06.038.

externí odkazy