2
$\begingroup$

Here are all the 369 octominoes: https://en.wikipedia.org/wiki/Octomino

If I have an 8x8 area, how to create one octomino, any of those 369 and any rotation and mirroring is allowed?

I have tried several linearized and/or tricks but those produced sometimes correct sometimes wrong solutions. How to make constraints so the eight binary ones are always connected?

$\endgroup$

1 Answer 1

6
$\begingroup$

You want to model a connected subgraph, with $8$ nodes, of an $8 \times 8$ grid graph. Let binary decision variable $x_{ij}$ indicate whether undirected edge $\{i,j\}\in E$ is selected. Let binary decision variable $y_i$ indicate whether node $i$ is selected. Let binary decision variable $s_i$ indicate whether node $i$ is selected as the source node. Let nonnegative decision variable $f_{ij}$ be the flow across directed arc $(i,j)\in A$. The idea is to enforce connectivity by sending one unit of flow from the source to each other selected node. The constraints are: \begin{align} \sum_i y_i &= 8 \tag1\label1 \\ x_{ij} &\le y_i &&\text{for all $\{i,j\}\in E$} \tag2\label2 \\ x_{ij} &\le y_j &&\text{for all $\{i,j\}\in E$} \tag3\label3 \\ x_{ij} &\ge y_i + y_j - 1 &&\text{for all $\{i,j\}\in E$} \tag4\label4 \\ \sum_i s_i &= 1 \tag5\label5 \\ s_i &\le y_i && \text{for all $i$} \tag6\label6 \\ f_{ij} + f_{ji} &\le 7 x_{ij} && \text{for all $\{i,j\}\in E$} \tag7\label7 \\ \sum_{(i,j) \in A} f_{ij} - \sum_{(j,i)\in A} f_{ji} &= 8 s_i - y_i &&\text{for all $i$} \tag8\label8 \end{align} Constraint \eqref{1} selects $8$ nodes. Constraints \eqref{2} through \eqref{4} link the node variables to the edge variables. Constraint \eqref{5} selects one source node. Constraint \eqref{6} forces the source node to be a selected node. Constraint \eqref{7} allows flow only on selected edges. Constraint \eqref{8} enforces flow balance.

Because a connected graph must have at most one more node than the number of edges, an optional constraint is $$\sum_{\{i,j\}\in E} x_{ij} \ge 7.$$

Note that you can relax $x$ to be nonnegative because it will automatically take values in $\{0,1\}$ if $y$ does.

$\endgroup$
3
  • $\begingroup$ Thank You. Could You or someone else comment how many x and f variables will be? I understand there is 64 y and s variables. $\endgroup$
    – user9050
    Aug 5, 2023 at 16:30
  • $\begingroup$ $|E|=8\times7\times2$ and $|A|=2|E|$ $\endgroup$
    – RobPratt
    Aug 5, 2023 at 19:34
  • $\begingroup$ Great answer! Did you use similar formulation in the greenhouse problem? And do you think this formulation has any connection with MTZ formulation? $\endgroup$
    – xd y
    Aug 7, 2023 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.