2D STRIP / BIN PACKING MILP & FAULT-LINE FREE MILP

Mathematical Foundations of TITAN PACK — 2D Strip Packing & MILP Linearization

Explore the Mixed-Integer Linear Programming (MILP) formulation of 2D Strip / Bin Packing behind TITAN PACK, along with the multi-scale interlocking algorithms that guarantee zero-fault-line solutions.

Chapter 011. What is the 2D Packing Problem?

The 2D Packing Problem is a combinatorial optimization challenge where rectangular parts of various dimensions must be placed inside a bounding sheet or plate without overlapping or exceeding boundary limits. It has extensive real-world applications in sheet-metal manufacturing, woodworking, cutting-stock layouts, and VLSI floorplanning.

Deciding whether a set of items can be packed with zero scrap (100% material efficiency) without void is known to be strongly NP-hard.

Chapter 022. Linearizing Geometric Non-Overlap Constraints (Big-M Formulation)

The condition that two rectangles $i$ and $j$ (placed at $(x_i, y_i)$ with dimensions $w_i \times h_i$) do not overlap is inherently disjunctive (connected by logical OR):

$$ (x_i + w_i \le x_j) \;\lor\; (x_j + w_j \le x_i) \;\lor\; (y_i + h_i \le y_j) \;\lor\; (y_j + h_j \le y_i) $$

In Mixed-Integer Linear Programming (MILP), we linearize this disjunction using four binary indicator variables $\delta_{ij,1}, \delta_{ij,2}, \delta_{ij,3}, \delta_{ij,4} \in \{0, 1\}$ and tight axis-specific constants derived from plate dimensions $W, H$:

$$ \begin{aligned} &\min \quad 0 \quad (\text{Feasibility check for zero scrap layout}) \\ &\text{s.t.} \\ &x_i + w_i \le x_j + W(1 - \delta_{ij,1}) \quad (\forall i < j) \\ &x_j + w_j \le x_i + W(1 - \delta_{ij,2}) \quad (\forall i < j) \\ &y_i + h_i \le y_j + H(1 - \delta_{ij,3}) \quad (\forall i < j) \\ &y_j + h_j \le y_i + H(1 - \delta_{ij,4}) \quad (\forall i < j) \\ &\delta_{ij,1} + \delta_{ij,2} + \delta_{ij,3} + \delta_{ij,4} \ge 1 \quad (\forall i < j) \\ &0 \le x_i \le W - w_i, \quad 0 \le y_i \le H - h_i \quad (\forall i) \end{aligned} $$

⚠️ CAUTION: Choice of Big-M and Numerical Stability

Setting Big-M to an arbitrary large number can weaken the continuous LP relaxation bound, increasing the number of branch-and-bound nodes. It may also trigger numerical instability where parts slightly overlap within solver tolerances ($10^{-6}$) and are falsely treated as feasible. Setting tight, provable upper bounds ($M_x = W$ and $M_y = H$) is standard practice in mathematical programming.

Chapter 033. Geometric Guarantees for Fault-Line-Free Layouts

If a rectangle is naively sliced with full-width or full-height cuts, continuous fault lines (guillotine cuts) emerge, degrading structural rigidity and breaking the puzzle into trivial independent sub-puzzles.

TITAN PACK uses a Multi-Scale Interlocking & Core Partitioning algorithm that guarantees every interior grid line $c \in \{1, \dots, W-1\}$ and $r \in \{1, \dots, H-1\}$ is crossed by at least one overlapping metal girder ($x_i < c < x_i + w_i$), ensuring an interlocking puzzle with zero continuous fault lines (furthermore, when identical parts exist, adding symmetry-breaking constraints like $x_i \le x_j$ eliminates redundant permutation branches in solver search).

Chapter 044. Implementation with WaSHI

Here is how to formulate and solve this 2D packing model using the @ohtaman/washi TypeScript mathematical modeling library:

import { Model, expr } from "@ohtaman/washi";

const model = new Model("TitanPacking2D");

// 1. Continuous coordinate variables for each part
const x = parts.map((p, i) => model.continuous(`x_${i}`, { lb: 0, ub: plateW - p.w }));
const y = parts.map((p, i) => model.continuous(`y_${i}`, { lb: 0, ub: plateH - p.h }));

// 2. Pairwise non-overlap constraints with axis-specific tight Big-M (plateW, plateH)
for (let i = 0; i < parts.length; i++) {
  for (let j = i + 1; j < parts.length; j++) {
    const d1 = model.binary(`d_${i}_${j}_left`);
    const d2 = model.binary(`d_${i}_${j}_right`);
    const d3 = model.binary(`d_${i}_${j}_below`);
    const d4 = model.binary(`d_${i}_${j}_above`);
    model.constraint(expr`${x[i]} + ${parts[i].w} - ${x[j]} + ${plateW} * ${d1} <= ${plateW}`);
    model.constraint(expr`${x[j]} + ${parts[j].w} - ${x[i]} + ${plateW} * ${d2} <= ${plateW}`);
    model.constraint(expr`${y[i]} + ${parts[i].h} - ${y[j]} + ${plateH} * ${d3} <= ${plateH}`);
    model.constraint(expr`${y[j]} + ${parts[j].h} - ${y[i]} + ${plateH} * ${d4} <= ${plateH}`);
    model.constraint(expr`${d1} + ${d2} + ${d3} + ${d4} >= 1`);
  }
}

const status = await model.solve({ solver: "highs" });
console.log("Status:", status);