A note on a symmetrical set covering problem: The lottery problem
European Journal of Operational Research , Volume 186 - Issue 1 p. 104- 110
In a lottery, n numbers are drawn from a set of m numbers. On a lottery ticket we fill out n numbers. Consider the following problem: what is the minimum number of tickets so that there is at least one ticket with at least p matching numbers? We provide a set-covering formulation for this problem and characterize its LP solution. The existence of many symmetrical alternative solutions, makes this a very difficult problem to solve, as our computational results indicate.
|integer programming, lottery problem, set covering problem, symmetry|
|ERIM Top-Core Articles|
|European Journal of Operational Research|
|Organisation||Erasmus Research Institute of Management|
Jans, R.F, & Degraeve, Z. (2008). A note on a symmetrical set covering problem: The lottery problem. European Journal of Operational Research, 186(1), 104–110. doi:10.1016/j.ejor.2007.01.039