# LP and ILP relaxations: half a piece everywhere

> Write Eternity II as an integer program, drop the integrality, and a linear solver reaches zero error in seconds, with 30% of one piece and 20% of another sharing a corner. Eighteen years of community campaigns measured where the fractional comfort ends: a plateau at 420–440 edges the moment the pieces must be whole, an ILP wall at 8×8, and an academic best of 461-in-an-hour. What the optimizer's road teaches, and where LP still earns its keep.

- Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/exact/lp-relaxations/
- Updated: 2026-07-02
- Topics: exact-methods
- Source: The max-clique framing: 262,144 placement vertices, find a clique of 256 (groups.io message 627, 2007) — https://groups.io/g/eternity2/message/627
- Source: Rotation sets solved by ILP (glpsol) in about 5 seconds each (groups.io message 3320, 2007) — https://groups.io/g/eternity2/message/3320
- Source: Vlasta's LP status report: 160,254 binaries; ILP 'applicable only for 8×8 puzzles' (groups.io message 5602, 2008) — https://groups.io/g/eternity2/message/5602
- Source: Andrew's continuous-ascent formulation and the 800,000-day estimate (groups.io message 5304, 2008) — https://groups.io/g/eternity2/message/5304
- Source: Benjamin's 50,000-variable LP and its fractional corner: 30% piece 1, 20% piece 2 (groups.io message 6905, 2009) — https://groups.io/g/eternity2/message/6905
- Source: Benjamin's constraint counts (7,952 equations) and the quadratic integrality trick (groups.io messages 6910/6913, 2009) — https://groups.io/g/eternity2/message/6913
- Source: Andrew on the implicit solver: 'every piece is everywhere', Newton–Raphson over 250,000 weights (groups.io message 6911, 2009) — https://groups.io/g/eternity2/message/6911
- Source: Timmermans's AMPL/CPLEX binary integer program: 272,704 variables, 24,566 equations (groups.io message 6728, 2009) — https://groups.io/g/eternity2/message/6728
- Source: The real-domain 12×12 'solution' at 5.3% infeasibility (groups.io message 6745, 2009) — https://groups.io/g/eternity2/message/6745
- Source: Munjak's retrospective: side-constrained assignment, 200–224 pieces, no backtracking (groups.io message 8791, 2011) — https://groups.io/g/eternity2/message/8791
- Source: Wauters: the academic line, 461/480 matched edges in one hour (groups.io message 9023, 2012) — https://groups.io/g/eternity2/message/9023
- Source: Wauters: rotation sets by MILP in milliseconds (groups.io message 9071, 2012) — https://groups.io/g/eternity2/message/9071
- Source: The MILP + Max-Clique paper reaches the list (groups.io message 9683, 2017) — https://groups.io/g/eternity2/message/9683
- Source: Salassa, Vancroonenburg, Wauters, Della Croce & Vanden Berghe, MILP and Max-Clique based heuristics for the Eternity II puzzle (arXiv:1709.00252, 2017) — https://arxiv.org/abs/1709.00252
- Source: Wauters, Vancroonenburg & Vanden Berghe, A guide-and-observe hyper-heuristic approach to the Eternity II puzzle (JMMA, 2012) — https://link.springer.com/article/10.1007/s10852-012-9178-4
- Source: Garvie's modern ILP: a 10×10, 6-colour instance solved in about 19 minutes (groups.io message 11502, 2025) — https://groups.io/g/eternity2/message/11502

---
There are three classic roads into Eternity II. Backtracking walks the tree.
[SAT and CSP encodings](/research/build/exact/sat-csp-encodings) hand the
logic to an industrial solver. The third road belongs to the optimizers:
write the puzzle as an integer program (variables, linear constraints, an
objective) and call CPLEX. It is the road every operations-research person
tries first, because it comes with a move the other two don't have:
*relaxation*. Delete the requirement that variables be whole numbers and the
NP-hard integer program becomes a linear program, solvable in polynomial
time. Solve the easy version, hope the answer is nearly integral, repair the
rest.

The community walked this road repeatedly between 2007 and 2025, with
solvers from `glpsol` to CPLEX to hand-rolled Newton–Raphson, and the
outcome was measured precisely enough to be worth a page: the relaxation
solves fast and reports a nearly perfect board, one made of fractions of
pieces. Force the pieces whole and the score collapses onto a plateau around
420–440 of 480 edges. The gap between the fractional optimum and the integer
one is not a technicality. It is the exact place where the puzzle lives.

## The formulation

One binary variable per placement, exactly as in the SAT encoding: let
$x_{c,p,r} \in \{0,1\}$ mean "piece $p$ sits at cell $c$ with rotation $r$".
Two families of assignment constraints and one per-seam accounting give the
whole model:

$$
\begin{aligned}
\max \;\; & \sum_{s} y_s
  && \text{(matched seams)} \\
\text{s.t.} \;\;
  & \sum_{p,\,r} x_{c,p,r} = 1 && \forall\, \text{cell } c \\
  & \sum_{c,\,r} x_{c,p,r} = 1 && \forall\, \text{piece } p \\
  & y_s \,\le\, \sum_{k} \min\!\big( f_{s,k}^{1},\, f_{s,k}^{2} \big)
  && \forall\, \text{seam } s
\end{aligned}
$$

where $f_{s,k}^{i}$ is the colour flow, the total weight of placements on
side $i$ of seam $s$ that show colour $k$ across it,
$f_{s,k}^{i} = \sum_{(p,r)\,\text{showing}\,k} x_{c_i,p,r}$. The $\min$ is
linearized with one auxiliary variable per seam and colour; for the
*feasibility* version you instead demand equal colour flow on both sides of
every seam. Community models land exactly where the arithmetic
says they should. Benjamin's 2009 LP had ~50,000 variables (placements
pruned to valid positions) and 7,952 equations: 256 per-cell, 256
per-piece, and $60 \times 5 + 420 \times 17 = 7{,}440$ seam-colour balance
constraints ([message 6910](https://groups.io/g/eternity2/message/6910)).
Vlasta's 2008 model carried 160,254 binaries
([message 5602](https://groups.io/g/eternity2/message/5602)); Jimmy
Timmermans's AMPL/CPLEX binary program, 272,704 variables and 24,566
equations ([message 6728](https://groups.io/g/eternity2/message/6728)).
Günter Stertenbrink had already posed the equivalent graph form in 2007:
make the 262,144 placements vertices, join compatible pairs, and ask for a
clique of size 256 ([message 627](https://groups.io/g/eternity2/message/627)),
the framing the academic literature returned to a decade later.

## Relax it, and it solves in seconds

Relaxation means one edit: replace $x_{c,p,r} \in \{0,1\}$ with
$0 \le x_{c,p,r} \le 1$. That single change moves the problem across the
most important boundary in optimization. The integer program is NP-hard:
0–1 integer programming is one of Karp's original 21 complete problems. The
linear program is solvable in polynomial time (ellipsoid, interior-point),
and in practice simplex dispatches these model sizes almost instantly.
Benjamin measured it: his 50,000-variable system reached an error below
0.01 in about ten seconds
([message 6913](https://groups.io/g/eternity2/message/6913)).

Two properties make the relaxation genuinely useful, not just fast. Every
integer solution is also a fractional one, so the LP optimum is a *bound*:
no real board can ever score more than the relaxation says. And LP solvers
return certificates (dual values, infeasibility proofs) that integer-free
methods don't. The whole question is how much of that speed survives the
return trip to whole pieces.

## The fractional board

Here is what the LP optimum actually looks like, in the words of the person
who computed it. Benjamin's system "converged relatively fast to zero
error" (a perfect board, as far as the constraints could see), and the
upper-left corner held "30% piece 1, 20% piece 2, 10% piece 3, 40% piece 4"
([message 6905](https://groups.io/g/eternity2/message/6905)). Andrew's
parallel experiment ran the same idea as an iterated ascent over a
256×256×4 grid of weights: "every piece is everywhere"
([message 6911](https://groups.io/g/eternity2/message/6911)).

The relaxation is happy because a superposition can hedge. A quarter of a
blue-edged piece plus three quarters of a pink-edged one presents a blend
that simultaneously part-matches a blue neighbour and a pink one, a match
no physical board can realize. Linear constraints can price how much of
each piece sits where; they cannot express "exactly one of these is real,"
because *one-of* is not a linear fact. It takes a quadratic constraint (or
an integrality one) to say it. Benjamin used
$(\sum v_i)^2 - \sum v_i^2 = 0$, which forces all but one variable in a
group to zero ([message 6913](https://groups.io/g/eternity2/message/6913)),
and the moment he added it, convergence died: the system "stalls at higher
values which resemble results like 420-440 / 480 correct edges"
([message 6905](https://groups.io/g/eternity2/message/6905)).

There is clean theory underneath the observation. The two assignment
families alone define a polytope whose vertices are all integral (that is
Birkhoff–von Neumann, and it is exactly why the Hungarian algorithm solves
pure assignment in polynomial time). Add the seam constraints and that
integrality property is destroyed: the polytope grows fractional vertices,
and the LP optimum sits on one of them. David Munjak's retrospective
compresses this into one line, listing among his tried approaches
"Assignment problem (integral solutions)" followed by "Assignment problem
with side constraints (not necessarily integral solutions)"
([message 8791](https://groups.io/g/eternity2/message/8791)). The side
constraints (the edges, the actual puzzle) are precisely what breaks the
guarantee. Eternity II is an easy assignment problem welded to a hard
coupling, and the relaxation quietly optimizes only the easy half.

## The measured plateau

Every few years someone new drove the road, with better solvers and more
memory, and hit the same three walls: the full ILP is unsolvable past toy
sizes; the LP is solvable and fractional; rounding or constraining toward
integrality lands in the mid-400s. The campaigns, in order:

| Year | Who | Model | Where it stopped | Msg |
| --- | --- | --- | --- | --- |
| 2007 | Günter Stertenbrink | Max-clique, 262,144 vertices | Framing only; never scaled | [166](https://groups.io/g/eternity2/message/166), [627](https://groups.io/g/eternity2/message/627) |
| 2007 | dmitri_ulitski | ILP (glpsol) on rotation sets | Solved in ~5 s per set; the subproblem is easy | [3320](https://groups.io/g/eternity2/message/3320) |
| 2008 | Vlasta | ILP, 160,254 binaries | "Applicable only for 8x8 puzzles"; switched to SAT, reached 428 | [5602](https://groups.io/g/eternity2/message/5602) |
| 2008–09 | Andrew (bozmo2004) | Continuous ascent, Newton–Raphson over ~250k weights | ~800,000 days projected with his VBA prototype | [5304](https://groups.io/g/eternity2/message/5304), [6911](https://groups.io/g/eternity2/message/6911) |
| 2009 | Benjamin (okifinoki) | LP, ~50,000 vars, 7,952 constraints | Zero error in ~10 s, fractional; forced integral: stalls at 420–440/480 | [6905](https://groups.io/g/eternity2/message/6905), [6913](https://groups.io/g/eternity2/message/6913) |
| 2009–10 | Jimmy Timmermans | Toric ideals; AMPL/CPLEX BIP, 272,704 then 153k vars | Singular's 32k-variable limit; a 12x12 "solved" at 5.3% infeasibility (converges, integrality doesn't) | [6716](https://groups.io/g/eternity2/message/6716), [6728](https://groups.io/g/eternity2/message/6728), [6745](https://groups.io/g/eternity2/message/6745), [8077](https://groups.io/g/eternity2/message/8077) |
| 2010 | Vlasta | MILP (164,256 booleans) converted to SAT | 8x8 in ~1 min; parity with backtrackers, no further | [7858](https://groups.io/g/eternity2/message/7858) |
| 2008–10 | David Munjak | Side-constrained assignment, fractional values as probabilities | 200–224 pieces placed, then a detected dead end; never backtracked | [8791](https://groups.io/g/eternity2/message/8791) |
| 2012 | Wauters group | Hyper-heuristic (peer-reviewed) | 461/480 in one hour (the academic line) | [9023](https://groups.io/g/eternity2/message/9023) |
| 2012 | Tony Wauters | MILP for rotation sets | Milliseconds; again, the easy subproblem | [9071](https://groups.io/g/eternity2/message/9071) |
| 2017 | Salassa, Vancroonenburg, Wauters et al. | MILP + Max-Clique formulations | "Computationally intractable for medium and large sized instances"; recycled as heuristic decompositions | [9683](https://groups.io/g/eternity2/message/9683), [arXiv](https://arxiv.org/abs/1709.00252) |
| 2025 | Marcus Garvie | Modern ILP | 10x10 with 6 colours in ~19 min; full E2 out of reach | [11502](https://groups.io/g/eternity2/message/11502) |

Three readings of the table. First, notice where ILP *wins*: rotation sets,
where you fix only each piece's orientation so the directional edge counts
balance, fell to `glpsol` in five seconds in 2007 and to CPLEX in milliseconds in
2012. When the integer structure is genuinely easy, the solver says so
immediately; the full puzzle's silence is a verdict, not a tooling problem.
Second, the plateau numbers agree across totally different machinery:
Benjamin's 420–440 by penalized LP, Munjak's 200–224 pieces placed
mismatch-free by iterated assignment, the Wauters group's 461 with an hour
of metaheuristic repair on top. Everything optimizer-shaped lands in the
same mid-400s band that plain
[local search](/research/build/local-search/local-search-alns) reaches without
any LP at all. Third, the 2017 paper, the strongest academic treatment,
with both a MILP and a Max-Clique formulation, concedes intractability in
its abstract and pivots to using the formulations *inside* heuristics. The
road's own builders posted the detour sign.

The bound side of the story has the same shape and lives on the
[dead-ends ledger](/research/build/dead-ends): this project's measured LP
ceiling sits around 478 while the best real boards sit near 458, a gap far
too wide to certify anything, for exactly the fractional-hedging reason
above.

## What it costs

- **The LP: polynomial, genuinely fast.** Interior-point methods solve
  linear programs in polynomial time; on models of this size (50k–270k
  variables, thousands to hundreds of thousands of constraints) modern
  solvers finish in seconds to minutes. This is the one genuinely cheap
  object on the page.
- **The ILP: NP-hard, and not abstractly.** Branch-and-bound is
  backtracking with an LP bound at every node: worst-case exponential, and
  an instance [built at the hardness peak](/research/why/phase-transition)
  is engineered to realize the worst case. The measured form of the cost:
  a solver that handles 8×8 (64 pieces) returns nothing on 16×16, because
  the tree under the root is squared, not doubled.
- **The integrality gap is the real currency.** The whole method's value is
  the distance between the LP optimum and the best integer solution. Here
  that distance is roughly 478 versus 458-and-stalling: the relaxation
  spends its polynomial budget answering a question about a different,
  fractional puzzle. Cutting planes exist to buy the gap down; nobody has
  reported cuts that close a dent of it on E2, and the per-seam structure
  that fakes matches regenerates the slack everywhere.
- **Branch-and-bound prunes with the bound it has.** A node is cut only
  when its LP bound falls below the incumbent. With the bound floating ~20
  edges above anything real, almost nothing prunes: the exact analogue of
  wide, useless learned clauses in
  [CDCL](/research/build/exact/sat-csp-encodings), one road over.

## What LP and MIP are still for

The fair conclusion is relocation, not dismissal, the same one the
[SAT page](/research/build/exact/sat-csp-encodings) reaches for CDCL.

- **Bounds, stated with their error bars.** The relaxation *is* a valid
  ceiling, computed in polynomial time; it is just a loose one here. The
  [dead-ends entry](/research/build/dead-ends) records the verdict so
  nobody re-derives it expecting a certificate.
- **Assignment subproblems, where integrality is free.** Inside repair
  loops, refilling $k$ pairwise non-adjacent holes is a pure $k \times k$
  assignment problem: Birkhoff's polytope, integral vertices, Hungarian
  algorithm in $O(k^3)$. That is Schaus's Eternity II neighborhood, and it
  is the one place on this wiki where the optimizer's machinery runs at
  full power: see
  [local search and ALNS](/research/build/local-search/local-search-alns).
- **Easy integer subproblems, dispatched instantly.** Rotation sets by MILP
  in milliseconds ([message 9071](https://groups.io/g/eternity2/message/9071))
  is the pattern: when a sub-question has tractable structure, a MIP solver
  is the fastest reliable way to settle it, including settling that the
  answer doesn't help.
- **Infeasibility as a theorem.** An ILP that comes back infeasible on a
  pinned region proves the same impossibility a SAT UNSAT call does: the
  certificate currency behind the
  [rigidity wall](/research/why/rigidity-wall). This project mints those
  certificates with SAT, which is faster on this encoding; a MIP solver is
  a legitimate second mint, and Munjak's placer used exactly that signal,
  "identifying an issue that would prevent all 256 pieces from being
  placed" ([message 8791](https://groups.io/g/eternity2/message/8791)).
- **Formulations as neighbourhood generators.** The 2017 paper's lasting
  contribution is methodological: MILP-based constructive methods seeding a
  multi-neighbourhood local search, plus new hard benchmark instances for
  the community ([arXiv:1709.00252](https://arxiv.org/abs/1709.00252)).
  The formulation survives as a *part*, inside a heuristic that owns the
  integrality problem instead of relaxing it away.

The optimizer's road, walked to its end, teaches one clean fact about
Eternity II: the puzzle is exactly the integrality constraint. Everything
linear about it, the flows, the balances, the assignment skeleton, is
polynomial and was solved by 2009, to zero error, in ten seconds. What
remains is the requirement that every piece be somewhere *whole*, once. The
relaxation's cheerful fractional board is the sharpest picture anyone has
drawn of what the easy 99% looks like without the hard 1%.

## Related

- [The rigidity wall](https://eternity2.dev/research/why/rigidity-wall) — Every record board we have is frozen in place. You cannot nudge your way from a great board to a perfect one, and we can prove it.
- [Dead ends](https://eternity2.dev/research/build/dead-ends) — Approaches we tried that look promising and don't move the needle on Eternity II, written down with what we found so you can spend your time elsewhere.
- [SAT and CSP encodings](https://eternity2.dev/research/build/exact/sat-csp-encodings) — Write the puzzle as clauses and hand it to an industrial solver: the obvious move, tried since 2008. Why complete solvers stall on the full board, and where their verdicts still earn their keep as impossibility proofs.
- [All-different, Régin's matching filter](https://eternity2.dev/research/build/reduce/alldiff-regin) — No piece may be used twice: one global all-different constraint over 256 cells. Jean-Charles Régin showed in 1994 how bipartite matching filters it completely in polynomial time; its per-colour cousin is the strongest propagator anyone has measured on edge matching, with one sharp caveat about mismatch-tolerant searches.