棒切断問題

$M$ 本の同一長さの棒材（長さ $L$）が与えられ、$N$ 個の注文がペア $(l_j,c_j)$ (0≤j≤N−1) で指定されていると仮定する。ここで $l_j$ は注文 $j$ の要求長、$c_j$ は要求数量である。棒材切断問題は、$M$ 本の棒材をどのように切断すれば全ての注文を満たせるかを決定することを目的とする。

一般に、棒切断問題は使用棒材数を最小化する最適化問題として定式化される。簡略化のため、本例では$M$本の棒材で全$N$注文を満たせるか否かを判定する実現可能性問題を検討する。

$x_{i,j}$ ($0\leq i\leq M-1, 0\leq j\leq N-1$) を、棒 $i$ から切断された注文 $j$ の部品数を表す。以下の制約を満たす必要がある。

注文制約:

各注文 $j$ について、全棒材に割り当てられた部品の総数は $c_j$ に等しくなければならない：

\[\begin{aligned} \sum_{i=0}^{M-1}x_{i,j} &= c_j & &(0\leq j\leq N-1) \end{aligned}\]

棒の制約

各棒材 $i$ について、割り当てられた部品の総長は $L$ を超えてはならない：

\[\begin{aligned} \sum_{j=0}^{N-1}l_jx_{i,j} &\leq L & &(0\leq i\leq M-1) \end{aligned}\]

QUBO++プログラム

以下のQUBO++プログラムは、長さ$L=60$のバー$M=6$本と以下の順序$N=4$を用いて実現可能な切断計画を見つける：

順序 $j$	0	1	2	3
長さ $l_j$	13	23	8	11
数量 $c_j$	10	4	8	6

この棒切断問題に対するQUBO++プログラムは以下の通りです：

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  const int L = 60;
  const qbpp::Vector<int> l = {13, 23, 8, 11};
  const qbpp::Vector<int> c = {10, 4, 8, 6};
  const size_t N = l.size();
  const size_t M = 5;

  qbpp::Vector<qbpp::Vector<qbpp::VarInt>> x(M);
  for (size_t i = 0; i < M; i++) {
    for (size_t j = 0; j < N; j++) {
      x[i].push_back(0 <= qbpp::var_int("x[" + qbpp::str(i) + "][" +
                                        qbpp::str(j) + "]") <= c[j]);
    }
  }

  auto order_fulfilled_count = qbpp::vector_sum(qbpp::transpose(x));
  auto order_constraint = order_fulfilled_count - c == 0;

  auto bar_length_used = qbpp::expr(M);
  for (size_t i = 0; i < M; i++) {
    bar_length_used[i] = qbpp::sum(x[i] * l);
  }
  auto bar_constraint = 0 <= bar_length_used <= L;

  auto f = qbpp::sum(order_constraint) + qbpp::sum(bar_constraint);
  f.simplify_as_binary();

  auto solver = qbpp::easy_solver::EasySolver(f);
  solver.time_limit(10.0);
  solver.target_energy(0);
  auto sol = solver.search();
  for (size_t i = 0; i < M; i++) {
    std::cout << "Bar " << i << ":  ";
    for (size_t j = 0; j < N; j++) {
      std::cout << sol(x[i][j]) << "  ";
    }
    std::cout << " used = " << sol(bar_length_used[i])
              << ", waste = " << L - sol(bar_length_used[i]) << std::endl;
  }
  for (size_t j = 0; j < N; j++) {
    std::cout << "Order " << j
              << " fulfilled = " << sol(order_fulfilled_count[j])
              << ", required = " << c[j] << std::endl;
  }
}

このプログラムは、非負整数変数からなる$M×N$行列を使用する。 x の非負整数変数を使用し、ここで x[i][j] は $x_{i,j}$、すなわち棒$i$から切断された順序$j$の部品の数に対応する。我々はこれを x をネストされた qbpp::Vector として実装し、各変数は$0\leq x_{i,j} \leq c_j qbpp::VarInt オブジェクトとして実装し、各変数は $0\leq x_{i,j} \leq c_j$ によって制限される。

制約は以下のように定義される：

order_fulfilled_count: $N$ 個の式からなるベクトルで、 order_fulfilled_count[j] は注文番号 $j$ に対する総生産個数を表す。
order_constraint: $N$ 個の制約式からなるベクトルで、 order_fulfilled_count[j] == c[j] すべての $j$ に対して
bar_length_used: $M$個の式からなるベクトル。ここで bar_length_used[i] はバー $i$ で使用される総長さを表す。
bar_constraint: $M$ 個の制約式からなるベクトル。 0 <= bar_length_used[i] <= L すべての $i$ に対して
f: 全ての制約式の和。 f.simplify_as_binary()を呼び出した後、Easy Solverは目標エネルギー0（すなわち全ての制約が満たされる）解を検索する。

以下の出力は実現可能な解の一例である:

Bar 0:  2  0  0  3   used = 59, waste = 1
Bar 1:  4  0  1  0   used = 60, waste = 0
Bar 2:  1  1  3  0   used = 60, waste = 0
Bar 3:  0  0  4  2   used = 54, waste = 6
Bar 4:  2  1  0  1   used = 60, waste = 0
Bar 5:  1  2  0  0   used = 59, waste = 1
Order 0 fulfilled = 10, required = 10
Order 1 fulfilled = 4, required = 4
Order 2 fulfilled = 8, required = 8
Order 3 fulfilled = 6, required = 6

$N=4$ の全順序が $M=6$ 本の棒材で満たされていることが確認できる。

$M=5$ と設定すると、ソルバーは次の非実現解を返す。この解では全ての順序が満たされていない:

Bar 0:  4  0  1  0   used = 60, waste = 0
Bar 1:  0  0  6  1   used = 59, waste = 1
Bar 2:  2  1  0  1   used = 60, waste = 0
Bar 3:  2  0  0  3   used = 59, waste = 1
Bar 4:  1  2  0  0   used = 59, waste = 1
Order 0 fulfilled = 9, required = 10
Order 1 fulfilled = 3, required = 4
Order 2 fulfilled = 7, required = 8
Order 3 fulfilled = 5, required = 6

最終更新日: 2026.01.06