# optlab — ブラウザ内 LP/MIP ソルバ 数理最適化（線形計画 LP / 混合整数計画 MIP）の問題を、**ブラウザだけで**解くツールです。 サーバ側のアプリケーションは不要で、求解はすべてブラウザ内の WebAssembly ソルバ （[HiGHS](https://highs.dev/)）で実行されます。 モデルの実体は **4 つの CSV** です。Excel で編集し、ZIP でまとめて出し入れします。 --- ## 起動 ```powershell .\start.ps1 # 既定ポート 8000 でローカル配信し、既定ブラウザを開く .\start.ps1 -Port 8100 -NoBrowser ``` `start.bat` をダブルクリックしても起動できます。`build.bat` をダブルクリックすると スタンドアロン版をビルドできます。どちらも対応する `.ps1` と同じフォルダーにあります。 PowerShell の実行ポリシーは起動プロセス内だけ迂回するため、Windows の設定は変更しません。 `file://` で直接開くことはできません。WebAssembly と Web Worker が同一オリジンの HTTP 配信を要求するためです。`start.ps1` は Python で静的配信するだけで、 アプリケーションサーバは存在しません（実体は `tool/serve.py`）。 配信は **キャッシュを無効**（`Cache-Control: no-store`）にしています。`python -m http.server` の既定のままだと `Cache-Control` が付かず、ブラウザが `app.js` をヒューリスティックに キャッシュします。編集しても**古い JavaScript が動き続け**、「直したはずの機能が出ない」 という原因の見えない失敗になるためです。 ただし no-store が効くのは「再取得したとき」だけで、**開きっぱなしのタブは再取得しません**。 そこで画面側でも、タブに戻るたびに各ファイルの `Last-Modified` を HEAD で確かめ、 変わっていればツールバーに「コードが更新されています — 再読み込み」を出します （勝手に再読み込みはしません。書きかけの表を消さないためです）。 対象ブラウザは Chromium 系（Edge / Chrome）です。 ### Windows 向けスタンドアロン版 Windows x64上で Node.js 20.12以降（Node.js 24 LTS推奨）を用意し、ビルド時に次を実行します。 ```powershell npm install npm run build:standalone ``` PowerShell スクリプトでもビルドできます（依存パッケージが未導入なら `npm ci` も自動実行）。 ```powershell .\build.ps1 # ビルド .\build.ps1 -Clean # 前回の exe と中間ファイルを削除してからビルド .\build.ps1 -Run # ビルド後に exe を起動 ``` 実行ポリシーで止まる場合は `powershell -ExecutionPolicy Bypass -File .\build.ps1` で実行してください。 エクスプローラーから起動する場合は `build.bat` をダブルクリックしてください。 `dist/optlab-windows-x64.exe` が生成されます。アプリ本体・サンプル・HiGHS WASMを 実行ファイルに埋め込んでいるため、配布先では Python や Node.js は不要です。EXEを起動すると ローカルHTTPサーバーが立ち上がり、既定のブラウザーでアプリが開きます。終了するには 起動したコンソールで Ctrl+C を押します。ポートを指定する場合は `optlab-windows-x64.exe --port 8100`、ブラウザーを自動で開かない場合は `optlab-windows-x64.exe --no-browser` を使います。指定ポートが使用中の場合は次のポートを 最大10回試します。 生成物はコード署名されていないため、配布先のWindowsでSmartScreenの警告が表示される場合があります。 --- ## モデルの形式（4 つの CSV） 文字コードは **UTF-8（BOM 付き）**、区切りは **カンマ**です。BOM 付きにしているのは、 Excel がダブルクリックで開いたときに日本語を文字化けさせない唯一の実用的な構成だからです。 ### `problem.csv` — 問題のメタ情報 `key,value` の 2 列。 | key | 必須 | 既定値 | 説明 | |---|---|---|---| | `objective_sense` | ✔ | — | `min` または `max` | | `objective_name` | | `obj` | 目的関数の名前 | | `objective_constant` | | `0` | 目的関数の定数項 | | `time_limit` | | `60` | 求解の打ち切り秒数 | | `mip_rel_gap` | | `0` | MIP の相対ギャップ許容値 | | `presolve` | | `choose` | `on` / `off` / `choose` | ### `variables.csv` — 変数 | 列 | 必須 | 説明 | |---|---|---| | `name` | ✔ | 変数名。英字または `_` で始まり、英数字と `_` のみ | | `kind` | | `continuous` / `integer` / `binary`（空欄は `continuous`） | | `lower` | | 下限。空欄は `0`。`-inf` 可 | | `upper` | | 上限。空欄は `+inf` | | `objective` | | 目的関数の係数。空欄は `0` | ### `constraints.csv` — 制約（右辺と向き） | 列 | 必須 | 説明 | |---|---|---| | `name` | ✔ | 制約名。命名規則は変数名と同じ | | `sense` | ✔ | `<=` / `>=` / `=` | | `rhs` | ✔ | 右辺の定数 | ### `coefficients.csv` — 係数（非ゼロのみ） | 列 | 必須 | 説明 | |---|---|---| | `constraint` | ✔ | `constraints.csv` に存在する制約名 | | `variable` | ✔ | `variables.csv` に存在する変数名 | | `coefficient` | ✔ | 係数 | 列名は英語が正で、大文字小文字・前後空白は無視されます。日本語の列名 （`変数名` / `種別` / `下限` / `上限` / `目的関数係数` / `制約名` / `不等号` / `右辺` / `係数`）も 読み込み時に限り受け付けます。 ### なぜこの形（正規化型）なのか 「1 行＝制約、1 列＝変数」のマトリクス型は小さな問題では読みやすい一方、変数が増えると 列が増え、Excel の列上限（16384）に当たり、疎な問題では空セルばかりになります。 Excel は「行を増やす」操作が得意で「列を増やす」操作が苦手なので、 係数を非ゼロだけ縦に持つ正規化型を選んでいます。数千変数でも破綻しません。 ### 表現上の約束 - 範囲制約 `lb ≤ ax ≤ ub` は `constraints.csv` の **2 行**で表現します（範囲型の列は持ちません）。 - `binary` の変数は上下限を `0` / `1` に強制します（別の値が書かれていれば警告します）。 - 数値は**半角のみ**です。全角数字や桁区切りカンマ（`1,000`）は、黙って読み替えず エラーとして拒否します。読み替えは静かな誤りの温床だからです。 - 同じ `(constraint, variable)` の組が 2 行あるとエラーです。合算するとモデルが 意図せず変わるため、明示的に直してもらいます。 --- ## 使い方 1. **サンプルを開く**: ツールバーのサンプル選択から 8 つのプリセットを読み込めます。 最適値はいずれも検算済みです（`tests/solve.test.js` / `tests/domain.test.js`）。 - `production_lp` — 生産計画（連続変数の LP）／最適値 **1100** - `knapsack_mip` — ナップサック（バイナリ 12 変数の MIP）／最適値 **85** - `assignment_mip` — 割当問題（バイナリ 16 変数の MIP）／最適値 **11** - `tsp_mip` — 巡回セールスマン（1 台・5 訪問先の一筆書き、MTZ 制約つき MIP）／最適値 **20.427** - `vrp_mip` — 配送計画（2 台・5 訪問先、MTZ 制約つき MIP）／`tsp_mip` と同じ地点 - `binpacking_mip` — ビンパッキング（8 荷物・容量 10）／最適値 **4 箱** - `shift_mip` — 勤務シフト表（4 人 × 7 日、日ごとの必要人数つき） - `scheduling_lp` — 工程計画（6 工程の先行関係）／最適値 **14** 2. **ZIP で保存** → Excel で編集 → **読み込み**。ZIP でも個別 CSV でも受け付けます。 ファイル名（`variables` / `constraints` / `coefficients` / `problem` の前方一致）で 自動判別し、判別できないものは手動で割り当てます。 3. **実行**（`Ctrl+Enter` でも実行）。求解は Web Worker で走るので画面は固まりません。 **中断**は常に効きます。入力エラーがあるときは実行ボタンを押せません。 4. **式**タブに目的関数と制約の数式、**結果**タブに状態・目的関数値・変数値、 **問題ビュー**タブに問題固有の結果、**ログ**タブにソルバの生ログが出ます。 実行すると結果タブへ移りますが、**式・問題ビューを開いているときはそのまま**です （画面を見ながら繰り返し解けます）。 「結果を保存」で `solution.csv`（全変数）と `summary.csv`（状態・打ち切り理由など）を 1 つの ZIP にまとめてダウンロードします。 ### 式（定式化） 変数・制約・係数の 3 表は**編集するための形**で、式は**確かめるための形**です。 係数タブを 1 行ずつ追って頭の中で式を組み立てる作業は、間違えるうえに疲れます。 式タブは同じモデルを数式に組み直して見せます（ここでは編集できません。 入力口を 2 つにすると、どちらが正本か分からなくなるためです）。 ``` 目的関数 最大化 profit = 30 chairs + 50 tables 目的関数値の内訳 制約（3 本） chairs 30 × 20 = 600 carpentry chairs + 2 tables <= 40 左辺 40 余裕 0（効いている） tables 50 × 10 = 500 finishing 2 chairs + tables <= 50 左辺 50 余裕 0（効いている） 合計 = 1100 table_demand tables <= 15 左辺 10 余裕 5 ``` - **目的関数値の内訳**は「なぜその値になったか」を係数 × 値で開きます。 合計は結果タブの目的関数値と一致します（一致しなければどちらかの組み立てが壊れています）。 - **余裕**は右辺と左辺の差です。**0 の行がその解を縛っている制約**で、 「どこを緩めれば良くなるか」はここを見れば分かります。 - 係数 1 は書きません（`1 chairs` は読みにくいため）。項が 200 を超える式は打ち切り、 打ち切ったことを明示します。 ソルバが読む LP 形式（`src/lp.js` / 「LP出力」ボタン）とは別物です。あちらは機械のための 文字列で、こちらは人のための表示です。見た目が似ていても用途が違うので共用していません。 ### 問題ビュー `solution.csv` の変数名と値の一覧は、**何を解いたのかを語りません**。`x_k1_c3_c4 = 1` が 1000 行並んでも、それが「どの車がどこを回ったか」にはなりません。問題ビューは、 モデルの構造から問題の型を見分け、その型の言葉（経路・箱・勤務表・工程表）で結果を描きます。 CSV の形式は変えていません。判定は読み込んだモデルから導くだけで、モデル側に 「私はVRPです」と書く必要はありません。 | 型 | 見せ方 | |---|---| | TSP / VRP | 拠点を中心に地点を並べた経路図と、訪問順の一覧。TSP は 1 本の一筆書き、VRP は車両ごとに色分け | | ビンパッキング | 箱ごとの詰まり具合を棒で表示。棒の幅が容量、区切りが荷物、斜線が空き | | 勤務シフト表 | 担当者 × 時間帯の勤務表。下段に必要人数と充足人数、不足は赤 | | スケジューリング | 工程ごとのガントチャート。縦の破線が全体の終了時刻 | | マッチング / 割当 | 行 × 列の対応表。選ばれた組み合わせを色で示す | | ナップサック / 選定 | 選択済み項目の一覧と、制約ごとの使用量 | | 汎用モデル | どれにも当てはまらないとき。変数・制約・結果タブで確認する | #### 判定は名前ではなく構造で行う 変数名は利用者が自由に付けられるので、名前だけで決めると**黙って型を取り違えます**。 たとえばビンパッキングと割当問題は、どちらも `x_<添字>_<添字>` のバイナリ変数と 「合計 = 1」の制約を持つので、名前では区別できません。そこで次のような構造を見ます。 - **経路**: 出発地の集合と到着地の集合が重なる（割当は両側が別物なので重ならない） - **ビンパッキング**: 箱ごとの容量制約がある（係数が 1 でない＝荷物の大きさ） - **勤務シフト表**: 時間帯ごとに「>= 必要人数」の充足制約が複数ある - **スケジューリング**: 「後工程の開始 − 前工程の開始 >= 所要時間」の 2 項制約がある **判定の根拠は画面に表示します。** 利用者が根拠を読んで「それは違う」と言えなければ、 自動判別はただの当て推量になるためです。荷物の大きさ・箱の容量・工程の所要時間も、 別表を用意させずに制約の係数と右辺から読み取っています。 #### 問題ビューから直す 問題ビューに出ている**入力の値**は、その場で直せます（直すと CSV の表に書き戻ります）。 | ビュー | 直せる値 | 書き戻し先 | |---|---|---| | 勤務シフト表 | 時間帯ごとの必要人数 | `constraints.csv` の `rhs` | | マッチング / 割当 | 行 × 列のコスト | `variables.csv` の `objective` | | ナップサック / 選定 | 項目の目的係数・制約の上限 | `variables.csv` / `constraints.csv` | **解の値（勤務の ●、選ばれた辺）は直せません。** 次に実行すれば上書きされる値なので、 編集させると嘘の操作になります。直せるのは入力だけです。 値の妥当性は表から読んだときと同じく `buildModel` が検証します（画面側で独自に弾くと 判断の基準が 2 つになるため）。書き戻し自体は `src/tables.js` の純関数で、 `tests/tables.test.js` が「画面では直ったのに CSV は古いまま」を防いでいます。 #### 外したときの逃げ道 自動判別は万能ではありません。問題ビューの右上の**「表示する型」**で手動指定できます。 指定した型にモデルが当てはまらないときは、落ちずに理由を表示して自動判別に戻せます。 「表示する型」の並びはサンプル選択と同じ順です（`DOMAIN_TYPES` が両方の正本）。 ### 表の読み方（説明） 変数・制約・係数・式・結果の各タブには、**その表が何を表しているかの説明**が付きます。 4 つの表も `solution.csv` も値しか持たず、意味は書いた本人の頭の中にしかありません。 時間が経てば本人も読めなくなるため、判定した型と変数名の形から読み方を組み立てて添えます。 ``` x_k1_d_c1 は「車両 k1 が d から c1 へ移動するなら 1、そうでなければ 0」と読めます。 0 か 1。1 にすると total_distance が 2.236 増えます。 visit_in_c1 は x_k1_d_c1 + x_k1_c2_c1 + x_k1_c3_c1 ほか（全 10 項）の合計が 1 ちょうど。 ``` **CSV に意味の列は増やしません。** 増やせば人が書き、書けば古くなり、やがて嘘をつくためです。 説明はモデルから毎回導き直すので、表を直せばその場で追従します。 推定である以上、外れることがあります。そこで次の 2 つを守っています。 - **どの型として読んでいるかを必ず併記する**（外れていれば「表示する型」で直せる） - **名前の形が型に合わないものは言い換えない**。VRP の `u_k1_c1` を 「k1 から c1 へ移動する」と訳すような取り違えを避け、種別と範囲の説明に留めます 説明は「説明を隠す」でたたむことができ、全タブに効きます。 ### 表示の上限 表と結果の表示は先頭 500 行までです。超えた分は警告を出して表示を打ち切ります。 ブラウザ上の表は「確認と微修正」のためのもので、全件編集は Excel 側の仕事です。 ### 結果の見え方 変数値は**既定で非ゼロのみ**表示します。MIP では大半の変数が 0 になり、 全件表示すると重要な行が 0 の海に埋もれるためです。CSV エクスポートは表示フィルタに 関係なく全件出力します。`summary.csv` には打ち切り理由（`time_limit` 到達など）を残します。 **時間切れの準最適解を最適解と誤認しないため**の情報です。 変数の「種別」は `variables.csv` の値をそのまま見せます。HiGHS の一発 API は binary も `Integer` として返すため（同梱の型定義でも lossy と明記されている）、 ソルバの分類を表示すると binary が integer に見えてしまいます。 ### モデルの保存 ブラウザの localStorage に、最後に読み込んだモデルを自動保存し、次回起動時に復元します。 名前を付けた保存・読み出しもできます。ただし localStorage はブラウザのプロファイルに 紐づくため、**モデルの正本は常に CSV / ZIP** です。 --- ## スコープ外（このバージョンでは作っていない） 感度分析（双対価格・reduced cost）、二次計画（QP）・非線形（NLP）、LP/MPS 形式の **インポート**、実行不可原因の特定（IIS）、数千行を全件編集できるグリッド、 サーバ側での求解。 問題ビューは**結果を読むための表示**であって、地図や現実の座標ではありません。 経路図の地点配置はモデルから作った概略で、緯度経度は扱いません（CSV に座標を持たせる 仕組みがないため）。地点が 40 を超える場合は図を省き、経路の一覧だけを出します。 LP 形式の**エクスポート**はあります。求解のために内部で LP テキストを生成しているので、 追加コストがほぼゼロで、かつ「他のソルバで検算する」手段が手に入るためです。 --- ## 開発 ### 構成 ``` index.html 画面（ツールバー＋問題設定＋6タブ） app.js UI とアプリケーション状態（ESM） style.css solver.worker.js HiGHS を呼ぶ Worker（classic worker） src/csv.js CSV の解析・生成（行番号を保持する） src/model.js CSV → モデル、および検証 src/lp.js モデル → CPLEX LP 形式テキスト src/domain.js モデル → 問題クラスの判定と問題固有データ（DOMに触れない） src/explain.js モデル → 表と結果の読み方・式（DOMに触れない） src/tables.js 画面で直した値 → CSV表への書き戻し（DOMに触れない） src/zip.js ZIP の読み書き（書きは store、読みは store と deflate） vendor/highs/ HiGHS 1.15.3（WASM, MIT）。求解時の唯一の外部コード samples/ プリセット 8 種 tests/ node:test による単体テスト（追加依存なし） tool/fetch_vendor.sh vendor/ を再取得する tool/serve.py 静的配信（キャッシュ無効・wasm の MIME 明示） tool/make_samples.mjs samples/ を定義から生成する tool/verify_browser.mjs 実ブラウザでの通し確認（puppeteer-core が必要） tool/export_sample_lp.mjs samples/ を LP 形式で書き出す（検算用） tool/crosscheck_lp.py 書き出した LP を Python 側 HiGHS で読み直して検算 ``` 問題ビューの判定ロジックを `src/domain.js` に分けているのは、**当たっているかをテストできる ようにするため**です。描画と混ざっていると DOM なしでは呼べず、「名前が似ているから たぶん合っている」で済ませることになります。 ### テスト ```bash npm test # node --test（86件） ``` 追加の依存はありません。Node.js 18 以降が必要です。 テストの中心は **`src/lp.js`（LP 生成器）** です。ここは符号の向き、`>=` 制約、負の下限、 `Bounds` / `Generals` / `Binaries` セクションの書き方を 1 つ間違えると、エラーにならずに **「それらしいが間違った最適解」**を返す部品で、手動確認では気づけません。 守り方は 2 段構えです。 1. **期待テキストとの突き合わせ** — 上下限のすべての形、定数項、折り返し、制約の順序。 2. **総当たりとの突き合わせ** — `knapsack_mip`（2^12 通り）と `assignment_mip`（2^16 通り）を モデルから直接評価して最適値を出し、ソルバの答えと比べます。総当たりは CSV から作った モデルを見て、ソルバはそこから生成した LP テキストを解くので、**生成器の誤りが露見します**。 問題ビューの判定は `tests/domain.test.js` が守ります。ここで効くのは **取り違えの回帰テスト**です。ビンパッキングを割当問題と、スケジューリングをナップサックと 呼んでしまう誤りは、エラーを出さずに「違う問題の答え」として画面に出てしまうため、 具体的な取り違えをそのままテスト名にしています。 ### ブラウザでの通し確認 単体テストでは見えない部分（Worker、WASM の読み込み、ファイル入出力、画面遷移）は 実ブラウザで確認します。 ```bash node tool/verify_browser.mjs ``` `puppeteer-core` はこのリポジトリに同梱していません。別の場所にあるものを使う場合は `PUPPETEER_HOST_DIR` に `node_modules` を持つディレクトリを、ブラウザを明示するなら `OPTLAB_BROWSER` に実行ファイルを指定します。 ### LP 出力の相互運用の確認 書き出した LP ファイルを、標準的な HiGHS のツールがそのまま読めるかを確かめます。 ```bash python -m venv tool/_venv tool/_venv/Scripts/python.exe -m pip install highspy # Windows tool/_venv/Scripts/python.exe tool/crosscheck_lp.py ``` 同じソルバ実装なので「別ソルバによる検算」ではありません。確かめているのは **エクスポートした LP が他のツールと相互運用できる**ことです。 ### vendor の更新 ```bash sh tool/fetch_vendor.sh # 既定は package.json に記録されたバージョン sh tool/fetch_vendor.sh 1.16.0 ``` 同梱物の出自が不明になるのを防ぐため、取得はスクリプト経由にしています。 HiGHS のライセンスは MIT（`vendor/highs/LICENSE`）です。 ブラウザは UMD 版（`highs.js`、Worker の `importScripts` から）、テストは ESM 版 （`highs.mjs`）を読みます。指す WASM は同じです。 --- ## 困ったとき | 症状 | 見るところ | |---|---| | ページが開かない | ブラウザのプロキシ設定で `127.0.0.1` / `localhost` が除外されているか。社内プロキシ経由になると到達できません | | ポートが使用中 | `start.ps1` は 10 個ぶん先まで自動で探します。`-Port` で明示もできます | | Excel で開くと文字化けする | ダウンロードした CSV は UTF-8 BOM 付きです。BOM を落として保存し直すと化けます | | 変数名が「使えません」と怒られる | Excel が `1-2` を日付に、`0012` を `12` に変換していないか。英字始まりの名前にしてください | | 求解が終わらない | `time_limit`（既定 60 秒）で必ず戻ります。手動の「中断」も常に効きます | | 数千行を編集したい | 画面の表は先頭 500 行までです。ZIP で保存して Excel で編集してください | | 問題ビューが真っ白 | 開いたままのタブが古い `app.js` を掴んでいます。`Ctrl+Shift+R` で再読み込みしてください。ツールバーに**「コードが更新されています — 再読み込み」**が出ていたら、それを押せば同じです。再読み込みしても白いままなら不具合なので、ビュー内に出る理由とコンソールの詳細を添えて知らせてください | | 問題ビューに図が出ない | 図は既知の型（経路・箱詰め・シフト・工程・割当・選定）だけです。当てはまらないモデルは「この型に合う専用の表示はありません」と出ます（判定の根拠もそこに出ます） | ## Cloudflare（Workers）へのデプロイ 公開に必要なファイルだけを `dist/web/` に集め、Wrangler で静的アセットとして配信します。 ```powershell npm install npx wrangler login # 初回のみ npm run dev:cf # ローカル確認（http://127.0.0.1:8787） npm run deploy # dist/web/ を生成して wrangler deploy ``` Workers BuildsでGit連携する場合、Wrangler設定の `[build]` はCloudflareのBuild commandとして使われません。Workers & Pages の対象Workerで **Settings > Builds** を開き、次のように設定してください。 - Root directory: リポジトリのルート（空欄または `.`） - Build command: `npm run build:cf` - Deploy command: `npm run deploy` `build:cf` が公開用ファイルを `dist/web/` に集め、Deploy command が Wrangler で配信します。`wrangler.toml` の `[build]` はローカルの `wrangler dev` / `wrangler deploy` 用です。Wrangler設定としてTOMLは引き続きサポートされています。 `/` が本体アプリ、`/lp/` がランディングページです。設定は `wrangler.toml`、配信対象は `tool/stage-cf.mjs` にあります。 ## Windows 単体実行ファイル Node.js の SEA で、アプリ一式を 1 つの exe に埋め込みます（実行側に Python / Node.js は不要）。 ```powershell npm run build:standalone # dist/optlab-windows-x64.exe を生成 .\build.ps1 [-Clean] [-Run] # 上記の PowerShell ラッパー .\dist\optlab-windows-x64.exe [--port 8000] [--no-browser] ``` ダブルクリックでローカルサーバーが起動し、ブラウザで開きます（終了は Ctrl+C）。ソルバーはブラウザ内で動くため外部通信はありません。 ## サンプル配布モード `config.js` の `DEFAULT_MODE` を `"sample"` にするか、URL に `?mode=sample` を付けると、CSV/ZIP の読み込み（ドラッグ&ドロップ含む）、ZIP保存、ブラウザ内保存が使えなくなります（サンプルの選択・編集・実行・LP出力は可能）。`?mode=full` で全機能に戻ります。LP の埋め込みデモは `?mode=sample` で開いています。