|
|
Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems
Kumar, Aryan ; Koutecký, Martin (vedoucí práce) ; Faliszewski, Piotr (oponent)
Celočíselné lineární programování (ILP) se ukázalo být mocným nástro- jem pro řešení obtížných problémů, zejména v oblasti výpočetní sociální volby, kde byl použit k řešení variant problému úplatků. V tomto prob- lému jde o nalezení nejmenší změny, která vede ke kýženému výsledku po- tom, co ve společnosti proběhne proces šíření názorů. Předchozí experimenty ukazují, že řešení tohoto problému pomocí ILP je omezené pouze na malé instance. Novější výsledky ukazují, že tentýž problém lze vyjádřit pomocí logických formulí v Presburgerově aritmetice (PrA) a lze tak dosáhnout složi- tosti podobné algoritmu ILP. Proto se nabízí provést praktickou analýzu přístupu založeného na PrA. V tomto projektu jsme vygenerovali náhodné instance s předepsanými parametry voleb a modelovali je jako instance ILP a PrA. Následně jsme takto získané instance vyřešili pomocí řešičů jako jsou např. GUROBI, GLPK a Z3 a provedli jsme srovnávací studii k vyhodnocení výkonnosti obou přístupů vzhledem k různých parametrům, jako jsou např. počet typů voličů a difúzních kroků. Naše výsledky ukazují, že přístup skrze ILP je v praxi robustnější než přístup PrA. 1
|
host ::
RSS.