3

I'm taking a class in linear programming and the project involves modelling a Rummikub game. I have made the simplifying assumptions (for now) that there is no joker and only one piece of each number/colour combination. So far what I have is:

Parametres:

  1. NB_NUM = number of numbers (normally 12)
  2. NB_COUL = number of colours (normally 4)
  3. cost[NB_NUM] = cost of each number (normally the number itself)
  4. table[NB_NUM, NB_COUL] = binary variable that tells whether the piece numbered i and coloured j is on the table before a round
  5. hand[NB_NUM, NB_COUL] = same thing, for the hand

Variables:

  1. x[NB_NUM, NB_COUL] = binary variable that tells whether the piece numbered i and coloured j is in the hand after the round
  2. y[NB_NUM, NB_COUL] = same thing, for the table
  3. gr[NB_NUM, NB_COUL] = tells whether the piece numbered i and coloured j is part of a group
  4. run[NB_NUM, NB_COUL] = same thing but for a run

Objective function: minimise $z = \sum\limits_{i, j}x[i, j]*cost[i]$

Constraints:

  1. $\forall i, j: x[i, j] + y[i, j] = table[i, j] + hand[i, j]$ (the number of pieces mustn't change)
  2. $\forall i, j:y[i, j] \geq table[i, j]$ (no piece can leave the table)
  3. $\forall i, j: x[i, j] + y[i, j] \leq 1$ (no piece is simultaneously on the table and in the hand)
  4. $\forall i, j: gr[i, j] + run[i, j] = y[i, j]$ (a piece on the table is always in a group or in a run)
  5. $\forall i, l:\sum\limits_jgr[i, j] \geq 3*gr[i, l]$ (if a group exists, it has at least 3 pieces)
  6. $\forall l, j : \sum\limits_{i = l}^{l+2}run[i, j]\geq 3*run[l+2,j]$ (if a run exists, it has at least 3 pieces)

I wrote this in my AMPL program and chose the initial condition of an empty table and the pieces [1 2] [2 2] [3 1] [3 2] [4 1] [4 3] [4 4] [5 1] [6 1] in the hand. As is easy to see, the optimal (in the sense of minimising the hand's cost) strategy is choosing to put the runs [1 2] [2 2] [3 2] and [3 1] [4 1] [5 1] [6 1] on the table and keeping the pieces [4 3] [4 4] for a hand worth 8 points. In this case, we'd have the following variables as nonzero:

  1. x[4, 3]
  2. x[4, 4]
  3. y[1, 2] and run[1, 2]
  4. y[2, 2] and run[2, 2]
  5. y[3, 2] and run[3, 2]
  6. y[3, 1] and run[3, 1]
  7. y[4, 1] and run[4, 1]
  8. y[5, 1] and run[5, 1]
  9. y[6, 1] and run[6, 1]

As is easy to check, this respects every constraint. However, when I run this, AMPL chooses instead to put the first run and the group [4 1] [4 3] [4 4] on the table and keep the pieces [3 1] [5 1] [6 1] in the hand for an objective value of 14.

So... what gives? (I'm using cplexamp by the way.)

Red
  • 950

1 Answers1

0

Constraint 6 rules out any run that doesn't start with 1. Consider a table with a green run containing 3, 4, and 5. Take l = 1, j = green, then we require run[1, green] + run[2, green] + run[3, green] >= 3 * run[3, green], but that's 0 + 0 + 1 >= 3 * 1, which fails, so this table is invalid even though it shouldn't be.

Shea Levy
  • 116