Porovnání výkonu ILP řešičů a logických řešičů na problému úplatků

Kumar, Aryan

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

guest :: login Digital Repository
		Search		Submit		Help		About