Find an optimal allocation of groups in an array

I recommend using only the $z_{ijk}$ variables. The constraints are then \begin{align} \sum_{j,k} z_{ijk} &=1 &&\text{for all groups $i$} \\ z_{i_1 j k_2} + z_{i_2 j k_2} &\le 1 &&\text{for all conflicting pairs $(i_1,k_1),(i_2,k_2)$ and rows $j$} \end{align} Alternatively, you can strengthen the formulation by replacing the conflict constraints with a clique constraint $$\sum z_{ijk} \le 1$$ for each cell, where the sum is over triples that occupy (including the terminating cell) the given cell.

In either case, the objective function to be minimized is $$\sum_{i,j,k} c_{i,j,k} z_{i,j,k},$$ where $c_{i,j,k}$ is the sum of scores of cells $(j,k)$ through $(j,k+a_i-1)$.

Here is SAS code for both versions, with the Conflict constraint commented out. I used $g$ for group and $(i,j)$ for cell.

%let numRows = 3;
%let numCols = 5;
data GroupData;
   input a @@;
   datalines;
1 2 4 5
;

proc optmodel;
   num numRows = &numRows;
   num numCols = &numCols;
   set ROWS = 1..numRows;
   set COLS = 1..numCols;
   set CELLS = ROWS cross COLS;
   num score {<i,j> in CELLS} = 1 + abs(i-(numRows+1)/2) + abs(j-(numCols+1)/2);
   print score;

   set GROUPS;
   num a {GROUPS};
   read data GroupData into GROUPS=[_N_] a;

   set STARTS_g {g in GROUPS} = {<i,j> in CELLS: j+a[g]-1 <= numCols};
   set CELLS_gij {g in GROUPS, <i,j> in STARTS_g[g]} = {i} cross j..j+a[g]-1;

   var Z {g in GROUPS, STARTS_g[g]} binary;

   min Objective = sum {g in GROUPS, <i,j> in STARTS_g[g], <ii,jj> in CELLS_gij[g,i,j]} score[ii,jj] * Z[g,i,j];

   con OneCellPerGroup {g in GROUPS}:
      sum {<i,j> in STARTS_g[g]} Z[g,i,j] = 1;

/* con Conflict {g1 in GROUPS, <i1,j1> in STARTS_g[g1], g2 in GROUPS diff {g1}, <(i1),j2> in STARTS_g[g2]: j1 <= j2 and j1 + a[g1] >= j2}:
          Z[g1,i1,j1] + Z[g2,i1,j2] <= 1; */
   con Clique {<i,j> in CELLS}:
      sum {g in GROUPS, <ii,jj> in STARTS_g[g]: <i,j> in CELLS_gij[g,ii,jj] union {<ii,jj+a[g]>}} Z[g,ii,jj] <= 1;

   solve;

   num sol {CELLS} init .;
   for {g in GROUPS} do;
      for {<i,j> in STARTS_g[g]: Z[g,i,j].sol > 0.5} do;
         for {<(i),jj> in CELLS_gij[g,i,j]} sol[i,jj] = a[g];
         leave;
      end;
   end;
   print sol;
quit;

There are 36 decision variables. The Conflict formulation has 166 constraints and 360 constraint coefficients. The Clique formulation has 19 constraints and 138 constraint coefficients. Your solution, with objective value 32, is optimal.

The following is an integer linear programming formulation of the problem.

For any $i \in \{1, 2, \dots, k\}$, we define the variables $r_i$ and $c_i$ such that the slots for group $i$ are at row $r_i$, starting from column $c_i$ to column $c_i + a_i - 1$.

It is straightforward to define the objective function of the ILP using the variables $r_1, c_1, r_2, c_2, \dots, r_k, c_k$. As for the constraints, we can also easily find the constraints to limit the group within the $n \times m$ array: \begin{align*} 1 \leq r_i &\leq n,\\ 1 \leq c_i &\leq m + 1 - a_i. \end{align*}

We also have the "separation" restriction: if group $i$ and group $j$ are in the same row, then must be separated by a slot (and cannot overlap). The relevant constraints would be \begin{align*} c_i - c_j + 2m|r_i - r_j| &\geq a_j + 1,\\ c_j - c_i + 2m|r_i - r_j| &\geq a_i + 1. \end{align*} To see why these constraints work, consider the following cases:

• Suppose the two groups are in different rows. Then $|r_i - r_j| \geq 1$. In this case, the first constraint always hold for any $c_i$ and $c_j$, because $$c_i - c_j + 2m|r_i - r_j| \geq 1 - m + 2m\cdot 1 = m + 1 \geq a_j + 1.$$ (The first inequality also uses the fact $c_i, c_j \in [1, m]$, while the last inequality assumes that $a_j \leq m$, i.e., a group cannot take more slots than the number of columns in the array.) The same conclusion also applies for the second constraint.

• Suppose the two groups are in the same row. Then $|r_i - r_j| = 0$. So, the constraints can be simplified to \begin{align*} c_i - c_j &\geq a_j + 1,\\ c_j - c_i &\geq a_i + 1. \end{align*} It is easy to see that the two constraints above are satisfied iff the two groups satisfy the "separation" restriction.

The absolute values in the constraints can be removed, e.g. with this method.