Formulación de programación entera de Takuzu

Question

A Takuzu es un rompecabezas numérico basado en la lógica cuyo objetivo es rellenar un (normalmente $10 \times 10$ ) con unos y ceros tales que se cumplan las siguientes condiciones:

1. Cada fila y cada columna tienen el mismo número de unos y ceros.

2. Cada fila y cada columna tienen un máximo de $2$ números adyacentes iguales.

3. Todas las filas son diferentes y todas las columnas son diferentes (pero una fila puede ser igual que una columna).

Estoy interesado en un programación entera (PI) para resolver dicho rompecabezas. Denotemos $A$ como el $2n \times 2n$ que representa la cuadrícula de dicho puzzle (supongamos una cuadrícula cuadrada) y que $\mathcal{N} = \{1,\ldots,2n\}$ . La formulación IP viene dada entonces por

\begin{align} \min 1 \\ \text{s.t.} \quad \sum_{j \in \mathcal{N}}a_{ij} & = n \quad \forall \ i \in \mathcal{N} \tag{1.1} \\ \sum_{i \in \mathcal{N}}a_{ij} & = n \quad \forall \ j \in \mathcal{N} \tag{1.2} \\ \sum_{j \in \mathcal{N}} |a_{ij}-a_{kj}| & \geq 1 \quad \forall \ i \in \mathcal{N}, \forall \ k \in \mathcal{N}, i \neq k \tag{3.1} \\ \sum_{i \in \mathcal{N}} |a_{ij}-a_{ik}| & \geq 1 \quad \forall \ j \in \mathcal{N}, \forall \ k \in \mathcal{N}, j \neq k \tag{3.2} \\ a_{ij} & \in \mathbb{B} \quad \forall \ i \in \mathcal{N}, \forall \ j \in \mathcal{N} \end{align}

Tengo dos preguntas principales:

1 : ¿Es válida la formulación? ¿Algún consejo sobre notación o solvencia?

2 : ¿Cómo hago cumplir la 2ª condición en mi programa?

Answer 1

La codificación de su segunda restricción puede hacerse para filas con :

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N} \setminus \{1,2 n\}, 1 \leq a_{i,j-1} + a_{i,j} + a_{i,j+1} \leq 2$

El resto de su formulación es válida.

Lo que tengo que decirte entonces no te hará feliz: resolver esto por rama y rama será un asco. Tienes una enorme simetría en esta formulación de programación entera, y esto es muy malo. Usted probablemente tendrá algunos resultados con un buen solucionador, pero para un mayor $n$ Creo que la programación con restricciones funcionaría mejor.

Siguiente comentario : aquí hay una forma de linealizar $(3.1)$ (sin utilizar la función objetivo) :

defina $\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k}$ el booleano igual a $|a_{i,j}-a_{k,j}|$ . Para que $b$ esté correctamente definida, puede añadir las restricciones

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \leq a_{i,j} + a_{k,j} $

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \leq 2 - (a_{i,j} + a_{k,j}) $

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \geq a_{i,j} - a_{k,j} $

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \geq a_{k,j} - a_{i,j} $

A continuación, exprese $(3.1)$ :

$\forall i \in \mathcal{N}, \forall k \in \mathcal{N}, \sum_{j \in \mathcal{N}} b_{i,j,k} \geq 1 $