Multiobjective knapsack（多目的ナップザック問題）

ここでは、2つの予約語で指定されたオブジェクトを持つナップザック問題を解説します。
任意のアイテム集合上の各重量と価値、また実行可能解は全重量が与えられた制限以下である部分集合として決定します。まず、最初のゴールは、総価値が与えられたゴールに達している解を探索することです。その後、最小の製品とリュックサックの中に取られた最大値を最小化したいと思います。この二番目のオブジェクトは完全に人工的ですが、LocalSolverを使用することで多目的最適化を導入することが可能です。

注：このモデル作成方法は整数計画法と全く同様です。：アイテムがナップザックにある場合、各アイテムにおける、0-1意思決定変数は1と同等に定義され、それ以外の場合は0と定義されます。
100万オブジェクトを持つ多目的ナップザック問題もLocalSolverを使用することで解くことが可能です。

LSP ソースファイル

/********** multiobj_knapsack.lsp **********/

function input() {
  usage = "Usage: localsolver multiobj_knapsack.lsp inFileName=inputFile "
    + "[knapsackGoal=goal] [lsTimeLimit=timeLimit]";

  if (inFileName == nil) error(usage);
  
  inFile = openRead(inFileName);  
  nbItems = readInt(inFile);
  weights[0..nbItems-1] = readInt(inFile);
  values[0..nbItems-1] = readInt(inFile);
  knapsackBound = readInt(inFile);
}

function model() {
  // 0-1 decisions
  x[0..nbItems-1] <- 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]);
  if (knapsackGoal != nil) maximize min(knapsackValue, knapsackGoal);
  else maximize knapsackValue;

  // secondary objective: minimize product of minimum and maximum values
  knapsackMinValue <- min[i in 0..nbItems-1](x[i] ? values[i] : knapsackBound);
  knapsackMaxValue <- max[i in 0..nbItems-1](x[i] ? values[i] : 0);
  knapsackProduct <- knapsackMinValue * knapsackMaxValue;
  minimize knapsackProduct;
}

function param() {
  if (knapsackGoal != nil) // stop optimizing when first goal reached
    setObjectiveBound(0, knapsackGoal); 
  computeInitialSol();
  if (lsTimeLimit == nil) // first 10 sec spent to optimize total value only
    lsTimeLimit = {10, 10}; 
  lsNbThreads = 4;
}

/* Computes initial solution greedily. */
function computeInitialSol() {    
  local i = 0;
  local weight = 0;
  local value = 0;

  while (i < nbItems && weight + weights[i] <= knapsackBound) {
    setValue(x[i], 1); // set item i into knapsack
        weight = weight + weights[i];
      value = value + values[i];
    i = i + 1;
  }

  display();  
}

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

  println("knapsackMinValue = " + getValue(knapsackMinValue)
    + ", knapsackMaxValue = " + getValue(knapsackMaxValue)
    + ", knapsackProduct = " + getValue(knapsackProduct)); 
}

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

/* Checks solution. */
function checkSol() {
  local weight = 0; local value = 0; local product = 0;

  for [i in 0..nbItems-1 : getValue(x[i]) == 1] {
    weight = weight + weights[i];
    value = value + values[i];
    product = product * values[i];
  }
  
  display();
  
  if (weight > knapsackBound) 
    error("weight (" + weight 
      + ") > knapsackBound (" + knapsackBound + ")");
}

例題コンテンツ

• multiobj_knapsack/
• multiobj_knapsack/instances/
• multiobj_knapsack/multiobj_knapsack.lsp
• multiobj_knapsack/README.txt
• multiobj_knapsack/MultiobjKnapsack.cs
• multiobj_knapsack/multiobj_knapsack.cpp
• multiobj_knapsack/MultiobjKnapsack.java
• multiobj_knapsack/instances/multiobjtoy.in
• multiobj_knapsack/instances/toy.in
• multiobj_knapsack/instances/kp_1000000_2.in
• multiobj_knapsack/instances/kp_100000_2.in
• multiobj_knapsack/instances/kp_10000_2.in
• multiobj_knapsack/instances/kp_1000_2.in
• multiobj_knapsack/instances/kp_100_2.in
• multiobj_knapsack/instances/kp_1000000_1.in
• multiobj_knapsack/instances/kp_100000_1.in
• multiobj_knapsack/instances/kp_10000_1.in
• multiobj_knapsack/instances/kp_1000_1.in
• multiobj_knapsack/instances/kp_100_1.in

このページの先頭へ