Slater Election Solving Method Based on Answer Set Programming

doi:10.3969/j.issn.1006-2475.2014.12.002

Abstract

Abstract: Slater election is an optimization problem and NP-hard problem, which is generally considered that polynomial time’s algorithms do not exist for solving. Given its complexity of solving is consistent with the complexity of answer set solving. Therefore, the paper proposes a new method of using ASP (answer set programming) to solve Slater election. First, it uses the saturation technology to build ASP model of logically equivalent for Slater election; secondly, proves the correctness of the model; finally, calls the answer set solver DLV to solve specific examples of Slater election and shows its feasibility in the experimental results. The proposed method can not only solve the Slater election problem, but also is the saturation technique used in ASP and provides a new logical representation approach for other similar optimization problem.

Key words: answer set programming (ASP), Slater election, saturation technique, solver, heuristic algorithm, optimization problem, NP-hard

CLC Number:

TP18

LAI He-lang. Slater Election Solving Method Based on Answer Set Programming[J]. Computer and Modernization, 2014, 0(12): 6-10+14.

References

[1] Chevaleyre Y, Endriss U, Lang J, et al. A short introduction to computational social choice[C]// Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science. 2007:51-69.

[2] Hudry O. On the complexity of Slater's problems[J]. European Journal of Operational Research, 2010,203(1):216-221.

[3] Slater P. Inconsistencies in a schedule of paired comparisons[J]. Biometrika, 1961,48(3-4):303-312.

[4] Lifschitz V. Answer set programming and plan generation[J]. Artificial Intelligence, 2002,138(1-2):39-54.

[5] Apt K, Bol B. Logic programming and negation: A survey[J]. Journal of Logic Programming, 1994,19-20(S1):9-71.

[6] Gelfond M, Lifschitz V. The stable model semantics for logic programming[C]// Proceedings of the 5th International Conference and Symposium on Logic Programming. 1988:1070-1080.

[7] Baral C, Gelfond M. Logic programming and knowledge representation[J]. Journal of Logic Programming, 1994,19-20(S1):73-148.

[8] Leone N, Pfeifer G, Faber W, et al. The DLV system for knowledge representation and reasoning[J]. ACM Transactions on Computational Logic, 2006,7(3):499-562.

[9] Simons P, Niemela I, Soininen T. Extending and implementing the stable model semantics[J]. Artificial Intelligence, 2002,138(1-2):181-234.

[10] Gebser M, Kaufmann B, Neumann A, et al. Conflict-driven answer set solving[C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI2007). 2007:386-392.

[11] 李鑫,李凡,边杏宾,等. E-R模型的回答集编程表示[J]. 计算机研究与发展, 2010,47(1):164-173.

[12] 赵岭忠,王雪松,钱俊彦,等. 从经典逻辑知识构建ASP知识库的新方法[J]. 计算机应用, 2010,30(11):2932-2936.

[13] 吕勇全,陈寅,邬家炜,等. 基于回答集程序的排课系统设计与实现[J]. 计算机技术与发展, 2010,20(6):228-232.

[14] 王洁,韩雪平,赵丽丽,等. ￢RDF推理中不一致问题研究[J]. 计算机工程, 2012,38(7):152-154.

[15] 张青伟,赵岭忠. 回答集程序设计在TTP求解中的应用[J]. 桂林电子科技大学学报, 2010,30(4):305-309.

[16] 王雪松,赵岭忠,张超. 基于ASP的CSP模型验证性质反例生成技术研究[J]. 计算机应用研究, 2013,30(1):52-55.

[17] Eiter T, Gottlob G, Mannila H. Disjunctive datalog[J]. ACM Transactions on Database Systems, 1997,22(3):364-418.

[18] Baral C. Knowledge Representation, Reasoning, and Declarative Problem Solving[M]. Cambridge University Press, 2003.

[19] Erdem E, Lifschitz V. Tight logic programs[J]. Theory and Practice of Logic Programming, 2003,3(4-5):499-518.