Find an optimal allocation of groups in an array

Question

Say we have an $n\times m$ array with $n$ and $m$ are odd, and a list of positive integers $(a_1,\dots, a_k)$. Each $a_i$ represents a number of elements which are to be allocated together in a row of the array. Each slot of the array has a value

$1+$rows from the middle row$+$columns to the middle column

so that the central slot has value $1$ and it increases by $1$ every time we move one row or column farther from it. I would like to find the allocation that minimizes the sum of values of slots in which there is an allocated element with the restrictions that each group must be allocated together in the same row, and that two groups in the same row must be separated by an empty slot.

For instance, given a $3\times 3$ array and the integers $(1,2,3)$ an optimal allocation would look like

$$ \begin{array}{|c|c|c|} \hline & 1 & \\ \hline 3 & 3 & 3\\ \hline 2 & 2 & \\ \hline \end{array} $$

where the number corresponds to the integer in the list.

In this case, the total value is computed as

$$ \begin{array}{|c|c|c|} \hline & 2+ & \\ \hline 2+ & 1+ & 2+\\ \hline 3+ & 2+ & \\ \hline \end{array}=12 $$

A case in which I need to put two groups in the same row would be for instance

$$ \begin{array}{|c|c|c|c|} \hline 4& 4 &4& 4& \\ \hline 5 & 5 & 5&5&5\\ \hline & 2 & 2 & &1 \\ \hline \end{array} $$

My thoughts

I think this problem can be modelled as an integer programming problem. The main difficulty that I find is that the allocation occurs in groups (the elements corresponding to an integer in the list must be allocated together) but the values are individual, so I am unsure what variables to use. For instance, I could define $x_{ij}$ to be the value of the $(i,j)$ slot of the array and $y_{ij}=1$ if there is an element in $(i,j)$ ($0$ otherwise). But then I would have to somehow take into acoung the groups. I could introduce some variable $z_{ijk}$ telling whether the group $i$ (corresponding to $a_i$) is allocated in the row $j$ starting at column $k$. However, I haven't been able to work out the constraints.

Another strategy that I have thought of is to find a heuristics to obtain some optimal allocation. I think the biggest groups should be allocated centered in the middle rows, and then if there is space left for some smaller groups on the sides, then we can allocate them there. However, I am not completely sure that this strategy works.

Can someone give me any ideas on how to approach this problem?

Answer 1

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.

Answer 2

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.