Placing number blocks so that the resulting matrix is symmetric

Question

There are some number blocks given as follows:

The aim is placing these blocks in such a way that the resulting 4X4 matrix is symmetrical. Blocks cannot be rotated, they must be used as given.

My question is, can this somehow be solved by linear programming? If yes, how should I model it?

For a more complicated version, here is a similar question, this time for 5X5 matrix:

Answer 1

I don't think you can use a linear programming model, but you can solve it with integer programming. (You can also solve it using constraint programming.)

I will use $N$ for the dimension of the square matrix (4 or 5 in your examples), $K$ for the number of blocks (6 in the first example, 11 in the second) and $m_i$ and $n_i$ for the row and column dimensions of block $i.$ (In your example, one of the dimensions of each block is 1, but we do not need to require that.) I'm going to use a coordinate system that puts the upper left cell of the matrix at $(1, 1)$ and the lower right cell at $(N, N).$ Finally, I will use $B^b$ to denote the $m_b \times n_b$ block $b.$

The integer programming model I tested uses two sets of variables. $x_{b,r,c}$ is a binary variable taking value 1 if block $b$ has its upper left corner in cell $(r, c)$ and 0 if not. $y_{r,c}$ is a continuous variable (which will end up being integer valued in your sample matrices) containing the value that ends up in cell $(r, c)$ of the assembled matrix.

I'll need two sets of predefined constants. $\alpha_{b, r, c, i, j}$ will be 1 if putting the upper left corner of block $b$ at position $(r, c)$ means that it covers cell $(i, j)$ and 0 if not. $\beta_{b, r, c, i, j}$ will be $B^b_{i-r + 1, j-c + 1}$ if putting block $b$ at $(r, c)$ covers $(i, j)$ (i.e., if $\alpha_{b, r, c, i, j} = 1$) and 0 if not. If block $b$ at $(r, c)$ covers $(i, j),$ $\beta_{b, r, c, i, j}$ will be the entry in cell $(i, j)$ of the final matrix.

On to the constraints.

• First up, we set $x_{b,r,c}=0$ if block $b$ will not fit with upper corner at $(r, c)$ (meaning $r + m_b - 1 > N$ or $c + n_b - 1 > N$).
• Next, we need to place each block exactly once: $$\sum_r \sum_c x_{b,r,c} = 1\quad \forall b.$$
• Every cell in the matrix should be covered by exactly one block: $$\sum_b \sum_r \sum_c \alpha_{b,r,c,i,j}x_{b,r,c} = 1 \quad \forall i,j\in \lbrace 1,\dots,N\rbrace.$$
• We need to define the $y$ variables: $$y_{i,j} = \sum_b \sum_r \sum_c \beta_{b,r,c,i,j}x_{b,r,c} \quad \forall i,j\in \lbrace 1,\dots,N\rbrace.$$
• Finally, we want the matrix to be symmetric: $$y_{i,j} = y_{j,i} \quad \forall i < j\in \lbrace 1,\dots,N\rbrace.$$

Answer 2

It's basically constrained programming.
If you want to go by blocks which I missed previously then:
Define blocks $B$ as a set of sets like $ B=\{b1,b2,..\}$ and numbers on blocks can be accessed as $ B_{b,i}$. Like example predefine $B_{1,1} = 7$ implying $7$ at first row of first block and the next $7$ as $B_{2,1}$ meaning its at row $1$, 2nd block.
To make it dynamic define a set C over blocks $b$ where $ C^b = 1$ if its vertically aligned, $0$ otherwise and $I^b$ is a $b$ indexed list of maximum number of figures like $2,3$ or $4$.

Pre-define a set, $S$ or a variable (if member of this set) of non-duplicating numbers like $ S = \{(1,2),(2,3)..\}$ where again the first element is the block $b$ and second the position/index. You can define a parameter like if $ S_{1,2} =1$ if the number at index $ 2$ of block $1$ is non-duplicated, $0$ otherwise.

Define binary variables $ y_{i,j}^b$ with $ i,j$ as matrix positions and variables $a_{i,j}$.

$ \sum_b y_{i,j}^b = 1 \quad \forall i,j$

$ C^b(I^b y_{i-1,j}^b + \sum_{k=1}^{i-2}y_{k,j}^b) \le I^b y_{i,j}^b \quad \forall b, j$: basically vertical orientation ensuring unless exhausted all rows are assigned to same block in a column

$ (1-C^b)(I^b y_{i,j-1}^b + \sum_{k=1}^{j-2}y_{i,k}^b)) \le I^b y_{i,j}^b \quad \forall b, i$

$ a_{i,j} = \sum_b \sum_{i}^{I_b}y_{i,j}^{b}\cdot B_{b,i} \quad \forall i,j$

Symmetry
$ a_{i,j} = a_{j,i}$

Diagonal:
$ a_{i,i} = \sum_b \sum_{i}^{I_b}y_{i,j}^b\cdot B_{b,i}\cdot S_{{b,i}}$