Domáca úloha č.3

Vytvorte programy na hľadanie najmenšej dominujúcej množiny v grafe. Ako nástroj na výpočet lineárneho programovania a celočíselného lineárneho programovania použite lp_solve. Na uľahčenie práce sme napisali malý wrapper (nemusíte ho použiť, objekt primárne zabaľuje C-čkovský interface, do C++-kovskej triedy). Zoznam funkcií knižnice lpsolve nájdete tu. Naprogramovali sme pre vás malý ukážkový projekt.
  1. Vytvorte funkciu int min_dominating_set_size_ilp(std::vector<std::vector<int>> graph);. Táto funkcia má vytvoriť celočíselný lineárny program a použiť lp_solve na jeho vyriešenie. V komentári, ak to považujete za potrebné, vysvetlite, ako celočíselný lineárny program funguje.
  2. Vytvorte funkciu int min_dominating_set_size_bnb(std::vector<std::vector<int>> graph);. V rámci tejto funkcie vytvoríte vlastný branch and bound algorithmus na počítanie minimálnej dominujúcej množiny. Vetviť sa bude na binárnych premenných, ktoré zodpovedajú vrcholom. Na získanie dolného odhadu použijeme lineárnu relaxáciu programu z prvej podúlohy (samozrejme, pre premenné, pre ktoré sme už urobili voľbu musia byť v lineárnom programe primerane nastavené; btw. medzi prvou a druhou úlohou je prienik, snažte sa namiesto skopírovania identického kódu vytvoriť vhodnú pomocnú funkciu). V komenári vysvetlite, ako funguje vaša heuristika na vetvenie (na ktorom vrchole sa vetviť a ktorou vetvou sa vydať skôr).
Riešenie odovzdajte do 10.1. vrátane (v SEČ) majlom na adresu lukotka.pts@gmail.com. Všetky funkcie odovzdajte v jednom súbore, nazvanom dominating.hpp. Tento súbor nemá obsahovať funkciu main. V rámci tohoto súboru sa snažte použit includy v takejto forme: #include "lphelper.hpp", #include <lp_lib.h>. Upozoržnujem, neposielajte na túto adresu nič iné ako samotné odovzdanie riešenia domácich úloh (na túto adresu sa prihlasujem iba keď sťahujem domáce úlohy a posielam feedback a aj teraz som tam objavil nejaké majly o bakalárkach).