How to arrange the colored cells in game grid?

Question

Puzzle: In a game grid some cells are missing. Each line has only one colored cell with a label (a number greater than zero). This is an example grid and the number of columns/rows can be less than the colored cell:

All numbers in the grid are for example.

A player can only move a colored cell in a horizontal direction. When all cells of the same color are placed in one column a reduction factor is applied to the numerical labels, and (vice versa) if such a position is violated the initial label values ​​are restored. The factor is different for each color.

The player's task is to arrange the colored cells so that the sum of all labels is minimal. In the final solution the sum of labels in one column for cells of different colors cannot exceed a certain value. This value can be different for each column.

I have a practical application of the task above and I want to formulate a puzzle for the first time. I am looking for some similar tasks, because for now I can't formulate an optimization task.

Edit I have read the paper Connected bin packing problem on traceable graphs and looking for a graph approach.

Some very interesting procedures for the bin packing problem with precedence constraints are discussed in the paper.

Question: Is it possible to find the optimal solution to the proposed puzzle?

Answer 1

You can solve the problem via mixed integer linear programming as follows.

Let $I$ be the set of rows, $J$ the set of columns, and $C$ the set of colors. For $c\in C$, let $J_c \subseteq J$ be the set of columns that can contain color $c$. For $i\in I$, let $c_i$ and $\ell_i$ be the color and initial label, respectively, for row $i$. For $c\in C$, let $f_c$ be the reduction factor for color $c$. For $j\in J$, let $u_j$ be the upper bound for the sum of final values in column $j$.

For $i\in I$ and $j\in J$, let binary decision variable $x_{i,j}$ indicate whether cell $(i,j)$ is occupied. (To avoid the missing cells, either fix $x_{i,j}=0$ for those cells or use a sparse index set for non-missing cells $(i,j)$.) For $c \in C$ and $j\in J_c$, let binary decision variable $y_{c,j}$ indicate whether all labels for color $c$ appear in column $j$. For $i\in I$ and $j\in J$, let continuous decision variable $z_{i,j}$ be the final value ($0$ if unoccupied) in cell $(i,j)$.

The problem is to minimize $$\sum_{i \in I} \sum_{j\in J} z_{i,j}$$ subject to \begin{align} \sum_{j \in J} x_{i,j} &= 1 && \text{for $i \in I$} \tag1 \\ y_{c,j} &\le x_{i,j} && \text{for $c \in C, j \in J_c, i \in I: c_i = c$} \tag2 \\ z_{i,j} &= \ell_i (x_{i,j} - (1 - f_{c_i}) y_{c_i,j}) && \text{for $i\in I, j \in J$} \tag3 \\ \sum_{i \in I} z_{i,j} &\le u_j && \text{for $j \in J$} \tag4 \end{align} Constraint $(1)$ selects exactly one column for the label in each row. Constraint $(2)$ forces all labels with color $c$ to be in column $j$ if $y_{c,j}=1$. Constraint $(3)$ determines the final value of cell $(i,j)$ based on $x$ and $y$. Constraint $(4)$ enforces the upper bound on column $j$.