An Improvement of Lotto-Meta Heuristic for Solving a Lottery Problem

Article Sidebar

Image cover page Journal of Science Ladkrabang, Vol. 29 No. 2, July-December 2020
PDF (ภาษาไทย)
Published: Dec 24, 2020
Keywords:
Integer programming Set covering problem Lottery problem Heuristic

Main Article Content

Kasitinart Sangngern
Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University
Aua-aree Boonperm
Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University

Abstract

In a lottery problem, k numbers are drawn from a set of n numbers. On a ticket we fill out k numbers and the winning ticket fill out p numbers from a set of n numbers. The objective function is the minimum number of tickets so that there are at least t matching numbers. This problem can be solved by formulating the integer programming model. However, solving this problem by exact method takes more time to solve it. So, in this paper, we propose an improvement of Lotto-Meta heuristic that is a heuristic algorithm for solving a lottery problem. From the computational result of the small instances of the lottery problem, we found that our method gave the number of tickets less than or equal to the number of tickets obtained by the original Lotto-Meta heuristic.

Article Details

How to Cite
Sangngern, K., & Boonperm, A.- aree. (2020). An Improvement of Lotto-Meta Heuristic for Solving a Lottery Problem. Journal of Science Ladkrabang, 29(2), 59–71. Retrieved from https://li01.tci-thaijo.org/index.php/science_kmitl/article/view/236594
Issue
Vol. 29 No. 2 (2020): July - December 2020
Section
Research article

References

Burger, A., Gründlingh, W.R. and Vuuren, Jan. 2003. The lottery problem. Available at: https://www.researchgate.net/publication/228998461_The_lottery_problem. Retrieved December 2, 2019.

Jans, R. 1997. Analysis of a symmetrical set covering problem: The lottery problem. Master’s Thesis, Department of Applied Economics, K.U. Leuven, Belgium.

Li, P.C. and ven Rees, G.H.J. 2000. New constructions of lotto designs. Utilitas Mathematica, 58, 45-64.

Beasley, J.E. and Chu, P.C. 1996. A genetic algorithm for the set covering problem. European Journal of Operation Research, 94, 392-404.

Lan, G., Depuy, G.W. and Whitehouse, G.E. 2007. An effective and simple heuristic for the set covering problem. European Journal of Operation Research, 176, 1387-1403.

Aickelin, U. 2002. An indirect genetic algorithm for set covering problems. Journal of the Operation Research Society, 53, 1118-1126.

Bautisa, J. and Pereira, J. 2007. A GRASP algorithm to solve the unicost set covering problem, Computer & Operations Research, 34, 3162-3173.

Li, P.C. and van Rees, G.H.J. 2002. Lotto design tables. Journal of Combinatorial Designs, 10, 335-359.

Li, P.C. 1999. Some results on lotto design. Ph.D. Thesis, University of Manitoba.

Li, P.C. and van Rees, G.H.J. 1999. Lower bounds on lotto designs. Congressus Numerantium, 141, 5-30.

Jans, R. and Degrave, Z. 2008. A note on a symmetrical set covering problem: the lottery problem. European Journal of Operational Research, 186, 104-110.

Mohammadi, A. 2012. Heuristic algorithm for solving the integer programming of the lottery problem. Scientia Iranica. 19. 895-901.