1. LocalSolverホーム
  2. クイックスタートガイド
  3. ユーザーのファースト・モデルを解く

ユーザーのファースト・モデルを解く

このセクションでは、ユーザーのファースト・モデル(典型的なナップザック問題)をどのようにモデリングし、解くのかについて解説しています。

ナップザック問題を下記のように定義します。

重量と価値をそれぞれ持つアイテム集合があります。これらの全重量が定められた制限より軽く、かつ全体の価値が可能な限り最大になるように部分集合を決定します。
この問題は理論的に解くことが難しい問題です。

ナップザック トイ モデル

下記はナップザック・トイ例題(例題・toyを参照ください)を生成するLocalSolverプログラム(LSP)です。:合計重量は102キロ以下とし、各8アイテムの重量は10、60、30、40、30、20、20、2そして各8アイテムの価値は1、10、15、40、60、、0、100、15
モデルの作成法は、整数計画と全く同様である点に留意ください:各アイテムにおいて、0-1意思決定変数はアイテムがナップザックに取られる場合、1となり、取られない場合は0と定義されます。

/********** toy.lsp **********/

function model() {
  // 0-1 decisions
  x_0 <- bool(); x_1 <- bool(); x_2 <- bool(); x_3 <- bool();
  x_4 <- bool(); x_5 <- bool(); x_6 <- bool(); x_7 <- bool();
  
  // weight constraint

  knapsackWeight <- 10*x_0 + 60*x_1 + 30*x_2 + 40*x_3 + 30*x_4 + 20*x_5 + 20*x_6 + 2*x_7;
  constraint knapsackWeight <= 102;
  
  // maximize value

  knapsackValue <- 1*x_0 + 10*x_1 + 15*x_2 + 40*x_3 + 60*x_4 + 90*x_5 + 100*x_6 + 15*x_7;
  maximize knapsackValue;
}

表現式と呼ばれるモデルの全変数は左矢印<-を使って宣言されています。bool変数(0-1意思決定変数)は算術演算子boolを使用することで導入されます。内部変数は他の演算子を使用し、これらの意思決定変数を生成することが可能です。product (*), sum (+), lower than or equal to (<=)その他多くの各種数学記号が利用頂けるため、大変理解しやすい形で非線形計算が必要な制約を表現することができ、非線形組合せ最適化問題の生成及び、求解が可能です。キーワードconstraintまたはmaximizeは表現式に制約、または最大化の宣言を追加するために使用します。

このモデルを解くために、アーギュメントとしてLSPファイルを使用しLocalSolverを呼び出します。さらに、built-in変数(プログラミング)lsTimeLimitの値はLocal-searchソルバーの実行時間を1秒に制限するために、上書きされます。
その後、自身のコンソールに下記のトレースが出力されます。

localsolver_2_0/examples/toy$ localsolver toy.lsp lsTimeLimit=1
LocalSolver 2.0 (build 20120213)
Copyright (C) 2012 Bouygues SA, Aix-Marseille University, CNRS.
All rights reserved (see End-User License Agreement for details).

Run model...
Run solver...

Model: 
  expressions = 50, operands = 62
  decisions = 8, constraints = 1, objectives = 1

Param: 
  time limit = 1 sec, no iteration limit, seed = 0, nb threads = 2, annealing level = 1

Objectives:
  Obj 0: maximize, no bound

Phases:
  Phase 0: time limit = 1 sec, no iteration limit, optimized objective = 0

Phase 0:

[1 sec, 24115 itr]: obj = (280), mov = 49405, inf = 75.6%, acc = 2.7%, imp = 13

24115 itr, 49405 mov performed in 1 sec
Feasible solution: obj = (280)

指定時間を設定していない場合、Ctrl+Cをクリックし、プログラムの停止が強制されるまで、探索は継続します。コンソール内のトレースはモデルのキー数値を使用し開始します:複数の表現式、オペランド、意思決定、制約およびオブジェクト。その後、ソルバーパラメータがリストされます:デフォルト・パラメータが報告される間、(スレッド、シュミレーティドアニーリング・レベル)制限時間をここで指定します。マルチ・オブジェクトの最適化が存在する場合の、オブジェクト及びフェーズに関するトレース方法は、当ガイドのおわりに記載しています。

LocalSolverは各二番目に、経過時間、イタレーション数、現時点での最も良いオブジェクト値を表示します。inf, accおよびimpの演算子は実行不可能解につながるムーブのパーセンテージ、許可れたムーブのパーセンテージ、およびそれぞれの改善したムーブ総数を戻します。探索が終了すると、イタレーション数とムーブ総数が、発見された最適解のステータスと同様に表示されます。(注;複数のスレットを使用した場合、イタレーションよりも、多くのムーブを実行することができます。)解のステータスは、実行不可能解、実行可能解または最適解となります。

基本的 ナップザックモデル

ここでは、入力データが、フォーマット済みファイルで指定された任意のナップザック例題をどのように解くかを解説します。LSPファイルは、下記のように(例題/ナップザックを参照)簡単に修正することが可能です。

/********** knapsack.lsp **********/

function input() {
  if (inFileName == nil) 
    error ("Usage: localsolver knapsack.lsp inFileName=inputFile [lsTimeLimit=limit]");
  
  inFile = openRead(inFileName);
  nbItems = readInt(inFile);
  for [i in 0..nbItems-1] weights[i] = readInt(inFile);
  for [i in 0..nbItems-1] values[i] = readInt(inFile);
  knapsackBound = readInt(inFile);
}


function model() {
  // 0-1 decisions
  for [i in 0..nbItems-1] x[i] <- bool();
  
  // weight constraint

  knapsackWeight <- sum[i in 0..nbItems-1](weights[i] * x[i]);
  constraint knapsackWeight <= knapsackBound;
  
  // maximize value

  knapsackValue <- sum[i in 0..nbItems-1](values[i] * x[i]);
  maximize knapsackValue;
}

function param() {
  if (lsTimeLimit == nil) lsTimeLimit = 10; 
  lsNbThreads = 1;
}


function display() {
  println("knapsackWeight = " + getValue(knapsackWeight) 
    + ", knapsackValue = " + getValue(knapsackValue)); 
}

function output() {
  println("Write solution into file 'sol.txt'");
  solFile = openWrite("sol.txt");
  for [i in 0..nbItems-1 : getValue(x[i]) == 1]
    println(solFile, i);
}

下記のコマンド行でこれを実行すると、前回のLSPファイルに同様のアウトプットを得ます。注:より柔軟性が増すように、コマンド行でいくつかの変数を定義しました。(inFileName, lsTimeLimit)

localsolver_2_0/examples/knapsack$ localsolver 
knapsack.lsp inFileName=instances/toy.in lsTimeLimit=1

全ての算術演算子を、モデリング及びプログラミング作業の双方で、使用することができます。例えば、ステートメントc <- a * bは表現cがモデリング表現aとbの積に一致することを宣言しています。一方、c = a * bは、プログラミングの変数a とbの積の結果をプログラミングの変数cに割り当てることを意味します。n-配列演算子は、任意のオペレントの数を持つ表現式を宣言するために、n配列関数が使用できます。(例えば、sum(a, b, c))オペランドの数が固定される場合、バイナリのinfix形式(例えばa+b+c)として使用することも可能です。例えば、ステートメント

knapsackWeight <- sum[i in 0..nbItems-1](weights[i] * x[i]);

は、0 to nbItems-1.による全てのアイテムに、表現式weights[i]とx[i]の積の合計として表現式knapsackWeightを宣言します。

LocalSolverのモデラーの紹介で解説したとおり、LSP言語の特異性は、main 関数を提供しないことです。実際、LSP言語は5つの定義済み関数input(), model(), param(), display(), output().から構成されるモデリング形式を帰納します。
これらの関数はLocalSolverの実行ファイルで実行される下記の一連のプログラムを帰納します。

  • input: 自身のデータの宣言または、ファイルからデータを読み込む
  • model: 自身の最適化モデルを宣言する
  • parm: 実行前にローカルサーチソルバーをパラメータ化する
  • display: 解いている間にコンソール内、または複数のファイル内で、様々な情報を表示する
  • output: 一度、解が得られたとき、コンソール内、またはファイル内にその結果を記述する

注;model()を除き、全てのbuilt-in変数および関数はデフォルト値を持ちます。

このページの先頭へ