A note on a symmetrical set covering problem: The lottery problem |
| |
| Authors: | Raf Jans Zeger Degraeve |
| |
| Affiliation: | 1. RSM Erasmus University, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands;2. London Business School, Regent’s Park, London NW1 4SA, UK |
| |
| Abstract: | 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. |
| |
| Keywords: | Integer programming Lottery problem Set covering problem Symmetry |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
