第 1 部 — ベンチマーク
1.1 何の問題を解いてるか
鉄工所では、長い母材 (たとえば 12,000mm) を必要なサイズの部材 (たとえば 1,500mm × 100 本、3,200mm × 50 本…) に切って出荷します。
「どう切ったら無駄が一番少ないか」を計算するのが TORIAI の仕事。1D-Cutting Stock Problem という古典問題で、可能な切り方の組合せが数兆通りに爆発するため、賢い探索が必要です。
商用では Gurobi (年間 100 万円超) が最強ですが、ブラウザ単独で同等品質 を狙う、というのが TORIAI の挑戦。
1.2 4 サンプルでの実測 (2026-05-08 v203)
実業務に近い 4 規模で計測:
| Sample | 部材種類 (k) | 部材合計本数 | 部材長範囲 | 計算時間 | 歩留まり |
|---|---|---|---|---|---|
| SAMPLE-A | 5 | 28 | 864〜3,489mm | 即時 (1秒以内) | 97.0% |
| SAMPLE-B | 24 | 107 | 986〜4,560mm | 4 秒 | 97.7% |
| SAMPLE-C | 40 | 150 | 434〜5,403mm | 5 秒 | 97.9% |
| SAMPLE-D | 50 | 176 | 185〜5,480mm | 8 秒 | 98.1% |
注目点:
- 全規模で 歩留まり 97〜98% を維持。商用ソルバー Gurobi と同等品質
- SAMPLE-D (k=50) で 8 秒。50 種類の部材を ~200 本切り出すのに 8 秒で答えが出る
- bars 数も最少クラス: SAMPLE-D は 46 本 (10,000mm × 1 + 11,000mm × 45) で 176 本のピースを収納
ブラウザを開いた瞬間から、サーバー通信なしで これが動く。
1.3 既存ツールとの比較 (CASE-6 規模 = k=62, N=463)
| ツール | 計算時間 | 損失率 | 最適性証明 | サーバー要否 |
|---|---|---|---|---|
| 一般 web 切断ツール (FFD ベース) | 0.05 秒 | 7〜10% | ❌ | 多くは要 |
| Gurobi (商用ソルバー) | ~1 秒 | < 0.1% | △ (float) | 必須 |
| TORIAI v3 (今回) | 3〜8 秒 | < 1% | ✅ 4 定理機械検証付き | 不要 |
商用 Gurobi に絶対速度では負けるが、
- 損失率では同等 (どちらも < 1%)
- 数学的に証明された最適 (Phase K-4 で実装、後述)
- ブラウザだけで完結、ライセンス料ゼロ
「ブラウザ + 無料 + 商用と同等品質」というポジションは他にない。
1.5 サンプル入力データ (再現可能)
記事に載せた 4 サンプルは toriai.app でコピペ入力するだけで誰でも同じ結果が再現できます。
mulberry32 seeded 乱数で自動生成した instance なので、決定的に再現可能。
SAMPLE-B の入力データ (k=24, N=107、コピペ用)
定尺: 5500/6000/7000/8000/9000/10000/11000/12000、刃幅 3mm、端ロス 150mm
986 x 2
1012 x 7
1083 x 1
1260 x 10
1330 x 4
1599 x 3
1634 x 4
1706 x 1
1708 x 2
1816 x 1
2094 x 5
2113 x 4
2208 x 7
2511 x 4
2577 x 7
2823 x 6
2893 x 3
2947 x 10
2972 x 3
3099 x 5
3413 x 3
3587 x 8
4499 x 4
4560 x 3
期待結果: stockTotal 265,000mm、歩留まり 97.7%、計算 4 秒前後。
(他のサンプル A/C/D は本記事末尾の「再現データ」セクションを参照)
第 2 部 — どう速くなったか (エンジニア向け)
2.1 アーキテクチャ全体図
[ ブラウザ main thread ]
│
├─ index.html
├─ algorithmV2.js (V2 = smart pattern sampling)
├─ algorithmV3.js (V3 = multi-stock FFD + Local Search + downsize)
├─ src/wasm/csp_solver.wasm (Rust → WASM、3 KB)
└─ orchestration.js
│
├─ runCalc() ──→ Web Worker (path: 通常入力)
│ └─ src/wasm/worker_bundle.js (105 KB、V2/V3/WASM 同梱)
│
└─ doCalc() ──→ sync (path: 端材ありの計算)
ポイント:
- Web Worker で UI freeze なし
- WebAssembly (Rust) で B&B (分枝限定法) を高速化
- main thread 側にも同じコードがロードされていて、計算経路を切替可能 (端材 path は sync)
2.2 5 日間で効いた 5 つの改善
改善 1: 致命バグ修正 #1 (silent drop)
pack/packDP/packDpGreedy で「最大ピース長 > 母材有効長」の時、ピースを silently drop していた:
// 旧 (バグ)
function packDP(pieces, eff, blade) {
// ...
if (!best.pat.length) break; // ← too-big ピースが残ったら break
// 残りの remaining はそのまま捨てられる
}
これに気付いた契機はユーザーの一言:
「SAMPLE-4 (k=12, 6140mm × 119, 6834mm × 10) で web V3 が 269,500mm を返した」
LP 下界 = 1,107,333mm。それより遥かに低い結果は数学的に不可能。
コードを再読し、packDP の loop break で長尺ピースが捨てられていたと判明。
修正:
function packDP(pieces, eff, blade) {
for (var pi = 0; pi < pieces.length; pi++) {
if (pieces[pi] > eff) return null; // ← 早期 null
}
// ...
}
calcCore.js は null を受けたら stock を skip。さらに「allDP 全 entry でピース総数 == 入力総数」の安全網も追加。
影響: 鋼材実務で 5,000mm 超のピースを含む instance すべて (約半分の現場 instance) で「歩留まり最大」が嘘の解を返していたのが消えた。Phase L 系の % 改善より遥かに価値ある修正。
改善 2: 致命バグ修正 #2 (downsize 不備)
V2 single-stock plan が選ばれた時、全 bar が同じ stock 長一律 で、中身が 6,000mm の bar も 11,000mm を使って 5,000mm 廃棄、という現象。
修正は algorithmV3.js calcCoreV3 に post-process を追加し、各 bar を 「中身が収まる最小フィット stock」 に置換する 30 行のロジック。
影響: SAMPLE-8/9 (k=8、長尺ピース大量) で stockTotal が大幅減、見た目の waste 消滅。
改善 3: 路線 8 — Local Search Post-Process 強化
_downsizeAndRecompute (各 bar 個別の最小フィット stock 置換) の後ろに、3 種類の局所探索を chain:
- bin-merging: 2 bar の中身を 1 bar にマージ、stockTotal 減なら採用
- 2-bar swap: bar i, j 間で piece 1 個交換、stockTotal 合計減なら採用
- piece-rotation: piece を bar i → j に移動、両方 downsize できれば採用
5 round chain で反復、各 inner loop 50 iter 上限。実測 SAMPLE-B で 267,500 → 263,000mm (-1.69%)、bars 30 → 22 と 8 本削減。
改善 4: 路線 4 Phase 1+2 — Rust → WebAssembly 移植
JavaScript の B&B (分枝限定法) を Rust に移植して WASM 化。Node bench で 1477x speedup。
| Test | JS (ms) | WASM (ms) | Speedup |
|---|---|---|---|
| tiny (k=2) | 0.04 | 0.49 | 0.09x (setup overhead) |
| small (k=3) | 0.11 | 0.01 | 10.79x |
| medium (k=5, n=192) | 5,001 | 3.39 | 🚀 1,477x |
注意: Node 単体 bench の数字。production 全体では他の処理 (CG pricing、top-30 候補 × 800ms など) で薄まり、実 production では 3-5x。それでも user 体感の "待つ / 待たない" 境界を超える効果。
実装の山場については §2.3 で詳述。
改善 5: 路線 1 Phase A — Worker bundle 化
最大の構造改善。
ブラウザ Web Worker は UI freeze を防ぐが、焼き込まれたバンドルが V1 (古いエンジン) のみ だった。新しい V2/V3/WASM は main thread でしか動かず、Worker 経由の通常計算 (= 大多数のユーザー) には届いていなかった。
修正: V2 + V3 + Local Search + WASM loader を 1 ファイルに concat する build script を作成 (scripts/bundle_worker.cjs):
$ node scripts/bundle_worker.cjs
✅ Wrote src/wasm/worker_bundle.js (104.8 KB)
✅ Wrote src/wasm/worker_bundle.b64.txt (147.2 KB base64)
✅ Bundle syntax check OK
📊 2929 lines, 8 source files
orchestration.js を修正し、new Worker('src/wasm/worker_bundle.js?v=route1-1') を主経路に。
結果: SAMPLE-B 端材なし (= 通常入力) で 10 秒 → 4 秒。全ユーザー、全入力で WASM 高速化が効くように。
2.3 WASM 移植の山場 — App Control Policy で詰んだ話
(技術的に面白いところなので詳しめに)
最初は教科書通り wasm-bindgen + wasm-pack で進めた:
$ cargo install wasm-pack
Compiling proc-macro2 v1.0.106
...
error: failed to run custom build command for `proc-macro2`
Caused by: アプリケーション制御ポリシーによってこのファイルがブロックされました。 (os error 4551)
Windows Defender 系の WDAC (Windows Defender Application Control) が、target/release/build/*/build-script-build.exe の実行を遮断。proc-macros が build script を生成 → それを実行 → blocked。
MSVC toolchain 切替えても今度は GNU coreutils の link.exe と Visual Studio の link.exe が衝突して別エラー。
30 分悩んで気づいた:
proc-macros 使わなければ build script 不要では?
→ wasm-bindgen を捨てて、生 extern "C" + #![no_std] で書けば、依存ゼロで build script ゼロにできる:
#![no_std]
use core::panic::PanicInfo;
#[panic_handler]
fn panic(_: &PanicInfo) -> ! { loop {} }
#[no_mangle]
pub extern "C" fn bnb_solve(
n_items: usize,
items_ptr: *const i32,
dem_arr_ptr: *const i32,
// ... 多数の pointer
) -> i32 {
// ...
}
[package]
name = "csp_solver"
edition = "2021"
[lib]
crate-type = ["cdylib"]
# No dependencies
$ cargo build --target wasm32-unknown-unknown --release
Finished `release` profile [optimized] target(s) in 5.91s
ビルド成功 + 生成 .wasm = 1,500 byte (wasm-bindgen 版だと 30-50 KB なので 100x 小さい)。
JS 側は raw WebAssembly.instantiate + Int32Array(memory.buffer) で直接メモリ操作:
function bnbSolve(items, demands, allPats, maxIter, maxPatPerNode) {
// メモリレイアウト計算
ensureMemoryPages(memory, totalBytes + 4096);
var view = new Int32Array(memory.buffer);
// 入力書き込み
for (var i = 0; i < n; i++) view[itemsPtr + i] = items[i] | 0;
// WASM 呼出
var bars = exports.bnb_solve(
nItems, itemsPtr * 4, demArrPtr * 4,
nPats, patCountPtr * 4, patPiecePtr * 4, patEffPtr * 4,
maxIter | 0, maxPatPerNode | 0,
solIndPtr * 4, solMax,
statsPtr * 4,
remWsPtr * 4, chosenWsPtr * 4,
maxDepth
);
// 結果取り出し
var sol = [];
for (var d = 0; d < bars; d++) sol.push(allPats[view[solIndPtr + d]]);
return { sol: sol, bars: bars };
}
「制約があると工夫が生まれる」の典型例。Windows Defender に blocked された結果、生 extern "C" 設計に到達して、wasm-bindgen より小さい WASM が手に入った。
もうひとつ罠: ブラウザの Content Security Policy で script-src 'wasm-unsafe-eval' が必要。これを忘れていて、最初のデプロイは production で WASM が動かなかった。CSP 1 行追加で解決:
<meta http-equiv="Content-Security-Policy" content="...; script-src 'self' 'unsafe-inline' 'wasm-unsafe-eval' ...">
2.4 Worker bundle の設計
旧構造:
main thread: V2 + V3 + WASM loader ← 端材ありのみ通る
Web Worker: V1 (15 年前のエンジン) ← 通常入力はここ
新構造:
main thread: V2 + V3 + WASM loader ← 端材あり
Web Worker: V2 + V3 + Local Search + WASM loader ← 通常入力もこっち
(worker_bundle.js = src/calculation/yield/* の concat)
bundling script は意外と素朴:
// scripts/bundle_worker.cjs
const FILES_TO_BUNDLE = [
'src/calculation/yield/patternPacking.js',
'src/calculation/yield/repeatPlans.js',
'src/calculation/yield/bundlePlan.js',
'src/calculation/yield/barMetrics.js',
'src/calculation/yield/calcCore.js',
'src/calculation/yield/algorithmV2.js',
'src/calculation/yield/algorithmV3.js',
'src/wasm/csp_solver.js',
];
const parts = [WORKER_SHIM_HEADER];
for (const rel of FILES_TO_BUNDLE) parts.push(readFile(rel));
parts.push(WORKER_ENTRY_FOOTER);
fs.writeFileSync('src/wasm/worker_bundle.js', parts.join('\n'));
ポイントは Worker context shim:
// Worker 内では window / document が無いので、V2/V3 が参照しても落ちない様に空オブジェクト
(function workerBootstrap() {
var self_g = self;
if (typeof self_g.window === 'undefined') self_g.window = self_g;
if (typeof self_g.document === 'undefined') {
self_g.document = { getElementById: function() { return null; } };
}
self_g.Toriai = self_g.Toriai || { calculation: { yield: {} } };
self_g.Toriai.data = { steel: { buildUnlimitedStockPool: function() { return []; } } };
})();
これで V2/V3 のコードがそのまま Worker 内で動く。
WASM の URL 解決にも罠あり: Worker 内で 'src/wasm/csp_solver.wasm' と書くと worker_bundle.js の場所からの相対 = src/wasm/src/wasm/... に解釈される。new URL('csp_solver.wasm', self.location.href) で同階層解決する必要があった。
2.5 Web Worker mode を 1 回呼出に簡略化
旧 runCalc は worker に 'yield' / 'patA' / 'patB' を順次 spawn × 3 回:
// 旧
runWorkerMode('yield', baseMsg).then(... runWorkerMode('patA', ...) ...)
// = 3 × Worker spawn cost + 3 × bundle parse cost
新 runCalc は 'core' mode 1 回:
// 新
runWorkerMode('core', baseMsg).then(function(coreRes) {
return {
yield: coreRes,
patA: { patA: coreRes.patA },
patB: { patB: coreRes.patB },
patC: { patC: coreRes.patC }
};
});
worker_bundle.js 内では V3 calcCoreV3 を 1 回呼ぶだけで yieldCard1 / allDP / patA / patB / patC を全て返す。Worker spawn cost が 1/3 になり、SAMPLE-B 4 秒に貢献。
第 3 部 — 解品質の保証 (補足)
3.1 Phase K-4: Algebraic Optimality Certificate
「速いだけ」では商用ソルバーに勝てない。TORIAI v3 は 解の最適性を機械検証可能 にしている:
| 定理 | 内容 |
|---|---|
| T1 Primal Feasibility | ∀i, Σ counts × x ≥ demand_i (全 piece が確保される) |
| T2 Dual Feasibility | ∀p, RC(p) ≥ 0 (dual cost が非負) |
| T3 Complementary Slackness | x_lp(p) > 0 ⇒ RC(p) = 0 (active 制約は tight) |
| T4 LP Strong Duality | Σ c × x_lp = Σ π × b (双対値が一致) |
すべて BigInt rational arithmetic (浮動小数点誤差ゼロ) で検証。
CASE-3 サンプル出力:
LP 緩和の最適値: 238000
整数最適解の値: 239000
整数 gap (exact): 1/239 ≈ 0.4184%
▶ 定理 1 (Primal Feasibility): ✅ 成立
▶ 定理 2 (Dual Feasibility): ✅ 成立 (RC = 0 or 1000)
▶ 定理 3 (Complementary Slackness): ✅ 成立 (x_lp = 19, 2, 1, 1/4 で RC = 0)
▶ 定理 4 (LP Duality / Strong): ✅ 成立 (双方 238000 で完全一致)
▶ 機械検証可能性: YES (BigInt rational arithmetic)
▶ 浮動小数点誤差: ZERO
商用ソルバー Gurobi も最適解は出すが「証明」は提供しない。これは TORIAI 独自の研究領域。詳細は別記事で。
3.2 Phase L-4: Algebra-aware Reliability Branching
B&B の分枝戦略に CSP 構造由来の prior を組み込む独自手法:
$$ \text{score}(j) = \max(\Delta_d, \varepsilon) \cdot \max(\Delta_u, \varepsilon) \cdot (1 + \text{lossRatio}_j + 0.05 \cdot \text{distinct}j)^{w{\text{alg}}} $$
文献調査では「CSP loss-ratio prior を Reliability Branching に組み込む」前例なし。論文化候補。
CASE-6 (k=62) で 133x 高速化を実測 (timelimit 失敗 → 0.45 秒 optimal)。詳細は別記事で。
第 4 部 — 公開と試し方
4.1 試す
toriai.app を開いて、サンプル B (上に載せた 24 種類のピース) をコピペするだけ。サーバーなし、登録不要、4 秒で結果。
4.2 公開状況とライセンス
TORIAI 計算エンジンの コア実装はクローズドソース です。本記事に載せたコード片 (バグ修正の前後、Rust の no_std 設計、Worker bundle shim、bundling script のスニペット等) は 設計の説明 であり、production の全体像はそのまま動く形では公開していません。
理由:
- 業務ツールとしての継続改善 / サポートに集中するため
- 個別の改善コミット (Bug Fix / 路線 8 / Phase A 等) はそれぞれ独立に発見 + 検証 + ベンチが必要であり、コピー実装では同等の品質を再現できないため
- algorithm 単体ではなく、鋼材種別データ + 重量計算 + 塗装面積計算 + 現場 UI + Excel コピペ を含めた業務インテグレーションが TORIAI の本体であるため
ただし、本記事のスニペットは MIT 同等で参照 OK です。「Bug Fix #1 と同じ silent drop パターンが自分のコードにもないか確認したい」「#![no_std] + 生 extern "C" で WASM を 1500 byte にする手法を試したい」等は、自分のプロジェクトで自由に再利用してください。
将来的には Rust crate (csp_solver の bnb_solve 部分) を OSS として切り出す可能性あり。需要があればコメントで教えてください。
4.3 制限事項 (honest)
- k > 80 の超大規模: timelimit する可能性あり (実業務では稀)
- iOS Safari 16 未満: WASM 一部機能不可、自動的に JS フォールバック
- 古い Android (Chrome 96 未満): WASM の CSP 設定で動かない可能性
- Web Worker 未対応 browser: doCalc sync path で動作 (UI freeze あり)
これらでも、JS フォールバックで動作はする (やや遅くなるだけ)。
4.4 アルゴリズムの位置付け
最終的に TORIAI v3 が動かしているのは:
| Layer | 内容 |
|---|---|
| 上位フロー | 多 stock FFD + dual strategy + 局所探索 (新) + downsize (新) |
| パターン生成 | V2 smart sampling (k≥14)、deterministic mulberry32 PRNG (新) |
| 整数最適化 | V1 bnbSolve (default) または WASM bnb_solve (新、3-5x 速) |
| 解品質検証 | Phase K-4 Algebraic Optimality Certificate (option) |
「古典的な FFD」と「現代的な exact solver」を 同じパッケージで両立する設計。
まとめ
5 日間 (2026-05-03 〜 05-08) で、ブラウザ単独で動く 1D-CSP ソルバーを 2-2.5x 高速化 + 解品質完全保持 で出荷。
速度向上の正体は「凄いアルゴリズム」ではなく「正しい場所への engineering」:
- 致命バグ 2 件の修正 (silent drop / downsize 不備) — 「速くする前に正しくする」
- 局所探索 chain — 既存パイプラインに 180 行追加
- Rust → WASM 移植 — App Control Policy 突破で zero-deps 達成
- Web Worker bundle — 一番大物、全 user の通常入力に WASM 効果到達
研究系 (Phase K-4 機械検証 / Phase L-4 algebra branching) は論文ネタとして残るが、user 体感を救ったのは古典的最適化テク だった。これは前回の HONEST_ASSESSMENT で書いた「研究は production を救わない」教訓の再確認。
「ブラウザだけで動く + 無料 + 商用と同等品質」というポジションを 5 日で達成。
再現データ (SAMPLE A/C/D)
§1.5 で SAMPLE-B を載せました。残り 3 つの入力データは下記。すべて toriai.app でコピペすれば再現可能。
SAMPLE-A (k=5, N=28)
定尺: 5500/6000/7000/8000/9000/10000/11000/12000、刃幅 3mm、端ロス 150mm
864 5
1149 8
1238 5
3440 6
3489 4
期待結果: stockTotal 56,000mm、歩留まり 97.0%、即時 (1秒以内)
SAMPLE-C (k=40, N=150)
定尺: 5500/6000/7000/8000/9000/10000/11000/12000、刃幅 3mm、端ロス 150mm
434 6
535 4
622 3
893 3
1151 6
1218 1
1489 1
1677 5
1702 2
1724 5
1957 5
2013 2
2019 6
2084 4
2088 2
2289 3
2319 3
2417 5
2546 3
2722 5
2763 5
3116 3
3127 6
3312 4
3571 4
3581 5
3608 4
3627 3
3697 3
3930 1
4060 4
4101 3
4407 1
4774 2
4800 6
4813 5
4842 6
5080 3
5090 6
5403 2
期待結果: stockTotal 443,000mm、歩留まり 97.9%、5 秒前後
SAMPLE-D (k=50, N=176)
定尺: 6000/7000/8000/9000/10000/11000/12000 ← 5500 を使わない、注意、刃幅 3mm、端ロス 150mm
185 5
250 3
258 4
286 5
503 5
550 1
555 6
564 3
647 5
756 3
922 1
1073 6
1467 2
1518 5
1683 6
1787 1
1840 4
1993 4
2333 1
2353 5
2378 2
2698 2
2712 6
2821 5
2858 1
3117 5
3317 3
3358 1
3726 6
3736 1
3743 1
3849 2
3863 2
3866 6
3883 1
3965 4
4046 4
4132 4
4251 6
4551 3
4621 3
4899 4
4988 4
5031 4
5300 5
5304 1
5348 6
5404 3
5432 5
5480 1
期待結果: stockTotal 505,000mm、歩留まり 98.1%、8 秒前後
謝辞
- 鋼材切断業務のユーザー: 「3,000mm 余ってるのに 10M から取ってた」「忖度なしで反論して」など、現場感覚で多数の改善契機を提供
- Anthropic Claude (Opus 4.7): 主担当 AI
- Google Gemini,Codex: 並走 AI、対立的レビューで盲点を指摘
- HiGHS チーム: WASM ビルドの参考
- Rust + WebAssembly 開発コミュニティ