Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems
Porovnání výkonu ILP řešičů a logických řešičů na problému úplatků
bachelor thesis (DEFENDED)
![Document thumbnail](/bitstream/handle/20.500.11956/183071/thumbnail.png?sequence=8&isAllowed=y)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/183071Identifiers
Study Information System: 254130
Collections
- Kvalifikační práce [10925]
Author
Advisor
Referee
Faliszewski, Piotr
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Computer Science with specialisation in Artificial Intelligence
Department
Computer Science Institute of Charles University
Date of defense
29. 6. 2023
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
English
Grade
Excellent
Keywords (Czech)
řešič|ilp|sat|úplatkyKeywords (English)
solver|ilp|presburger|logic|sat|briberyCeločí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
Integer Linear Programming (ILP) has proven to be a powerful tool for solving hard problems, particularly in computational social choice, where it has been used to address variants of the bribery problem. This problem involves finding the smallest change that results in a desired outcome after opinions diffuse through a society. The ILP solution for this problem has been shown to be experimentally limited to small instances of the problem. Research has shown that such problems can be encoded using logical formulas in Presburger Arithmetic (PrA) matching the complexity of the ILP algo- rithm. Therefore, a practical analysis of the PrA-based approach is called for. In this project, we randomly generate instances with prescribed election parameters and model them as ILP instances and PrA formulas. We use solvers such as GUROBI, GLPK, and Z3 to solve these instances and con- duct a comparative study to evaluate the performance of both approaches under different parameters, such as the number of voter types and diffusion steps. Our results show that the ILP approach is more robust than the PrA approach in practice. 1