==============
Obsah archivu
==============

presentation/
Prezentace připravená k obhajobě DP

text/
Text diplomové práce

text/experiments
Základní experimenty - jsou zatíženy chybným návrhem
a chybami v programu

prog/hybridscp
Hybridní algoritmus ve formě knihovny

prog/clihybrid
CLI rozhraní pro knihovnu. Na vstupu akceptuje matice ve formátu
jako je soubor matrix.dat

prog/boomadapt
Přizpůsobovací třída pro BOOM


==================
Začlenění do BOOMu
==================

Knihovna hybridscp je závislá na následujících knihovnách:
a)GLPK (GNU Linear programming kit)
b)GNU MP (Knihovna pro přesnou aritmetiku MP - multiple precision)

Nejprve je třeba přeložit knihovnu GNU MP. Na internetu je
sice možné najít binárky pro Visual Studio, ale obvykle bývají
zastaralé, překlad ze zdrojových textů je jistější.

Je třeba mít MinGW (port GNU toolchainu) a MSYS (minimální sada
nástrojů a emulátor terminálu potřebný k překladu programů 
využívajících autotools). Obojí je dostupné na adrese http://www.mingw.org

Při překladu se postupuje stejně jako pod unixovým systémem:
1) Rozbalí se archiv
2) Spustí se emulátor terminálu, přejde se do adresáře se zdrojovým textem
   a postupně se spustí následující příkazy
   ./configure --disable-static --enable-shared
   make
   make check
   make install
3) V adresáři se zdrojovým textem se objeví adresář .libs, ve kterém se
   spustí příkaz:
   lib /machine:i386 /def:libgmp-3.dll-def
   lib je program, který se dodává k Visual Studiu. Nyní je už vše potřebné
   k dispozici - .lib soubor .dll soubor a soubor gmp.h - tyto soubory 
   je třeba uschovat

Dalším krokem je překlad knihovny GLPK. Binárky na internetu jsou aktuální, ovšem
mají podstatnou nevýhodu - nejsou přeloženy s podporou knihovny GNU MP a tedy
funkce glp_exact() je pomalá. Se zdrojovými texty se sice dodává dávkový soubor
pro překlad pomocí Visual C++, ale opět bez podpory pro GNU MP.

Nejlépe je postupovat takto:
1) Rozbalí se archiv
2) Všechny .c soubory z adresáře src a .h soubory z adresáře include se přemístí
   do jediného společného adresáře vytvořeného někde mimo. Do tohoto adresáře
   se přidá soubor config.h, který obsahuje následující dva řádky:

   #define __WOE__ 1
   #define HAVE_GMP 1

3) Spustí se Visual Studio a založí se "Nový projekt z existujících zdrojových textů", jako
   typ se zvolí statická knihovna. Projekt se nastaví tak, aby ke knihovně GLPK byla přilinkována
   knihovna GNU MP - od toho je dialog na nastavení linkeru. Důležité je to, aby byly
   definovány symboly preprocesoru:

   HAVE_CONFIG_H
   HAVE_GMP 1

   Od toho je dialog pro nastavení preprocesoru

4) Knihovna se přeloží (Build solution)

Dalším krokem je překlad knihovny hybridscp.
1) Vezmou se všechny .c a .h soubory, zkopírují se do zvláštního adresáře
2) Vytvoří se "projekt ze stávajících zdrojových textů" - statická knihovna. Projekt se
   nastaví tak, aby byly přilinkovány knihovny GLPK a GNU MP. 
3) Knihonva se přeloží (Build solution)

Posledním krokem je kompilování BOOMu
Do BOOMu jsem neprováděl žádné zásahy, tzn. stačí do projektu přidat soubory HybridCover.cpp
a HybridCover.h a nastavit projekt, aby byly přilinkovány všechny potřebné knihovny a byly
viditelné všechny potřebné hlavičkové soubory. Také je třeba správně umístit soubor libgmp-3.dll
a případně ho přejmenovat na libgmp-3.dll.dll

Knihovna GLPK si s sebou nese jednu nectnost - při spuštění simplexové metody pracující
s racionálními čísly nefunguje vypnutí výpisů - já jsem je pro svoje potřeby zakomentoval, ale
je třeba udělat to opatrně:
if (podmínka) xprintf("...."); 
if (podmínka) /*xprintf("....")*/; (SPRÁVNĚ)
if (podmínka) /*xprintf("....");*/ (Špatně)

Celé se to zdá složité, ale je třeba to provést jen jednou

=========================
Poznámky k implementaci
=========================

Důležitá poznámka pro použití GLPK - počítat ihned s racionálními čísly je příliš pomalé,
proto se určitý počet iterací provede v oboru reálných čísel, následuje škálování pak
opět určitý počet iterací v oboru reálných čísel a potom teprve v oboru racionálních čísel.
Nelze se také spoléhat na to, že když glp_simplex() vrátí "našel jsem optimum", není třeba
spouštět glp_exact() - tak se snadno přijde o celočíselné řešení.

=========================
Možná vylepšení algoritmu
=========================

- V případě, že by se našel někdo, kdo by měl zájem hybridní
  algoritmus vylepšit (?), může udělat následující:

- Vyzkoušet jiný řešič LP problémů (například lp_solve)

- počítat Lexikografická minima trochu jinak - například neminimalizovat každou
  proměnnou zvlášť, ale po blocích, například místo série osmi minimalizací:

  min x1,min x2,min x3,min x4,min x5,min x6,min x7,min x8

  sérii dvou blokových minimalizací

  min 8x1 + 4x2 +2x3 +x4, min 8x5 + 4x6 +2x7 +x8

  (více malých LP problémů, nebo méně větších ?) 
  Nebo na to jít nějakou úpravou řešiče LP problémů, nebo napsat panu Kolokolovovi
  do RFR jak to řeší on.

- Použít bitový paralelismus u hladových algoritmů, které jsou součástí NBGA
  a u Lagrangeovské heuristiky, hlavně přijít na to proč LGH neakceleruje LCE.

- V rámci rešerše najít vylepšení Lagrangeovské heuristiky

- Podívat se na paralelní variantu kombinace GA a LCE
  Eremeev,Kolokolov: An application of genetic algorithm and L-class enumeration
                     to the integer programming problem
                   

- Pokusit se vysledovat nějaké závislosti mezi charakterem vstupní matice a optimálními
  parametry algoritmu

- Při vylepšování algoritmu by se měla omezit dynamická alokace paměti, ale pozor na ukládání
  příliš velkých struktur na zásobník - stalo se, že mi přetékal do různých částí programu
  a vyvolávaly se nesmyslné chyby
