! Lottery ticket covering problem. Which combination of tickets should
we buy so we win, regardless of the outcome. Cast in the form of
betting on the outcome of a number of futbol games.
Ref: Linderoth, J., F. Margot, ang G. Thain(2009),
"Improving Bounds on the Football Pool Problem by
Integer Programming and High-Throughput Computing",
INFORMS Journal of Computing, vol. 21, no. 3, pp. 445-457;
SETS:
OUTK1;
OUTK2;
OUTK3;
OUTK4;
OUTK5;
OUTK6;
COMBO( OUTK1,OUTK2,OUTK3,OUTK4,OUTK5,OUTK6): Y;
ENDSETS DATA:
OUTK1 = WIN LOSE DRAW;
OUTK2 = WIN LOSE DRAW;
OUTK3 = WIN LOSE DRAW;
OUTK4 = WIN LOSE DRAW;
OUTK5 = WIN LOSE DRAW;
OUTK6 = WIN ;!LOSE DRAW;
ENDDATA
! Known results:
# Games Tickets must buy
1 1
2 3
3 5
4 9
5 27
6 71<= t <= 73
;
! Y(i1, i2, i3, i4, i5, i6) = 1 if we buy a ticket that bets
on outcome (i1, i2, i3, i4, i5, i6);
MIN = @SUM( COMBO(i1, i2, i3, i4, i5, i6): Y(i1, i2, i3, i4, i5, i6));
! Make them binary;
! @FOR( COMBO(i1, i2, i3, i4, i5, i6): @BIN(Y(i1, i2, i3, i4, i5, i6)));
! For each game and each outcome, at least one of our choices
must be close enough. We are close enough if we got only one wrong;
@FOR( COMBO( i1, i2, i3, i4, i5, i6):
Y( i1, i2, i3, i4, i5, i6) ! Get all right;
! or get exactly 1 outcome wrong ;
+@SUM( COMBO(k1, i2, i3, i4, i5, i6) | k1 #NE# i1 : Y(k1, i2, i3, i4, i5, i6))
+@SUM( COMBO(i1, k2, i3, i4, i5, i6) | k2 #NE# i2 : Y(i1, k2, i3, i4, i5, i6))
+@SUM( COMBO(i1, i2, k3, i4, i5, i6) | k3 #NE# i3 : Y(i1, i2, k3, i4, i5, i6))
+@SUM( COMBO(i1, i2, i3, k4, i5, i6) | k4 #NE# i4 : Y(i1, i2, i3, k4, i5, i6))
+@SUM( COMBO(i1, i2, i3, i4, k5, i6) | k5 #NE# i5 : Y(i1, i2, i3, i4, k5, i6))
>= 1;
);
! Kill some symmetry;
Y(1, 1, 1, 1, 1, 1) = 1;
|