『TITAN PACK』の数理モデル解説 — 2次元板金パッキングと非重複制約の線形化

1. 2次元パッキング問題（2D Packing Problem）とは

2次元パッキング問題は、与えられた母材プレート（長方形のシート）の中に、異なる寸法を持つ複数の長方形パーツを「互いに重ならず」「はみ出さず」配置する組合せ最適化問題です。板金加工、木工、半導体フロアプランニングなど実産業で広く応用されています。

すべてのパーツを隙間なくぴったり詰め込み、端材（材料ロス）を 0% にできるか判定する問題は NP 困難であることが知られています。

2. 幾何学的非重複制約の線形化（Big-M 定式化）

2つの長方形パーツ i と j（位置 (x_i, y_i)、幅 w_i、高さ h_i）が互いに重ならないための条件は、本来「論理和（OR）」を含む非線形な条件です：

混合整数線形計画法（MILP）では、4つのバイナリ変数 δ_ij,1, δ_ij,2, δ_ij,3, δ_ij,4 ∈ {0, 1} と十分大きな定数 M を用いて以下のように線形制約へ変換します：

3. 断層禁止（Fault-Line Free）の幾何学的保証

単にパーツを長方形に分割するだけでは、端から端まで貫通する直線（ギロチン切断線）が生じ、パズルが「ただの小分けの寄せ集め」になってしまいます。

TITAN PACK では、すべての垂直境界 $c \in \{1, \dots, W-1\}$ および水平境界 $r \in \{1, \dots, H-1\}$ について、少なくとも1つのパーツがその境界を跨ぐ（$x_i < c < x_i + w_i$）構造を保証するMulti-Scale Interlocking & Core Partitioning アルゴリズムを採用し、知恵の輪のように有機的に噛み合う良問を無限に生成しています。

4. WaSHI による実装コード例

TypeScript 数理最適化モデリングライブラリ @ohtaman/washi を使ってこの 2D パッキングモデルを構築するコードは以下の通りです：

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

const model = new Model("TitanPacking2D");
const M = Math.max(plateW, plateH) + 1;

// 1. 各パーツの座標変数 (連続変数)
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. ペアごとの非重複制約 (Big-M)
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(x[i].add(parts[i].w).sub(x[j]).add(d1.mul(M)).le(M));
    model.constraint(x[j].add(parts[j].w).sub(x[i]).add(d2.mul(M)).le(M));
    model.constraint(y[i].add(parts[i].h).sub(y[j]).add(d3.mul(M)).le(M));
    model.constraint(y[j].add(parts[j].h).sub(y[i]).add(d4.mul(M)).le(M));
    model.constraint(d1.add(d2).add(d3).add(d4).ge(1));
  }
}

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