1

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?

optimal moves 3

Akansha Banerjee
  • 31
  • 5
  • A word to describe the position of your dots : they are placed according to a rhombic pattern. – Jean Marie Jun 24 '23 at 07:07
  • Draw the normal pyramid on paper, and the inverted pyramid on a transparent overlay. You can then translate the inverted pyramid around (move it horizontally and vertically), thus modifying the amount of dots the two pyramids will have in common. The minimum number of required moves is (10 - the number of common dots), and you can prove exhaustively that the number of common dots cannot be greater than 7. The 7 common dots happen when the two pyramids have the same center dot. – user3257842 Jun 25 '23 at 12:58

1 Answers1

0

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}$

Sutanu Majumdar
  • 458