Úvod

Tento textík slouží hlavně studentům Optimalizačních metod na Matematicko-fyzikální fakultě UK, aby se rychle dostali z teoretického pohledu na lineární programování k praktickému řešení. Textík se zaměřuje na knihovnu GLPK, její řešič glpsol a jazyk GNU MathProg.

Tento návod je na některých místech úmyslně stručný. Pokud návod vás někde zmate nebo máte nápad, jak ho vylepšit, napište mi. Text je zveřejněný pod licencí CC BY-SA.

Pořízení GLPK

První program

V tomto návodu budeme používat glpsol, čili samostatný řešič pro GLPK. Abychom ho měli na co vypustit, potřebujeme si nejdříve napsat lineární program do souboru, a pak jej předhodíme řešiči.

První konstrukt, který každý programátor potřebuje, jsou komentáře: 

# toto je komentar a la bash 
/* toto je delsi
      dvojradkovy komentar ve stylu C */
Je taky dobré si uvědomit základní syntax jazyka -- pro GNU MathProg platí, že příkazy jsou oddělené středníky, mezery nehrají roli a na konci programu musí být kouzelné slůvko end;

Když už máme komentáře a základní syntax, dáme se do našeho prvního lineárního programu. Zkusme třeba tento:

max 3x + 5y - 2z
2x + 3z <= 5
2z - 3y <= 8
y >= 3
y <= 4
x,y,z >= 0

Proměnné si zadefinujeme klíčovým slovem var. Nejdřív je jméno proměnné, potom můžeme přidávat extra parametry. Můžeme třeba chtít, aby proměnná byla celočíselná -- pak k nim napíšeme slovíčko integer. Můžeme také dopsat dolní a holní odhad na proměnnou, pokud ho známe -- což v našem případě zjednoduší situaci.

V našem případě tedy máme:

var x >= 0;
var y, >= 3, <= 4;
var z >= 0;

Účelovou funkci napíšeme jako lineární funkci, která má vlastní označení (což není moc důležité, takže můžeme zvolit třeba obj. Označení se píše mezi slovo maximize/minimize a samotnou účelovou funkci. Naše účelová funkce bude:

maximize obj: 3*x + 5*y - 2*z;

Podmínky píšeme celkem přirozeně, s jednou podstatnou změnou: každá podmínka musí mít také svoje označení, které je před nerovností a končí dvojtečkou. Označení může obsahovat písmena a číslice.

V našem příkladu tedy máme: 

p1: 2*x + 3*z <= 5;
p2: 2*z - 3*y <= 8;

Nakonec ještě dopíšeme přání, že bychom program chtěli vyřešit, a to příkazem solve;. Celé dohromady to tedy vypadá takto:

# My Little Elpee: Optimization is Magic
var x >= 0;
var y, >= 3, <= 4;
var z >= 0;
maximize obj: 3*x + 5*y - 2*z;
p1: 2*x + 3*z <= 5;
p2: 2*z - 3*y <= 8;
solve;
end;

Řešič na náš program vypustíme příkazem glpsol.exe -m soubor1.mod. Výpis tohoto příkazu bude záznam o řešení a stručný výsledek (věta OPTIMAL LP SOLUTION FOUND, PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION a tak podobně).

Pokud chceme vidět celé optimální řešení, můžeme si buď vypsat pro nás důležité proměnné (o tom více v sekci Hrátky s výstupem) nebo použít parametr -w vysledek.txt, který vypíše všechno.

Automatizujeme

Ukažme si nyní triky na úspornější a přehlednější zápis s jiným ukolem, zadaným takto:

Napište lineární program, který hledá minimální vrcholové pokrytí
pro graf na 5 vrcholech s hranami:
  1 -- 2;
  1 -- 3;
  1 -- 4;
  2 -- 4;
  3 -- 5;
  2 -- 5;

Parametry (aneb konstanty) se dají definovat pomocí klíčového slova param. Definice je podobná jako u proměnných, jenom jim musíme nastavit konstantní hodnotu, a to pomocí značky :=. Parametr tedy může být třeba:

param N := 5;

Množiny nám pomohou psát uspornější programy, zvláště když pracujeme v oblasti grafů a dalších množinových struktur. Množiny jsou v MathProgu trochu zavádějící pojem, protože jako prvky mohou obsahovat jen samostatné prvky nebo uspořádané k-tice (a to vždy k-tice jednoho typu). To nám ale pro většinu použití bude stačit.

Množiny začneme využívat tak, že si vygenerujeme množinu indexů {1,2,3,4,5}, které označují vrcholy:

set Vertices := (1..N);

Zadefinujme si také množinu všech hran, tentokrát explicitně vypsanou:

set Edges := {(1,2),(1,3),(1,4),(2,4),(3,5),2,5)};

Jakmile máme nějaké množiny, můžeme pomocí nich také definovat proměnné. Když chceme indexovat přes nějakou množinu, používáme pro to notaci {iterator in Largeset}. Když pak uvnitř iterovaného výrazu přistupujeme k proměnné, používáme notaci x[i], případně pro vícerozměrné množiny x[i,j,k]. Zadefinujme si tedy pomocí množiny Vertices všechny proměnné xi:

var x{i in Vertices}, >= 0, <= 1, integer;

Sumy se hodí pro rychlou konstrukci podmínek nebo účelových funkcí. Notace je stejná, jako když iterujeme uvnitř množin, a uvnitř podmínek používáme x[i]. Budeme tedy potřebovat napsat účelovou funkci přes proměnné na vrcholech: 

minimize obj: sum{i in Vertices} x[i];

Teď budeme chtít přidat podmínku pro každou hranu. Hodilo by se, aby jazyk MathProg podporoval nějaký druh for cyklu, abychom všechny podmínky mohli přidat na jeden řádek. For cyklem to přímo říci nemůžeme, ale podmínky můžeme indexovat pomocí nějaké množiny:

condition_edge{(i,j) in Edges}: x[i] + x[j] >= 1;

A jsme hotovi! Výsledný celočíselný program tedy vypadá takto:

# Program na reseni minimalniho vrcholoveho pokryti
param N := 5;
set Vertices := (1..N);
set Edges := {(1,2),(1,3),(1,4),(2,4),(3,5),(2,5)};
var x{i in Vertices}, >= 0, <= 1, integer;
minimize obj: sum{i in Vertices} x[i];
condition_edge{(i,j) in Edges}: x[i] + x[j] >= 1;
solve;
end;

Hrátky s výstupem

Jakmile glpsol doběhne, tak (podle parametrů) buď odpoví jen jednou větou nebo naopak vysype hodnotu všech proměnných a těsnost všech podmínek. Abychom nemuseli luštit z tabulky, které proměnné a podmínky nás zajímají, můzeme si zapsat vlastní výstupní příkazy.

Mezi solve; a end; můžeme také přidat příkazy printf, které do výstupu programu navíc zapíšou námi zvolené texty a hodnoty. Printf se chova jako v jazyce C -- první parametr je formátovací řetězec, ostatní jsou hodnoty, které se do formátovacího řetězce vloží. Nejprve můžeme třeba napsat řádek bez dat:

printf "#OUTPUT:\n";

Příkaz printf můžeme také indexovat pomocí iterování přes množinu, což se nám pro vrcholy může hodit:

printf{i in Vertices} "Vrchol %d ma hodnotu %d\n", i, x[i];

Protože už máme vyřešeno (už jsme pod příkazem solve;, můžeme uvnitř příkazu printf použít výrazu if k tomu, abychom podmínili výstup, čili můžeme napsat:

printf "Vrchol 1 %s\n" , (if (x[1] = 1) then "byl pouzit" else "nebyl pouzit");

Výraz if je v MathProgu kuriózní stvůra -- není to příkaz (jako set, var, for, printf), ale výraz (jako 3,"string", (1..8)) Náš kód se tedy v závislosti na optimální hodnotě x[1] buď vyhodnotí jako: 

printf "Vrchol 1 %s\n" , "byl pouzit";
nebo jako 
printf "Vrchol 1 %s\n" , "nebyl pouzit";

Ten samý trik s příkazem if můžeme použít i na formátovací řetězec, což nám umožní se buď odkázat na konkrétní vrchol, nebo ve výpisu nechat prázdný řádek. Využijeme totiž toho, že po expanzi zbude printf "",3, což je korektní zápis vypisující "".

printf (if x[3] > 0 then "Vrchol %d byl pouzit\n" else ""), 3;

Nakonec ještě jeden řádek bez dat:

printf "#OUTPUT END.\n";
Celkově náš upravený program pro minimální vrcholové pokrytí vypadá takto: 
# Hubaty program na reseni minimalniho vrcholoveho pokryti
param N := 5;
set Vertices := (1..N);
set Edges := {(1,2),(1,3),(1,4),(2,4),(3,5),(2,5)};
var x{i in Vertices}, >= 0, <= 1, integer;
minimize obj: sum{i in Vertices} x[i];
condition_edge{(i,j) in Edges}: x[i] + x[j] >= 1;
solve;
printf "#OUTPUT:\n";
printf{i in Vertices} "Vrchol %d ma hodnotu %d\n", i, x[i];
printf "Vrchol 1 %s\n" , (if (x[1] = 1) then "byl pouzit" else "nebyl pouzit");
printf (if x[3] > 0 then "Vrchol %d byl pouzit\n" else ""), 3;
printf "#OUTPUT END\n";
end;
A na jeho výstupu se mimo jiné objeví: 
#OUTPUT:
Vrchol 1 ma hodnotu 1
Vrchol 2 ma hodnotu 1
Vrchol 3 ma hodnotu 0
Vrchol 4 ma hodnotu 0
Vrchol 5 ma hodnotu 1
Vrchol 1 byl pouzit
#OUTPUT END

Co dál?

Teď už byste měli mít dostatečnou hrubou představu o jazyce, abyste mohli začít psát vlastní programy. Asi nebudou syntakticky správně hned na první pokus, ale s pomocí příkladů výše a anglického referenčního manuálu svůj program určitě vypilujete.

Nezapomeňte, můžete si napsat program, který vám soubor s MathProgem vygeneruje -- výsledný lineární program může být jakkoli ošklivý, co do zápisu, stačí jen, že to bude validní lineární program a že ho glpsol během několika minut vyřeší. Většinu konstrukcí popsaných výše (množiny, sumy, podmínky, iterátory) tedy vůbec nepotřebujete, pokud lineární podmínky vygeneruje sám váš generátor.

Na druhou stranu, jazyk GNU MathProg je o dost bohatší, než co jste stihli spatřit z rychlíku. Pokud budete chtít vytvořit řešení stručné a elegantní, určitě využijete dalších výrazů a příkazů, které najdete v referenčním manuálu.

Užitečné odkazy