IBM Bob + CPLEXでナップサック問題を解いてみる

1. はじめに

みなさん、こんにちは。今回は私の周りで盛り上がっている「IBM Bob」を使って、最適化問題（オペレーションズ・リサーチ）の世界では、一番有名といっても過言ではない「超定番」の基礎問題である、「ナップサック問題」に挑戦してみます。

ツールは「IBM ILOG CPLEX」、言語はOptimization Programming Language (OPL)を使います。

私も、そろそろCPLEXについても勉強していかないといけない状況ではあったのですが、IBM Bobの登場はとても心強い味方が現れたと思っています。

ゆくゆくは、SPSS Modelerとの連携についてもやっていきたいと考えています。

本記事で作成した、OPLファイルやサンプルデータ、READMEファイルをGitHubにアップロードしています。
ご自由にダウンロードしてください。

2. ナップサック問題とは

一言でいうと、**「限られた容量のリュックサックに、どの品物を詰め込めば、合計の価値が一番高くなるか？」**を計算する問題です。

具体的なイメージ
例えば、あなたがRPGゲームの主人公だとします。

ナップサックの容量制限: 15kgまでしかアイテムを持てない。

目の前にあるアイテム:
● 伝説のくわ（重さ10kg、強さ100）
● 魔法のすだれ（重さ8kg、強さ80）
● 回復のおもち（重さ2kg、強さ30）
● おはじき（重さ1kg、強さ20）

全部は持っていけないので、「どの組み合わせで持っていくのが一番『強さ（価値）』を高くできるか？」を考えますよね。これがナップサック問題です。

2.1 標準的な0-1ナップサック問題

今回は、「0-1ナップサック問題」を題材にします。
と、私がそうしようと思ったわけではなく、Bobに以下のようにお願いしたら、まずは「0-1ナップサック問題」のモデルとデータを作成するという提案を受けました。
新しいファイルとなっているのは、私が何回か実験でナップサック問題のモデルを作成していたからです。今回は新しく最初から作ってと頼みました。

「0-1」という名前の由来は、それぞれの品物に対して**「丸ごと全部入れる（1）か、全く入れない（0）かの2択しかない」**という点にあります。

標準的な0-1ナップサック問題には、以下の明確なルール（前提条件）があります。

★ 0-1ナップサック問題の3つのルール

①. 分割できない（0か1のみ）

金塊や水のように「半分だけ（0.5）入れる」といったことはできません。剣やパソコンのように「1個入れるか、入れないか」のどちらかです。

②. 各品物は1つずつしかない

同じアイテムを2個、3個と複数入れることはできません。（※もし複数個入れられる場合は「整数ナップサック問題」という別の種類になります）

③. 容量制限を絶対に守る

選んだ品物の重さの合計は、ナップサックの制限容量を1グラムでも超えてはいけません。

3. Bobでナップサック問題を解くモデルを書いてもらう

ここからは、作成する過程をお見せします。

3.1 モデルの作成

何も考える必要はないです。勝手にプログラムを書いてくれます。

次のタスク進む際に確認をしてくれますが、「Autoーapprove」機能を "ON" にすれば、こちらが "approve" をクリックしなくてもタスクを実行してくれるモードもあります。

ナップサック問題モデル

/*********************************************
 * ナップサック問題 (0-1 Knapsack Problem)
 * CPLEX OPL モデル
 *********************************************/

// パラメータの宣言
int n = ...; // アイテムの数
int capacity = ...; // ナップサックの容量

range Items = 1..n; // アイテムのインデックス

int value[Items] = ...; // 各アイテムの価値
int weight[Items] = ...; // 各アイテムの重さ

// 決定変数
dvar boolean x[Items]; // x[i] = 1 ならアイテムiを選択、0なら選択しない

// 目的関数：価値の合計を最大化
maximize
  sum(i in Items) value[i] * x[i];

// 制約条件
subject to {
  // 容量制約：選択したアイテムの重さの合計が容量以下
  ctCapacity:
    sum(i in Items) weight[i] * x[i] <= capacity;
}

// 結果の出力
execute DISPLAY {
  writeln("=== ナップサック問題の解 ===");
  writeln("ナップサックの容量: ", capacity);
  writeln();
  
  var totalValue = 0;
  var totalWeight = 0;
  
  writeln("選択されたアイテム:");
  for(var i in Items) {
    if(x[i] == 1) {
      writeln("  アイテム ", i, ": 価値=", value[i], ", 重さ=", weight[i]);
      totalValue += value[i];
      totalWeight += weight[i];
    }
  }
  
  writeln();
  writeln("合計価値: ", totalValue);
  writeln("合計重さ: ", totalWeight);
  writeln("容量使用率: ", (totalWeight * 100.0 / capacity).toFixed(2), "%");
}

3.2 データの作成

サンプルデータも作ってくれます。

サンプルデータ

/*********************************************
 * ナップサック問題のデータファイル
 * 
 * 例題：5つのアイテムから選択
 *********************************************/

// アイテムの数
n = 5;

// ナップサックの容量
capacity = 15;

// 各アイテムの価値
value = [
  10,  // アイテム1
  40,  // アイテム2
  30,  // アイテム3
  50,  // アイテム4
  35   // アイテム5
];

// 各アイテムの重さ
weight = [
  5,   // アイテム1
  4,   // アイテム2
  6,   // アイテム3
  3,   // アイテム4
  7    // アイテム5
];

3.3 概要及び実行方法

もう、至れり尽くせりですよ。

3.4 CPLEXで実行

「IBM ILOG CPLEX Optimization Studio」を起動して、プロジェクトを作り、データ、モデルをワークスペースに配置し、実行構成を作成して実行しました。
※.データ名、モデルファイル名は今後も同じプロジェクト内で管理しようと思い、一旦名前を変えています。
※.日本語を使うとうまく実行できないので、全てアルファベットを使用しました。

さて、エラーになりました。'toFixed'が定義されていませんと。
Bobに報告します。

Execution of "DISPLAY" failed: "C:\haya\work\CPLEX\DEMO\KnapSack_Bob\KnapSack_Bob\mod\knapsack_opl_bob1.mod", line 55: undefined method 'toFixed'.	knapsack_opl_bob1.mod	/KnapSack_Bob/mod	35:1-8 C:\haya\work\CPLEX\DEMO\KnapSack_Bob\KnapSack_Bob\mod\knapsack_opl_bob1.mod	OPL 問題マーカー

3.5 Bobでエラー修正をする

エラーメッセージをそのまま貼り付けて、Bobに確認すると、すぐに修正をしてくれました。

3.6 再度CPLEXで実行する

修正したプログラムを反映して再度実行すると、以下のように結果が出力されました。
アイテム２，４，５を選択することで、Weightが14、valueが125となりました。

4. 感想

さて、まずは最適化問題の入門となるナップサック問題に取り組んでみました。
最適化問題については超初心者であり、CPLEXのOPLも全く理解していない私が、簡単に実装できたことが驚きですね。
IBM Bobより CPLEXの操作の方が大変だったくらいです。

これからは、IBM Bobの力を借りながら、最適化問題を勉強していきたいと思います。
プログラムの内容をはじめ、最適化問題もきちんと理解できるように精進していきます。

5. おわりに

さて、いかがでしたでしょうか？まずは簡単と思われる内容に取り組んでみました。
今後は、もう少し難しい内容やSPSS Modelerとの連携にも取り組んでいきたいと思っています。

IBM Bobもさらに進化していくと思います。わたしも取り残されないように頑張っていきたいと思います。
ではまた次回！！！

参考

SPSS Modeler ノードリファレンス目次

SPSS Modeler 逆引きストリーム集

SPSS funさん記事集

IBM 斎藤さんの記事集

SPSS連載ブログバックナンバー

SPSSヒモトクブログなどは以下のTechXchangeのコミュニティに統合されました。
ご興味がある方は、ぜひiBM IDを登録して参加してみてください！！！お待ちしています。

IBM TechXchange Data Science Japan