For developers

1次元カッティングストック問題

必要な長さの部品一式を、最小本数の定尺材から切り出す方法、これが1次元カッティングストック問題です。古くからある、真に困難な最適化問題です。ここでは、この問題の内容、なぜ総当たり攻撃が通用しないのか、そしてこのサイトの背後にあるAPIを含め、実際にどのように解決されているかを説明します。

1次元カッティングストック問題とは何か

固定長の母材（例えば6000 mmのバー）と、それぞれに長さと数量が指定された必要部品のリストが与えられます。切断パターンとは、1本の母材をいくつかの部品に切り分ける一方法です。残った長さはすべて無駄になります。問題は、どのパターンを、それぞれ何本のバーで実行するかを選択し、すべての必要部品を生産しつつ、母材の総本数、つまり総無駄量を可能な限り最小にすることです。1次元なのは、長さだけが問題だからです。刃は断面全体を横切るため、幅や形状は組み合わせに影響しません。

1次元ビンパッキング問題と、それがNP困難である理由

カッティングストック問題は1次元ビンパッキング問題を一般化したものです。ビンパッキング問題は、異なるサイズの品目を最小数の固定サイズ容器に詰めることを問います。カッティングストック問題は、品目が大量に繰り返される場合の同じ問いであり、個々の品目ではなくパターンについて考えます。ビンパッキング問題は古典的なNP困難問題の一つであり、その決定版である「これらの品目をk個の容器に収めることができるか」はNP完全です。カッティングストック問題もその困難性を受け継いでいます。

理由は組み合わせ爆発です。異なる切断パターンの数は部品サイズの種類に応じて指数関数的に増加し、さらにそれらのパターンに数量を割り振る方法は爆発的に増えます。保証された最適解を入力に対して多項式時間で発見する既知のアルゴリズムは存在せず、P=NPでない限り、今後も現れないでしょう。そのため、実際のソルバーはすべてを列挙するのではなく、どの可能性を排除できるかを賢く判断します。

実際の解決方法

LinearCuttingの解決方法

LinearCuttingは次のスタックを実行します。まず高速なヒューリスティックで即座に実行可能な計画を立て、次に下界主導の探索で改善を続けます。下界と一致する（証明可能な最適解であり、その旨が通知されます）か、時間予算を使い果たして見つかった最良の計画を返すまで続きます。物理的な側面もモデル化します。すべての切断における切り代、端部のトリム、定量の端材、余分に消費する角度切りなどです。なぜなら、刃を無視した計画は単に準最適であるだけでなく、間違っているからです。ベンチマークジョブは公開されており、他のツールと結果を比較できます。

JSON APIとして公開されています。部品と母材の情報を送信すると、レイアウト、無駄、段取り回数、そして計画が最適下界に達したかどうかを含む、検証済みの切断計画が返されます。Python (pip install linearcutting) と JavaScript または TypeScript (npm install linearcutting) の公式クライアントがあり、どちらの言語でも数行で呼び出せます。