Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems
| Název práce v češtině: | Porovnání výkonu ILP řešičů a logických řešičů na problému úplatků |
|---|---|
| Název v anglickém jazyce: | Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems |
| Klíčová slova: | řešič|ilp|sat|úplatky |
| Klíčová slova anglicky: | solver|ilp|presburger|logic|sat|bribery |
| Akademický rok vypsání: | 2022/2023 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | Mgr. Martin Koutecký, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.11.2022 |
| Datum zadání: | 11.11.2022 |
| Datum potvrzení stud. oddělením: | 28.02.2023 |
| Datum a čas obhajoby: | 29.06.2023 09:00 |
| Datum odevzdání elektronické podoby: | 10.05.2023 |
| Datum odevzdání tištěné podoby: | 15.05.2023 |
| Datum proběhlé obhajoby: | 29.06.2023 |
| Oponenti: | Dr. Piotr Faliszewski |
| Zásady pro vypracování |
| In theory, the tractability of certain variants of Integer Linear Programming (ILP) has been used repeatedly to show the tractability of various problems in computational social choice, mainly variants of the Bribery problem. In Bribery, we are given a description of a society, and the task is to compute the smallest change which results in some desired outcome. The problem can be made more realistic but complex by introducing a notion of opinion diffusion, i.e., the task is to compute the smallest change such that, after an opinion diffusion process has stabilized, the desired outcome occurs. Falisezwski et al. [IJCAI 2018] have shown that this problem can be solved using ILP, and Koutecký and Talmon [AAAI 2021] have shown that this and other problems can also be solved using logical methods.
It is natural to ask which approach is better in practice, and whether any of them is practical at all, since the constants hidden in the theoretically efficient algorithms are astronomical. The task of the student is to compare the performance of the two approaches on the “Bribery with Opinion Difusion” problem. This involves generating random instances with prescribed parameters, modeling each instance as an ILP or as a Presburger Arithmetic (PrA) formula, and solving these models using solvers such as Gurobi, GLPK, z3, and others. Finally, we are interested how various paameters correlate with performance, e.g. the number of voter types, the number of voters, the number of diffusion steps, etc. |
| Seznam odborné literatury |
| Piotr Faliszewski, Rica Gonen, Martin Koutecký, Nimrod Talmon:
Opinion Diffusion and Campaigning on Society Graphs. IJCAI 2018: 219-225 Martin Koutecký, Nimrod Talmon: Multi-Party Campaigning. AAAI 2021: 5506-5513 |