A (two-dimensional) pyramid is constructed in four layers: The bottom layer consists of (equally spaced) dots 1, 2, 3, and 4; the next layer includes dots 5, 6, and 7; the following layer has dots 8 and 9; and the top layer has dot 10. You want to invert the pyramid (i.e., bottom layer has one dot and top layer has four) by moving the dots around.
Determine the smallest number of moves needed to invert the pyramid.
in order to arrive at the optimum solution to this problem, I found the solution using the hit and trial method, as attached in the figure. Is there any mathematical model to arrive at the optimal answer to this question? How do I think about forming the math model for this problem on my own?
Basically you define a $5 \times 4 $ matrix with nodes $V =\{1,2,...10 \} $ with initial parameters $a_{i,j} = v $ like $a_{4,1} = 1, a_{4, 3} = 2,...a_{1,4}= 10$
To reduce number of variables being created you can name these $(i,j)$ as $k$ like $1,1$ as $1$.
$k$ should have $\{1,2,...21 \}$ possible values for inversion.
When inverting you count as additional point where node $10$ is placed in inverted pyramid
Define binary variables $x_{v,k} $ and another continuous $u_{v,k}^+, u_{v,k}^- $ and binary $y_{v,k}$.
Constraints:
(1) $\sum_v x_{v,k}^v = 1 \ \ \forall k \in $ Inverted Pyramid
For inversion points $k$ where $a_k=0$ will now have a value or a node (1,2,3...). Define these in set inverted pyramid and loop constr (1) only for those points. Some points will remain as before.
If you are using modern solver like Gurobi you can use absConstraint to do
If $\vert a_{k}- vx_{v,k}\vert \gt 0 $ then $y_{v,k} =1$, else $0$. This is needed to count the change in position for a node
Otherwise you have to do gymnastics to linearize abs constraints
(2) $a_{k}- vx_{k}^v = u_{v,k}^+ - u_{v,k}^- \ \ \forall k \ \ \forall v$
(3) $y_{v,k} \le u_{v,k}^+ + u_{v,k}^- \le My_{v,k}$
where $M = 21$
(4) $ 0 \le u_{v,k}^+, u_{v,k}^-$
Since $y_v$ counts the move, $ \min \sum_{v,k}y_{v,k}$