Optimalizačný softvér na ulabserve
- Podrobnosti
- Kategória: Výskum
- Napísané: sobota, 12. január 2013, 22:43
- Ostatná aktualizácia: sobota, 23. február 2013, 18:06
- Napísal: Michal Kaukič
Krátky popis systémov (OSS aj komerčných) pre LP, MILP, MINLP, constraint programming, modelovacie jazyky, ktoré máme nainštalované na ulabserve a ku ktorým má prístup každý člen katedry, ba i študenti a doktorandi FRI. Ak by bolo niečo nejasné, alebo nefunkčné, obráťte sa na mňa. Uvádzam aj odkazy na dokumentáciu. Kto niečo pekné naštuduje a chce sa s poznatkami podeliť, tak buď formou článku na tejto našej stránke, alebo na seminári KMM (kontakt: doc. Peško).
Samostatné riešiče a knižnice, OSS:
glpk
webstránka: http://www.gnu.org/software/glpk/
dokumentácia (z distribúcie): riešič a knižnica, jazyk GMPL
charakteristika: LP, MILP, knižnica (C, Python), samostatný riešič glpsol, modelovací jazyk GMPL
aktuálna verzia: 4.47, 9. sept. 2011, na ulabserve 4.45
lp_solve
webstránka:http://lpsolve.sourceforge.net/5.5 (odkazy na stiahnutie, aj dokumentácia)
charakteristika: LP, MILP, knižnica (C, Python, MATLAB, octave, Excel, Scilab, Php, Java, Delphi,...), samostatný riešič lp_solve, vie načítať GMPL, AMPL, Cplex LP súbory, má IDE pre Windows
aktuálna verzia: 5.5.2.0, 12. aug. 2010, na ulabserve 5.5.0.13
scip (s podporou riešičov soplex, clp a gurobi)
webstránka: http://scip.zib.de/ (aj soplex, ZIMPL, gcg,...)
charakteristika: LP, MILP, MINLP, constraint programming (C/C++), samostatné riešiče, na ulabserve je scip, scip-gurobi, scip-clp, gcg gcg-gurobi (gcg je branch-cut-and-price riešič, kde pravidlá si môže určovať používateľ)
na ulabserve sú aktuálne verzie (stav 13. jan. 2013)
Pozn.: zo stránky programu pripájame porovnanie OSS a komerčných riešičov na testovacích problémoch MIPLIB
Komentár asi netreba.
coin-or, alebo COmputational INfrastructure for Operations Research
Táto stránka obsahuje veľa projektov, máme inštalované samostatné riešiče tieto:
clp - LP, simplex riešič
cbc - Branch and Cut, MILP
ipopt - Interior-Point riešič pre všeobecné rozsiahle nelineárne problémy (nie celočíselné problémy)
symphony - MILP riešič a knižnica, môže byť pre paralelné výpočty (ak bude záujem, skompilujem)
OSSolverService - nevoláme ho priamo, ale umožňuje iným programom (napr. scip,...) využívať coin-or riešiče
Komerčný, neobmedzený systém gurobi, akademická licencia
Toto je určite najsilnejší nástroj, aký máme k dispozícii - stačí sa pozrieť na obrázok vyššie. Je pre akademické účely zadarmo, každý, kto by ho chcel používať si môže licenciu jednoducho vyžiadať na webstránke http://www.gurobi.com, momentálne máme licenciu - ja, Štefan a Roman Hajtmanek. Na horeuvedenej webstránke je aj dokumentácia.Charakteristika systému: LP, MILP, QP (to, čo chýba Xpress-ákom), rozhranie pre C, C++, C#, Java®, Microsoft® .NET, Python, MATLAB, a R. Neoceniteľné je interaktívne prostredie gurobi.sh (je to vlastne IPython s modulmi pre gurobi). Môžem povedať, že tvorba modelu a riešenie v Pythone je pohodlné, ale v kombinácii s nižšieuvedenými modelovacími nástrojmi to ide ešte ľahšie. Len treba začať... môžeme to ukázať na seminári KMM.
Šéfom Gurobi je Robert Bixby, optimalizátor par excellence. Stačí si pozrieť jeho domovskú stránku. Priamy riešič sa volá gurobi_cl ale to asi často potrebovať nebudete.
Modelovacie jazyky a nástroje:
CMPL (Coin Mathematical Programming Language) a IDE Coliop
webstránka: http://projects.coin-or.org/Cmpl (je to jeden z projektov COIN-or)
charakteristika: jazyk pre matematické programovanie a systém pre LP a MILP optimalizáciu
Poznámka k modelovacím jazykom. Prvý bol AMPL - komerčný nástroj a podľa neho si veľa systemov vytvorili jazyky vlastné, čiastočne s AMPL kompatibilné (vyššie sme spomínali GMPL pre glpk, ZIMPL pre scip). Žiaden sa však nerozšíril tak, aby ho akceptovali komerčné systémy - tie majú vlastné modelovacie nástroje, alebo používajú GAMS, AIMSS. CMPL má taketo možnosti, už teraz sú priamo podporované glpk, scip, riešiče COIN-or a hlavne Cplex a gurobi (nepriamo aj ďalšie, pomocou formátov vstupných súborov MPS, Free-MPS či OSiL). Môj názor na takéto modelovacie jazyky je, že ich nedostatkom je malá vyjadrovacia schopnosť jazyka a tým vynútené neprehľadné programovanie.
Pyomo, ďalší projekt COIN-or
Je súčasťou projektu COOPR (COmmon Optimization Python Repository) ktorý máme inštalovaný na ulabserve. Je v ňom aj PySP (Python-based Stochastic Programming) a o Pyomo vyšla aj knižka Pyomo – Optimization Modeling in Python vo vydavateľstve Springer. Momentálne na ulabserve môžete s Pyomo použiť riešiče cbc, glpk a gurobi. Tento spôsob práce považujem za veľmi perspektívny, lebo v pozadí máte plnohodnotný programovací jazyk, ktorý nemá obmedzenia vyššieuvedených jazykov.
Numberjack je jednoduchý a prehľadný modelovací jazyk, založený na Pythone. Spája v sebe LP, MILP a aj constraint programming. Máme ho s riešičmi Mistral, MiniSat, WalkSat, SCIP,...).
Programovanie s obmedzeniami (constraint programming, CP):
(Postupne budeme dopĺňať popisy, príp. v samostatných článkoch príklady použitia. Isto pomôže Štefan a ďalší :-)
minizinc s rôznymi riešičmi (mzn-gecode, mzn-g12fd, mzn-g12mip, mzn-g12cpx, mzn-g12lazy, mzn-g12sat )
eclipse a grafické IDE tkeclipse
Google or-tools obsahujú riešič CP, riešiče LP a MILP, tiež špeciálne riešiče pre "routing problems" a aj niektoré grafové algoritmy (pre toky napr.).