Find an optimal allocation of groups in an array

combinatoricsdiscrete optimizationinteger programmingoptimization

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?

Best Answer

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.

Related Question