Hay tres caminos clásicos hacia Eternity II. El backtracking recorre el árbol.
Los codificaciones SAT y CSP entregan
la lógica a un solucionador industrial. El tercer camino pertenece a los
optimizadores: escribir el puzzle como un programa entero (variables,
restricciones lineales, un objetivo) y llamar a CPLEX. Es el camino que toda
persona de investigación operativa prueba primero, porque viene con una jugada
que los otros dos no tienen: la relajación. Elimina el requisito de que las
variables sean números enteros y el programa entero, NP-difícil, se convierte en
un programa lineal, resoluble en tiempo polinómico. Resuelve la versión fácil,
confía en que la respuesta sea casi entera, repara el resto.
La comunidad recorrió este camino una y otra vez entre 2007 y 2025, con
solucionadores que iban desde glpsol hasta CPLEX pasando por Newton–Raphson
hechos a mano, y el resultado se midió con precisión suficiente para merecer una
página: la relajación se resuelve rápido y reporta un tablero casi perfecto,
hecho de fracciones de piezas. Fuerza las piezas a ser enteras y la puntuación
se desploma sobre una meseta en torno a 420–440 de 480 aristas. La brecha entre
el óptimo fraccionario y el entero no es un tecnicismo. Es exactamente el lugar
donde vive el puzzle.
Una variable binaria por colocación, exactamente como en la codificación SAT:
sea xc,p,r∈{0,1} el significado «la pieza p ocupa la celda c con
rotación r». Dos familias de restricciones de asignación y una contabilidad
por costura dan el modelo completo:
maxs.t.s∑ysp,r∑xc,p,r=1c,r∑xc,p,r=1ys≤k∑min(fs,k1,fs,k2)(matched seams)∀cell c∀piece p∀seam s
donde fs,ki es el flujo de color, el peso total de las colocaciones en
el lado i de la costura s que muestran el color k a través de ella,
fs,ki=∑(p,r)showingkxci,p,r. El min se
linealiza con una variable auxiliar por costura y color; para la versión de
factibilidad se exige en cambio un flujo de color igual a ambos lados de cada
costura. Los modelos de la comunidad aterrizan exactamente donde la aritmética
dice que deberían. El LP de Benjamin de 2009 tenía ~50 000 variables
(colocaciones podadas a posiciones válidas) y 7 952 ecuaciones: 256 por celda,
256 por pieza, y 60×5+420×17=7,440 restricciones de
equilibrio color-costura
(message 6910). El modelo de
Vlasta de 2008 cargaba 160 254 binarias
(message 5602); el programa
binario AMPL/CPLEX de Jimmy Timmermans, 272 704 variables y 24 566 ecuaciones
(message 6728). Günter
Stertenbrink ya había planteado la forma de grafo equivalente en 2007: hacer de
las 262 144 colocaciones vértices, unir los pares compatibles, y pedir un clique
de tamaño 256 (message 627), la
formulación a la que la literatura académica volvió una década más tarde.
La relajación no exige más que una edición: reemplazar
xc,p,r∈{0,1} por 0≤xc,p,r≤1. Ese único cambio hace que
el problema cruce la frontera más importante de la optimización. El programa
entero es NP-difícil: la programación entera 0–1 es uno de los 21 problemas
completos originales de Karp. El programa lineal es resoluble en tiempo
polinómico (elipsoide, puntos interiores), y en la práctica el símplex despacha
estos tamaños de modelo casi al instante. Benjamin lo midió: su sistema de
50 000 variables alcanzó un error inferior a 0,01 en unos diez segundos
(message 6913).
Dos propiedades hacen que la relajación sea genuinamente útil, no solo rápida.
Toda solución entera es también una fraccionaria, así que el óptimo del LP es
una cota: ningún tablero real puede puntuar nunca más de lo que dice la
relajación. Y los solucionadores LP devuelven certificados (valores duales,
pruebas de infactibilidad) que los métodos sin variables enteras no ofrecen.
Toda la cuestión es cuánta de esa velocidad sobrevive al viaje de vuelta hacia
las piezas enteras.
Así es como se ve realmente el óptimo del LP, en palabras de quien lo calculó.
El sistema de Benjamin «convergió relativamente rápido a error cero» (un tablero
perfecto, hasta donde las restricciones podían ver), y la esquina superior
izquierda contenía «30 % pieza 1, 20 % pieza 2, 10 % pieza 3, 40 % pieza 4»
(message 6905). El experimento
paralelo de Andrew llevaba la misma idea como un ascenso iterado sobre una
malla de pesos 256×256×4: «cada pieza está en todas partes»
(message 6911).
La relajación está contenta porque una superposición puede cubrirse. Un cuarto
de una pieza de arista azul más tres cuartos de una de arista rosa presenta una
mezcla que a la vez coincide en parte con un vecino azul y con uno rosa, una
coincidencia que ningún tablero físico puede realizar. Las restricciones
lineales saben poner precio a cuánta parte de cada pieza va dónde; no pueden
expresar «exactamente una de estas es real», porque una-de-varias no es un
hecho lineal. Hace falta una restricción cuadrática (o una de integralidad) para
decirlo. Benjamin usó (∑vi)2−∑vi2=0, que fuerza a cero todas
las variables de un grupo salvo una
(message 6913), y en el momento en
que la añadió, la convergencia murió: el sistema «se estanca en valores más
altos que se parecen a resultados del tipo 420-440 / 480 aristas correctas»
(message 6905).
Hay una teoría limpia bajo la observación. Las dos familias de asignación por sí
solas definen un politopo cuyos vértices son todos enteros (eso es
Birkhoff–von Neumann, y es exactamente por lo que el algoritmo húngaro resuelve
la asignación pura en tiempo polinómico). Añade las restricciones de costura y
esa propiedad de integralidad queda destruida: el politopo adquiere vértices
fraccionarios, y el óptimo del LP se posa sobre uno de ellos. La retrospectiva
de David Munjak comprime esto en una línea, listando entre sus enfoques
probados «Problema de asignación (soluciones enteras)» seguido de «Problema de
asignación con restricciones laterales (soluciones no necesariamente enteras)»
(message 8791). Las restricciones
laterales (las aristas, el puzzle de verdad) son precisamente lo que rompe la
garantía. Eternity II es un problema de asignación fácil soldado a un
acoplamiento difícil, y la relajación optimiza discretamente solo la mitad
fácil.
Toda la brecha cabe en dos celdas. Toma dos celdas adyacentes y dos piezas,
una entera de color 1, otra entera de color 2. Cualquier disposición con
piezas enteras puntúa 0: la costura siempre ve el color 1 contra el
color 2. El LP puntúa exactamente 1,0: pon media pieza de cada una en cada
celda, y las variables de coincidencia linealizadas de la costura recogen
0,5 de crédito por el color 1 más 0,5 por el color 2, con el óptimo
fraccionario posado precisamente en el punto 50/50. Lo verificamos a mano
y con un solucionador LP (el programa entero devuelve 0, la relajación
devuelve 1,0). Es la esquina de «30 % pieza 1» de Benjamin reducida a su
álgebra mínima, y aísla el mecanismo: las variables de costura premian
activamente las asignaciones fraccionarias por celda, así que el LP
prefiere las superposiciones.
El ejemplo también afila la historia de Birkhoff–von Neumann. En ese
óptimo fraccionario las restricciones de asignación se satisfacen
exactamente; nada del politopo de asignación se fuerza. Es solo el
objetivo de costura en mínimo-de-sumas lo que arrastra el óptimo fuera de
los vértices enteros. La mitad de asignación del modelo nunca fue el
problema.
Cada pocos años alguien nuevo recorría el camino, con mejores solucionadores y
más memoria, y chocaba con los mismos tres muros: la PLE completa es irresoluble
más allá de tamaños de juguete; el LP es resoluble y fraccionario; redondear o
restringir hacia la integralidad aterriza en los 400 y pico. Las campañas, en
orden:
| Año | Quién | Modelo | Dónde se detuvo | Msg |
|---|
| 2007 | Günter Stertenbrink | Clique máximo, 262 144 vértices | Solo formulación; nunca escaló | 166, 627 |
| 2007 | dmitri_ulitski | PLE (glpsol) sobre conjuntos de rotación | Resuelto en ~5 s por conjunto; el subproblema es fácil | 3320 |
| 2008 | Vlasta | PLE, 160 254 binarias | «Aplicable solo a puzzles 8x8»; pasó a SAT, alcanzó 428 | 5602 |
| 2008–09 | Andrew (bozmo2004) | Ascenso continuo, Newton–Raphson sobre ~250k pesos | ~800 000 días proyectados con su prototipo VBA | 5304, 6911 |
| 2009 | Benjamin (okifinoki) | LP, ~50 000 vars, 7 952 restricciones | Error cero en ~10 s, fraccionario; forzado a entero: se estanca en 420–440/480 | 6905, 6913 |
| 2009–10 | Jimmy Timmermans | Ideales tóricos; BIP AMPL/CPLEX, 272 704 y luego 153k vars | Límite de 32k variables de Singular; un 12x12 «resuelto» con un 5,3 % de infactibilidad (converge, la integralidad no) | 6716, 6728, 6745, 8077 |
| 2010 | Vlasta | MILP (164 256 booleanos) convertido a SAT | 8x8 en ~1 min; a la par con los backtrackers, sin ir más allá | 7858 |
| 2008–10 | David Munjak | Asignación con restricciones laterales, valores fraccionarios como probabilidades | 200–224 piezas colocadas, luego un callejón sin salida detectado; nunca hizo backtracking | 8791 |
| 2012 | Grupo Wauters | Hiperheurística (revisada por pares) | 461/480 en una hora (la línea académica) | 9023 |
| 2012 | Tony Wauters | MILP para conjuntos de rotación | Milisegundos; de nuevo, el subproblema fácil | 9071 |
| 2017 | Salassa, Vancroonenburg, Wauters et al. | Formulaciones MILP + Max-Clique | «Computacionalmente intratable para instancias de tamaño medio y grande»; recicladas como descomposiciones heurísticas | 9683, arXiv |
| 2025 | Marcus Garvie | PLE moderna | 10x10 con 6 colores en ~19 min; el E2 completo fuera de alcance | 11502 |
Tres lecturas de la tabla. Primero, fíjate en dónde la PLE gana: los conjuntos
de rotación, donde fijas solo la orientación de cada pieza de modo que los
recuentos de aristas direccionales se equilibran, cayeron ante glpsol en cinco
segundos en 2007 y ante CPLEX en milisegundos en 2012. Cuando la estructura
entera es genuinamente fácil, el solucionador lo dice de inmediato; el silencio
del puzzle completo es un veredicto, no un problema de herramientas. Segundo,
los números de la meseta coinciden a través de maquinarias totalmente
distintas: los 420–440 de Benjamin por LP penalizado, las 200–224 piezas
colocadas sin desajuste de Munjak por asignación iterada, los 461 del grupo
Wauters con una hora de reparación metaheurística por encima. Todo lo que tiene
forma de optimizador aterriza en la misma banda de los 400 y pico que la
búsqueda local simple alcanza
sin ningún LP en absoluto. Tercero, el artículo de 2017, el tratamiento
académico más sólido, con tanto una formulación MILP como una de Max-Clique,
concede la intratabilidad en su resumen y pivota hacia usar las formulaciones
dentro de heurísticas. Los propios constructores del camino pusieron la señal
de desvío.
El lado de la cota de la historia tiene la misma forma y vive en el
registro de callejones sin salida: los techos LP
medidos de este proyecto se sitúan entre 477 y 479 mientras que los tableros
que los sostienen rondan 458, una brecha demasiado ancha para certificar nada,
por exactamente la razón de cobertura fraccionaria de arriba. La anatomía de
esas cotas tiene su propia sección más abajo.
Un hecho de la literatura merece un sitio junto a la tabla. El tratamiento
académico más sólido, el artículo MILP + Max-Clique de 2017, solo resuelve
instancias enteras hasta aproximadamente 7×7 u 8×8 y nunca reporta una cota de
relajación LP para la instancia 16×16
(arXiv:1709.00252). Hasta donde llega el
registro público, nadie ha publicado una cota LP o MILP válida por debajo de
480 para el Eternity II completo. Los valores de 477 a 479 medidos más abajo
son condicionales (asumen un borde fijado), así que la pregunta
incondicional sigue abierta: probar cualquier cota válida por debajo de 480
mediante relajación convexa sería algo nuevo.
Probamos una relajación propia, construida desde el otro extremo del modelo.
En lugar de preguntar qué pieza ocupa qué celda, se listan los 1 024 lados de
pieza (256 piezas, 4 lados cada una) y se pregunta qué lados se emparejan:
dos lados solo pueden encontrarse si sus colores coinciden, y un tablero
terminado es un emparejamiento de los 960 lados no-borde en las 480 costuras
interiores. Ese recuento es exacto por construcción: las 4 piezas de esquina
aportan 2 lados no-borde cada una, las 56 piezas de borde aportan 3, las 196
interiores aportan 4, y 8+168+784=960=480×2. La instancia no
tiene holgura alguna; cada lado no-borde debe encontrar pareja.
El LP sobre este grafo de emparejamiento cuenta su historia en tres pasos.
Congela cada pieza en una orientación fija y la cota vale 307,00, entera e
igual a un recuento en forma cerrada, pero inválida para el puzzle real
porque prohíbe las rotaciones. Deja que los lados se emparejen libremente a
través de las rotaciones (21 636 variables de emparejamiento, una restricción
de grado por lado) y el LP alcanza exactamente 480,00, con 132
emparejamientos fraccionarios; añadir presupuestos de emparejamiento por
pieza no cambia nada. Añade la coherencia de rotación, una variable de
rotación relajada por pieza acoplada a los emparejamientos para que los lados
emparejados de una pieza acuerden una sola orientación (262 900 variables,
unas 503 000 restricciones, minutos de solucionador): sigue en 480,00, ahora
con todos los emparejamientos fraccionarios y ni una sola pieza con rotación
entera. El LP mantiene 480 factible poniendo cada pieza parcialmente en sus
cuatro rotaciones a la vez, el gemelo a nivel de lados de la esquina con
«30 % pieza 1» de arriba.
Así que el libro de cuentas de los colores cuadra perfectamente en cada nivel
de la relajación que pudimos permitirnos, y una cota que se clava en el
máximo es un resultado negativo de un tipo concreto y útil: localiza la
dureza. Nada en «qué lados pueden emparejarse con cuáles» obstruye un 480. La
obstrucción vive por entero en lo que estas relajaciones no ven, que cada
pieza ocupa una celda entera y que el emparejamiento debe tenderse plano como
una malla 16×16. El mismo veredicto que el modelo celda-pieza, alcanzado
desde la dirección opuesta.
Tres mediciones posteriores cierran del todo la cuestión del suministro.
Primero, la cota de conteo más simple de todas, cada color c con mc
medias aristas permite como mucho ⌊mc/2⌋ costuras
emparejadas, se evalúa sobre el juego de piezas real en
5⋅12+5⋅24+12⋅25=480 exactamente, porque cada uno
de los 22 recuentos de color es par. El presupuesto global de colores es
vacuo por construcción del puzzle; cualquier argumento de escasez tiene
que ser local o condicional. Segundo, las rotaciones enteras no restauran
la obstrucción. Dale a cada pieza una única variable entera de rotación y
pregunta al modelo de suministro por color si los compromisos de rotación
bastan por sí solos para bloquear el 480: no bastan. El óptimo LP es 480,0
y, esta vez resuelto también a optimalidad entera, el óptimo entero es
igualmente 480,0: para cada color existe una asignación de rotaciones
enteras que pone sus aristas en los lados correctos para gastar todo el
presupuesto ⌊Nk/2⌋. Eso añade un cuarto peldaño a la
escalera de arriba (rotaciones fijas 307, emparejamiento libre 480,00
fraccionario, coherencia de rotación 480,00 fraccionario, y ahora incluso
las rotaciones enteras dejan el 480 factible a nivel de suministro). La
flexibilidad de rotación nunca es la restricción activa; la obstrucción es
posicional, qué celda, junto a qué celda. Tercero, la vista de suministro
ni siquiera sabe ordenar tableros parciales. Un LP de costuras acotado por
el suministro por color (0,1 segundos por borde) devuelve 480 para los
seis bordes que le dimos, tanto el borde que sostiene el tablero
comunitario de 469 aristas (aristas coincidentes, puntuado fuera de la
convención estricta de cinco pistas; las convenciones están en
la página de récords) como cinco bordes recién
generados. Como discriminador de calidad de borde, el LP a nivel de
suministro es inútil; el LP posicional, por celda, de la sección siguiente
los separa de forma demostrada.
La cota incondicional se clava en el techo, así que la condicionamos. Fija
un borde completo (las 60 piezas del perímetro) y resuelve la relajación
LP sobre las 196 celdas interiores: el óptimo es una cota superior válida
para ese borde. Una nota de convención antes de los números: cada
puntuación de esta sección son aristas coincidentes sobre 480 en el 16×16
canónico con las cinco pistas oficiales fijadas, y los tableros medidos
son los mejores de este proyecto en el momento de la medición, no récords;
los mejores comunitarios están más arriba, con todo el contexto en
la página de récords.
La primera sorpresa es cuántos bordes distintos comparten un mismo techo.
Cuatro tableros de nuestro archivo, con cuatro bordes distintos, que
puntúan 458, 457, 455 y 454 aristas coincidentes, devuelven todos
exactamente la misma cota LP condicional: 478. Y dos de esos bordes no
guardan relación estructural con los demás: un tablero de 457 comparte con
el de 458 las cuatro filas superiores completas (56 piezas), pero los
tableros de 454 y 455 solo comparten con él 8 o 9 colocaciones de 256,
alrededor del 3 %. La cota es, pues, un invariante grueso que tableros
genuinamente distintos tienen en común, no la huella de una familia de
soluciones. La búsqueda local confirma que los propios tableros están
atascados: empujones sobre los tres tableros no-458 (8, 4 y 4 semillas a
diez minutos cada una) los subieron +0, +0 y +1; cada cuenca yace en su
propio óptimo local muy por debajo del techo compartido de 478.
Dos mediciones menores esbozan el paisaje alrededor de ese techo. El borde
del tablero de 458 se comporta como un máximo local de la propia cota: las
13 perturbaciones aleatorias de borde que probamos (5 intercambios simples
y 8 permutaciones de tres piezas, una sola semilla RNG) bajaron todas la
cota condicional, entre 2 y 5,5 puntos. Trece ensayos de una sola semilla
son un boceto, no un teorema. Y proyectar el borde del tablero comunitario
de 469 aristas a la convención de cinco pistas (superponer las cinco
pistas, recolocar las piezas desplazadas) baja su techo condicional a
477, un punto por debajo del borde de nuestro tablero de 458: un indicio
estructural, no una prueba, de que el techo con cinco pistas podría estar
por debajo del techo sin pistas.
Con un borde fijado, la cota se descompone sobre los tres tipos de
costura: 60 costuras del anillo del borde (totalmente determinadas por el
borde), 56 costuras borde-interior y 364 costuras interior-interior, con
un máximo combinatorio de 60+56+364=480. Muchos bordes distintos
presentan el mismo multiconjunto de demandas de color hacia el interior,
y por eso tantos comparten un mismo valor LP. En el borde del tablero de
458, la descomposición se lee 478=60+54,02+363,98. Léela
despacio: la parte interior-interior es esencialmente ajustada, el LP
concede solo 0,02 de las 364 costuras interiores; toda la pérdida contra
el máximo se asienta en la costura borde-interior. El veredicto del LP
sobre este borde: 2 de sus 56 costuras hacia el interior son
estructuralmente inemparejables por cualquier completado interior. El
propio tablero deja 4 sin emparejar, así que como mucho 2 son
teóricamente reparables, una subida máxima dentro del borde de +2, hasta
460. Probamos ese margen una vez: una re-resolución entera exacta
liberando 84 celdas (el perímetro inferior más las cinco filas interiores
inferiores; 30 minutos, un solucionador, una ejecución) devolvió delta 0.
O el +2 no es factible en enteros, o necesita una ventana mayor.
Un segundo borde intercambia en sentido contrario: su descomposición es
477=60+54,17+362,83, algo más de margen borde-interior pero
alrededor de 1,15 costuras interiores menos. Ningún color domina por sí
solo ninguna de las dos brechas; el acoplamiento es difuso. Llegar a 480
exige las dos partes al máximo a la vez, y ningún borde medido tiene
ambas. De las mismas tablas cae un microhecho del diseño de colores del
puzzle: los cinco colores raros (24 medias aristas cada uno) aportan
exactamente 0 a la parte interior-interior, porque solo aparecen en los
lados interiores de las piezas de borde; un emparejamiento
interior-interior de color raro es imposible por taxonomía de piezas.
El techo condicional más alto de nuestro archivo es 479, a uno de la
perfección, y descansa sobre un tablero que solo puntúa 457. Su borde
salió de apenas un minuto de búsqueda local, frente a horas detrás de los
bordes de 478. Y sin embargo ocho semillas independientes de búsqueda
local a una hora cada una se estancan todas en 457, y una re-resolución
entera exacta de la unión de todos sus grupos de fallos (28 celdas
liberadas) prueba que no existe mejora local: delta 0 en 0,46 segundos.
Las tres descomposiciones se alinean como
478=60+54,02+363,98, 477=60+54,17+362,83 y
479=60+55,48+363,52, y la brecha LP-entero por tablero se lee
20, 20 y 22: casi constante en todos los bordes probados (479 es también
el techo más alto visto en 18 LP condicionales sobre bordes diversos). La
cota condicional ordena los bordes por estructura, pero no predice qué
borde da el mejor tablero de piezas enteras; el borde con techo 479 está
bloqueado en enteros más abajo que el de techo 478. El mecanismo es el de
la página: el margen extra es holgura de cobertura fraccionaria, y un
techo más alto solo significa que el libro de cuentas de colores está
más cerca de cuadrar, no que algún tablero entero lo realice. Una
conjetura merece escribirse como conjetura: el borde de un tablero
perfecto debe tener cota condicional exactamente 480, ambas partes al
máximo a la vez, y el borde de 479 muestra que el LP se queda a uno de esa
condición necesaria.
Una última cautela al leer estas descomposiciones: las asignaciones LP por
color no son cotas por color. En el tablero de 458, el recuento entero
real de un color (21) supera el suelo de su asignación LP (20,89, que
redondea hacia abajo a 20). El óptimo LP es una asignación conjunta entre
colores; leer sus filas por color como techos individuales es un error de
categoría. La anatomía completa en ese tablero: el total LP de costuras
interiores es 363,96 frente a 346 costuras realmente emparejadas, una
brecha interior de 17,96, de la cual 5,96 es holgura fraccionaria y 12 es
el LP asignando colores de una manera que ningún tablero de piezas
enteras puede.
La respuesta de manual a un LP flojo es apretarlo: elevar los términos
bilineales, añadir planos de corte, subir por la jerarquía de
relajaciones. Probamos uno de cada y medimos. Ninguno cerró la brecha, y
dos de los fracasos son lo bastante instructivos como para ser la
lección.
La elevación de McCormick: válida en teoría, inabordable a tamaño
real. El remedio estándar para productos de variables es una variable
auxiliar por costura y por par de colocaciones compatibles, emparedada por
z≤x1, z≤x2 y z≥x1+x2−1. En instancias pequeñas
nuestra implementación reproduce la cota estándar: un 6×6 necesita 22 000
variables de par y 2,5 segundos, un 8×8 de 4 colores 300 000 y 60
segundos. El escalado se detiene justo después: un 8×8 de 6 colores y un
10×10 de 6 colores (1,25 millones de variables de par) agotaron ambos los
60 segundos en nuestro solucionador LP, y el puzzle completo necesitaría
del orden de 5 a 20 millones de variables de par con unas tres
restricciones cada una, más allá de lo que ese solucionador maneja. Los
dos atajos obvios produjeron cotas inválidas, en direcciones opuestas, y
cada uno se refuta con aritmética pura. Restringir las variables de par a
colocaciones con masa LP superior a 0,05 infracuenta y devuelve 402, por
debajo de un tablero factible conocido de 458; una cota superior por
debajo de un punto factible es una prueba de invalidez. Mantener a la vez
las variables de par y las variables de costura originales cuenta doble y
devuelve 479,58, por encima del 478 sin elevar; añadir restricciones
solo puede bajar un óptimo LP, así que ese también se refuta solo. El
patrón correcto, generar como planos de corte las desigualdades de
McCormick violadas con costes reducidos exactos, exige un acceso al
solucionador de más bajo nivel que el que construimos: no probado, no
imposible.
Planos de corte sobre la escasez de color: válidos o vacuos, nunca
ambos. Implementamos branch-and-cut con una sola familia de cortes,
cortes de clique de suministro sobre el grafo de conflicto de colores
(«si un conjunto de costuras está forzado al color k, como mucho
⌊suministrok/2⌋ de ellas pueden coincidir»), en un
solo hilo y una sola configuración; el veredicto de abajo es sobre esta
familia de cortes, no sobre todos los cortes. Los LP de cola sin cortes,
sobre uno de nuestros tableros de 459 aristas (aristas coincidentes,
convención de cinco pistas), son válidos pero flojos en un 4 a 22 %:
liberar las últimas 1, 2, 3 y 4 filas da cotas LP de 27, 58, 90 y 124
frente a 26, 49, 74 y 104 conseguidos, sin certificar nunca nada. El
corte tal cual está enunciado es peor que flojo, es inválido: en la cola
de una fila empuja el LP a 20, por debajo del 26 factible, así que la
desigualdad cortó el óptimo verdadero (las medias aristas del color k
también se consumen fuera del conjunto forzado, y por los otros tres
lados de cada pieza). Toda contabilidad lo bastante floja para ser válida
volvió a caer en la cota vacua sin cortes. El hilo conductor encaja con el
resto de la página: la dureza del puzzle es la distinción global, cada
pieza usada exactamente una vez, no la escasez local de color, y los
cliques del grafo de conflicto de colores son minúsculos y poco
informativos.
Un nivel más arriba en la jerarquía: el SDP está igual de ciego. El
peldaño por encima del LP es la elevación semidefinida de nivel 1 (Shor)
de la formulación cuadrática, válida por construcción: toda solución
verdadera sigue siendo factible con el mismo valor objetivo. La
construimos exactamente sobre instancias 3×3 plantadas con óptimos
certificados de 12, 11 y 11 sobre 12. En las dos instancias no triviales
el SDP certifica 12,000: no ve una obstrucción de tamaño unidad que un
conteo elemental (5 medias aristas de un color permiten como mucho 2
coincidencias) resuelve al instante. Un control LP McCormick válido
devuelve el mismo 12,000, así que la ceguera ya está presente en el nivel
lineal; la restricción semidefinida positiva no añade nada aquí. Y el
coste explota de inmediato: la elevación completa consciente de las
rotaciones con solo 9 celdas (324 variables, un bloque semidefinido de
325×325) falló en tres intentos independientes bajo un presupuesto
mononúcleo de 280 segundos. Si la elevación conjunta con las rotaciones
recuperaría el ajuste es una pregunta abierta, no refutada. Son hallazgos
computacionales sobre instancias diminutas con un solo solucionador SDP,
no teoremas.
- El LP: polinómico, genuinamente rápido. Los métodos de puntos interiores
resuelven programas lineales en tiempo polinómico; en modelos de este tamaño
(50k–270k variables, de miles a cientos de miles de restricciones) los
solucionadores modernos terminan en segundos a minutos. Es el único objeto
genuinamente barato de la página.
- La PLE: NP-difícil, y no de forma abstracta. La ramificación y acotación
es backtracking con una cota LP en cada nodo: exponencial en el peor caso, y
una instancia construida en el pico de dureza
está diseñada para realizar ese peor caso. La forma medida del coste: un
solucionador que maneja el 8×8 (64 piezas) no devuelve nada en el 16×16,
porque el árbol bajo la raíz se eleva al cuadrado, no se duplica.
- La brecha de integralidad es la moneda real. Todo el valor del método es
la distancia entre el óptimo del LP y la mejor solución entera. Aquí esa
distancia es de aproximadamente 478 frente a 458-y-estancándose: la relajación
gasta su presupuesto polinómico respondiendo a una pregunta sobre un puzzle
distinto, fraccionario. Los planos de corte existen para reducir la brecha;
nadie ha reportado cortes que le cierren ni una muesca en el E2, incluidos
nuestros tres intentos medidos de arriba, y la estructura por costura que
finge coincidencias regenera la holgura en todas partes.
- La ramificación y acotación poda con la cota que tiene. Un nodo se corta
solo cuando su cota LP cae por debajo del incumbente. Con la cota flotando
~20 aristas por encima de cualquier cosa real, casi nada se poda: el análogo
exacto de las cláusulas aprendidas anchas e inútiles en
CDCL, un camino más allá.
La conclusión justa es una reubicación, no un rechazo, la misma a la que llega
la página SAT para el CDCL.
- Cotas, enunciadas con sus barras de error. La relajación es un techo
válido, calculado en tiempo polinómico; solo que aquí es flojo. La
entrada de callejones sin salida registra el
veredicto para que nadie lo vuelva a deducir esperando un certificado.
- Una cautela: no toda relajación es una cota. Una «relajación» barata
y tentadora, rellenar el tablero celda a celda con la pieza localmente
mejor permitiendo reutilizar piezas, no es un techo válido de ninguna
clase: es una heurística voraz cuyo punto fijo depende del tablero de
partida. Desde uno de nuestros tableros de 457 aristas (aristas
coincidentes, convención de cinco pistas) converge a 461; desde uno de
456, a 461; desde uno de 440, hasta 469. El uso válido es como
indicador de margen: cuando la puntuación voraz relajada iguala la del
propio tablero, el tablero queda probado como máximo local estricto
incluso con la unicidad de piezas relajada, un certificado de callejón
sin salida más fuerte que las pruebas por operadores. En ese tablero de
457, la brecha de +4 quedó probada incerrable por cualquier cadena de
permutaciones hasta longitud 11 (40 millones de permutaciones, cero
mejoras). La regla: solo los valores derivados de LP o MIP son techos;
las puntuaciones voraces relajadas son diagnósticos.
- Subproblemas de asignación, donde la integralidad es gratis. Dentro de los
bucles de reparación, rellenar k agujeros no adyacentes dos a dos es un puro
problema de asignación k×k: politopo de Birkhoff, vértices enteros,
algoritmo húngaro en O(k3). Ese es el vecindario Eternity II de Schaus, y
es el único lugar de este wiki donde la maquinaria del optimizador corre a
plena potencia: véase
búsqueda local y ALNS.
- Subproblemas enteros fáciles, despachados al instante. Los conjuntos de
rotación por MILP en milisegundos
(message 9071) son el patrón:
cuando una subpregunta tiene estructura tratable, un solucionador MIP es la
forma fiable más rápida de zanjarla, incluido zanjar que la respuesta no
ayuda.
- La infactibilidad como teorema. Una PLE que vuelve infactible sobre una
región fijada prueba la misma imposibilidad que una llamada SAT UNSAT: la
moneda-certificado detrás del
muro de rigidez. Este proyecto acuña esos
certificados con SAT, que es más rápido en esta codificación; un solucionador
MIP es una segunda casa de moneda legítima, y el colocador de Munjak usó
exactamente esa señal, «identificando un problema que impediría colocar las
256 piezas» (message 8791).
- Formulaciones como generadores de vecindarios. La contribución duradera
del artículo de 2017 es metodológica: métodos constructivos basados en MILP
que siembran una búsqueda local de vecindarios múltiples, más nuevas
instancias de referencia difíciles para la comunidad
(arXiv:1709.00252). La formulación
sobrevive como una pieza, dentro de una heurística que se apropia del
problema de integralidad en lugar de relajarlo.
- La formulación es el algoritmo. Medimos dos codificaciones MIP de la
misma tarea, recombinar un pequeño corpus de buenos tableros en uno
mejor, y se comportan como la noche y el día (un solo solucionador, CBC,
ejecuciones únicas). La codificación A, «cada celda elige un tablero
fuente», arrastra variables de costura cuadráticas en el tamaño del
corpus: va bien con 4 o 5 tableros (óptimo entero encontrado en 17 a 86
segundos), pero con 9 tableros (unas 50 000 variables de costura y
100 000 restricciones) el solucionador no encontró ninguna solución
entera factible en 30 minutos, y su cota LP de 1 094, más del doble del
techo de 480, no significaba nada. La codificación B, «libera una
región, una variable por celda-pieza-rotación, fija el resto», es de 10
a 50 veces más pequeña (unas 800 variables), se resuelve en menos de un
minuto, y su LP queda ajustado contra el óptimo entero: prueba la
optimalidad local en lugar de adivinarla. El mecanismo: las variables de
la codificación A no llevan ningún significado geométrico que el LP
pueda explotar, las mezclas fraccionarias de tableros cobran un crédito
que ningún redondeo conserva, mientras que las variables de la
codificación B son colocaciones, así que su politopo se queda cerca de
la envolvente entera. El artículo de 2017 reciclando sus formulaciones
dentro de heurísticas es la misma lección vista desde el otro lado.
El camino del optimizador, recorrido hasta el final, enseña un hecho limpio
sobre Eternity II: el puzzle es exactamente la restricción de integralidad. Todo
lo lineal en él, los flujos, los equilibrios, el esqueleto de asignación, es
polinómico y quedó resuelto ya en 2009, a error cero, en diez segundos. Lo que
queda es el requisito de que cada pieza esté en algún sitio entera, una vez. El
alegre tablero fraccionario de la relajación es la imagen más nítida que nadie
ha dibujado de cómo se ve el 99 % fácil sin el 1 % difícil.