複数のナップサックの問題を解決する

このセクションでは、複数のナップサックの問題を解く方法について説明します。 MIP ソルバーと CP-SAT ソルバーを 使用しています この場合、コンテナを「ビン」と呼ぶのが一般的ですが、 考えてみましょう

次の例は、アイテムを 5 つのビンに梱包する最適な方法を見つける方法を示しています。

例

前の例と同様に、 さまざまな重量と値を持つアイテムのコレクション。問題は、大量のコードを アイテムのサブセットを 5 つのビンに分割し、それぞれのビンの最大容量は 100 です。 パックされた合計値が最大値になるようにします

以降のセクションでは、この問題を解決するプログラムのセクションを紹介します。 完全なプログラムについては、完全なプログラムをご覧ください。

MIP ソリューション

以降のセクションでは、 MPSolver ラッパー。

ライブラリのインポート

次のコードは、必要なライブラリをインポートします。

Python

from ortools.linear_solver import pywraplp

C++

#include <iostream>
#include <memory>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

データを作成する

次のコードは、問題のデータを作成します。

Python

data = {}
data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
assert len(data["weights"]) == len(data["values"])
data["num_items"] = len(data["weights"])
data["all_items"] = range(data["num_items"])

data["bin_capacities"] = [100, 100, 100, 100, 100]
data["num_bins"] = len(data["bin_capacities"])
data["all_bins"] = range(data["num_bins"])

C++

const std::vector<int> weights = {
    {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}};
const std::vector<int> values = {
    {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}};
const int num_items = weights.size();
std::vector<int> all_items(num_items);
std::iota(all_items.begin(), all_items.end(), 0);

const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
const int num_bins = bin_capacities.size();
std::vector<int> all_bins(num_bins);
std::iota(all_bins.begin(), all_bins.end(), 0);

Java

final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
final int numItems = weights.length;
final int[] allItems = IntStream.range(0, numItems).toArray();

final double[] binCapacities = {100, 100, 100, 100, 100};
final int numBins = binCapacities.length;
final int[] allBins = IntStream.range(0, numBins).toArray();

C#

double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();

double[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();

データには次のものが含まれます。

• weights: アイテムの重みを含むベクトル。
• values: アイテムの値を含むベクトル。
• capacities: ビンの容量を含むベクトル。

この例では、すべてのビンの容量が同じですが、必ずしもそうである必要はありません。 見ていきましょう。

MIP ソルバーを宣言する

次のコードは MIP ソルバーを宣言しています。

Python

solver = pywraplp.Solver.CreateSolver("SCIP")
if solver is None:
    print("SCIP solver unavailable.")
    return

C++

  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

Java

// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
  System.out.println("Could not create solver SCIP");
  return;
}

C#

// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
    return;
}

変数を作成する

次のコードは、問題を表す変数を作成します。

Python

# x[i, b] = 1 if item i is packed in bin b.
x = {}
for i in data["all_items"]:
    for b in data["all_bins"]:
        x[i, b] = solver.BoolVar(f"x_{i}_{b}")

C++

// x[i][b] = 1 if item i is packed in bin b.
std::vector<std::vector<const MPVariable*>> x(
    num_items, std::vector<const MPVariable*>(num_bins));
for (int i : all_items) {
  for (int b : all_bins) {
    x[i][b] = solver->MakeBoolVar(absl::StrFormat("x_%d_%d", i, b));
  }
}

Java

MPVariable[][] x = new MPVariable[numItems][numBins];
for (int i : allItems) {
  for (int b : allBins) {
    x[i][b] = solver.makeBoolVar("x_" + i + "_" + b);
  }
}

C#

Variable[,] x = new Variable[NumItems, NumBins];
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        x[i, b] = solver.MakeBoolVar($"x_{i}_{b}");
    }
}

各 x[(i, j)] は 0 ～ 1 の変数です。i はアイテム、j はビンです。イン 解答では、アイテム i がビン j に置かれた場合 x[(i, j)] は 1、0 になります。 できません。

制約を定義する

次のコードは、問題の制約を定義しています。

Python

# Each item is assigned to at most one bin.
for i in data["all_items"]:
    solver.Add(sum(x[i, b] for b in data["all_bins"]) <= 1)

# The amount packed in each bin cannot exceed its capacity.
for b in data["all_bins"]:
    solver.Add(
        sum(x[i, b] * data["weights"][i] for i in data["all_items"])
        <= data["bin_capacities"][b]
    )

C++

// Each item is assigned to at most one bin.
for (int i : all_items) {
  LinearExpr sum;
  for (int b : all_bins) {
    sum += x[i][b];
  }
  solver->MakeRowConstraint(sum <= 1.0);
}
// The amount packed in each bin cannot exceed its capacity.
for (int b : all_bins) {
  LinearExpr bin_weight;
  for (int i : all_items) {
    bin_weight += LinearExpr(x[i][b]) * weights[i];
  }
  solver->MakeRowConstraint(bin_weight <= bin_capacities[b]);
}

Java

// Each item is assigned to at most one bin.
for (int i : allItems) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int b : allBins) {
    constraint.setCoefficient(x[i][b], 1);
  }
}

// The amount packed in each bin cannot exceed its capacity.
for (int b : allBins) {
  MPConstraint constraint = solver.makeConstraint(0, binCapacities[b], "");
  for (int i : allItems) {
    constraint.setCoefficient(x[i][b], weights[i]);
  }
}

C#

// Each item is assigned to at most one bin.
foreach (int i in allItems)
{
    Constraint constraint = solver.MakeConstraint(0, 1, "");
    foreach (int b in allBins)
    {
        constraint.SetCoefficient(x[i, b], 1);
    }
}

// The amount packed in each bin cannot exceed its capacity.
foreach (int b in allBins)
{
    Constraint constraint = solver.MakeConstraint(0, BinCapacities[b], "");
    foreach (int i in allItems)
    {
        constraint.SetCoefficient(x[i, b], Weights[i]);
    }
}

制約は次のとおりです。

• 各アイテムは最大で 1 つのビンに入れることができます。この制約は、 すべてのビンに対する x[i, j] の合計が j 以下であることが必要です を 1 にします。
• 各ビンに梱包する合計重量が容量を超えないようにする必要があります。この ビンに入れられたアイテムの重量の合計を必須にすることで、制約を設定 j は、ビンの容量以下になります。

目標を定義する

次のコードは、問題の目的関数を定義します。 梱包された商品の合計金額。

Python

# Maximize total value of packed items.
objective = solver.Objective()
for i in data["all_items"]:
    for b in data["all_bins"]:
        objective.SetCoefficient(x[i, b], data["values"][i])
objective.SetMaximization()

C++

// Maximize total value of packed items.
MPObjective* const objective = solver->MutableObjective();
LinearExpr objective_value;
for (int i : all_items) {
  for (int b : all_bins) {
    objective_value += LinearExpr(x[i][b]) * values[i];
  }
}
objective->MaximizeLinearExpr(objective_value);

Java

// Maximize total value of packed items.
MPObjective objective = solver.objective();
for (int i : allItems) {
  for (int b : allBins) {
    objective.setCoefficient(x[i][b], values[i]);
  }
}
objective.setMaximization();

C#

Objective objective = solver.Objective();
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        objective.SetCoefficient(x[i, b], Values[i]);
    }
}
objective.SetMaximization();

x[i, j] * data['values'][i] はアイテム i の値を アイテムがビン j に置かれている場合の、目標。i がどのビンにも配置されていない場合は、 目標に寄与しません

ソルバーを呼び出す

次のコードはソルバーを呼び出します。

Python

print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

C++

const MPSolver::ResultStatus result_status = solver->Solve();

Java

final MPSolver.ResultStatus status = solver.solve();

C#

Solver.ResultStatus resultStatus = solver.Solve();

解答を印刷

次のコードは、問題の解答を表示します。

Python

if status == pywraplp.Solver.OPTIMAL:
    print(f"Total packed value: {objective.Value()}")
    total_weight = 0
    for b in data["all_bins"]:
        print(f"Bin {b}")
        bin_weight = 0
        bin_value = 0
        for i in data["all_items"]:
            if x[i, b].solution_value() > 0:
                print(
                    f"Item {i} weight: {data['weights'][i]} value:"
                    f" {data['values'][i]}"
                )
                bin_weight += data["weights"][i]
                bin_value += data["values"][i]
        print(f"Packed bin weight: {bin_weight}")
        print(f"Packed bin value: {bin_value}\n")
        total_weight += bin_weight
    print(f"Total packed weight: {total_weight}")
else:
    print("The problem does not have an optimal solution.")

C++

if (result_status == MPSolver::OPTIMAL) {
  LOG(INFO) << "Total packed value: " << objective->Value();
  double total_weight = 0.0;
  for (int b : all_bins) {
    LOG(INFO) << "Bin " << b;
    double bin_weight = 0.0;
    double bin_value = 0.0;
    for (int i : all_items) {
      if (x[i][b]->solution_value() > 0) {
        LOG(INFO) << "Item " << i << " weight: " << weights[i]
                  << " value: " << values[i];
        bin_weight += weights[i];
        bin_value += values[i];
      }
    }
    LOG(INFO) << "Packed bin weight: " << bin_weight;
    LOG(INFO) << "Packed bin value: " << bin_value;
    total_weight += bin_weight;
  }
  LOG(INFO) << "Total packed weight: " << total_weight;
} else {
  LOG(INFO) << "The problem does not have an optimal solution.";
}

Java

// Check that the problem has an optimal solution.
if (status == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Total packed value: " + objective.value());
  double totalWeight = 0;
  for (int b : allBins) {
    double binWeight = 0;
    double binValue = 0;
    System.out.println("Bin " + b);
    for (int i : allItems) {
      if (x[i][b].solutionValue() == 1) {
        System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]);
        binWeight += weights[i];
        binValue += values[i];
      }
    }
    System.out.println("Packed bin weight: " + binWeight);
    System.out.println("Packed bin value: " + binValue);
    totalWeight += binWeight;
  }
  System.out.println("Total packed weight: " + totalWeight);
} else {
  System.err.println("The problem does not have an optimal solution.");
}

C#

// Check that the problem has an optimal solution.
if (resultStatus == Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine($"Total packed value: {solver.Objective().Value()}");
    double TotalWeight = 0.0;
    foreach (int b in allBins)
    {
        double BinWeight = 0.0;
        double BinValue = 0.0;
        Console.WriteLine("Bin " + b);
        foreach (int i in allItems)
        {
            if (x[i, b].SolutionValue() == 1)
            {
                Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                BinWeight += Weights[i];
                BinValue += Values[i];
            }
        }
        Console.WriteLine("Packed bin weight: " + BinWeight);
        Console.WriteLine("Packed bin value: " + BinValue);
        TotalWeight += BinWeight;
    }
    Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
    Console.WriteLine("The problem does not have an optimal solution!");
}

各ビンについて、そのビンに配置されたアイテムと、そのビンのアイテムが表示されます。 合計値と重みまた、全体の合計値と、 重量が含まれます。

プログラムを実行すると、次の出力が表示されます。

Total packed value: 395.0
Bin  0

Item 3 - weight: 36  value: 50
Item 13 - weight: 36  value: 30
Packed bin weight: 72
Packed bin value: 80

Bin  1

Item 5 - weight: 48  value: 30
Item 7 - weight: 42  value: 40
Packed bin weight: 90
Packed bin value: 70

Bin  2

Item 1 - weight: 30  value: 30
Item 10 - weight: 30  value: 45
Item 14 - weight: 36  value: 25
Packed bin weight: 96
Packed bin value: 100

Bin  3

Item 2 - weight: 42  value: 25
Item 12 - weight: 42  value: 20
Packed bin weight: 84
Packed bin value: 45

Bin  4

Item 4 - weight: 36  value: 35
Item 8 - weight: 36  value: 30
Item 9 - weight: 24  value: 35
Packed bin weight: 96
Packed bin value: 100

Total packed weight: 438

プログラムを完了する

複数のナップサックの完全なプログラムを以下に示します。

Python

"""Solve a multiple knapsack problem using a MIP solver."""
from ortools.linear_solver import pywraplp


def main():
    data = {}
    data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    assert len(data["weights"]) == len(data["values"])
    data["num_items"] = len(data["weights"])
    data["all_items"] = range(data["num_items"])

    data["bin_capacities"] = [100, 100, 100, 100, 100]
    data["num_bins"] = len(data["bin_capacities"])
    data["all_bins"] = range(data["num_bins"])

    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")
    if solver is None:
        print("SCIP solver unavailable.")
        return

    # Variables.
    # x[i, b] = 1 if item i is packed in bin b.
    x = {}
    for i in data["all_items"]:
        for b in data["all_bins"]:
            x[i, b] = solver.BoolVar(f"x_{i}_{b}")

    # Constraints.
    # Each item is assigned to at most one bin.
    for i in data["all_items"]:
        solver.Add(sum(x[i, b] for b in data["all_bins"]) <= 1)

    # The amount packed in each bin cannot exceed its capacity.
    for b in data["all_bins"]:
        solver.Add(
            sum(x[i, b] * data["weights"][i] for i in data["all_items"])
            <= data["bin_capacities"][b]
        )

    # Objective.
    # Maximize total value of packed items.
    objective = solver.Objective()
    for i in data["all_items"]:
        for b in data["all_bins"]:
            objective.SetCoefficient(x[i, b], data["values"][i])
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print(f"Total packed value: {objective.Value()}")
        total_weight = 0
        for b in data["all_bins"]:
            print(f"Bin {b}")
            bin_weight = 0
            bin_value = 0
            for i in data["all_items"]:
                if x[i, b].solution_value() > 0:
                    print(
                        f"Item {i} weight: {data['weights'][i]} value:"
                        f" {data['values'][i]}"
                    )
                    bin_weight += data["weights"][i]
                    bin_value += data["values"][i]
            print(f"Packed bin weight: {bin_weight}")
            print(f"Packed bin value: {bin_value}\n")
            total_weight += bin_weight
        print(f"Total packed weight: {total_weight}")
    else:
        print("The problem does not have an optimal solution.")


if __name__ == "__main__":
    main()

C++

// Solve a multiple knapsack problem using a MIP solver.
#include <iostream>
#include <memory>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {

void MultipleKnapsackMip() {
  const std::vector<int> weights = {
      {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}};
  const std::vector<int> values = {
      {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}};
  const int num_items = weights.size();
  std::vector<int> all_items(num_items);
  std::iota(all_items.begin(), all_items.end(), 0);

  const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
  const int num_bins = bin_capacities.size();
  std::vector<int> all_bins(num_bins);
  std::iota(all_bins.begin(), all_bins.end(), 0);

  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

  // Variables.
  // x[i][b] = 1 if item i is packed in bin b.
  std::vector<std::vector<const MPVariable*>> x(
      num_items, std::vector<const MPVariable*>(num_bins));
  for (int i : all_items) {
    for (int b : all_bins) {
      x[i][b] = solver->MakeBoolVar(absl::StrFormat("x_%d_%d", i, b));
    }
  }

  // Constraints.
  // Each item is assigned to at most one bin.
  for (int i : all_items) {
    LinearExpr sum;
    for (int b : all_bins) {
      sum += x[i][b];
    }
    solver->MakeRowConstraint(sum <= 1.0);
  }
  // The amount packed in each bin cannot exceed its capacity.
  for (int b : all_bins) {
    LinearExpr bin_weight;
    for (int i : all_items) {
      bin_weight += LinearExpr(x[i][b]) * weights[i];
    }
    solver->MakeRowConstraint(bin_weight <= bin_capacities[b]);
  }

  // Objective.
  // Maximize total value of packed items.
  MPObjective* const objective = solver->MutableObjective();
  LinearExpr objective_value;
  for (int i : all_items) {
    for (int b : all_bins) {
      objective_value += LinearExpr(x[i][b]) * values[i];
    }
  }
  objective->MaximizeLinearExpr(objective_value);

  const MPSolver::ResultStatus result_status = solver->Solve();

  if (result_status == MPSolver::OPTIMAL) {
    LOG(INFO) << "Total packed value: " << objective->Value();
    double total_weight = 0.0;
    for (int b : all_bins) {
      LOG(INFO) << "Bin " << b;
      double bin_weight = 0.0;
      double bin_value = 0.0;
      for (int i : all_items) {
        if (x[i][b]->solution_value() > 0) {
          LOG(INFO) << "Item " << i << " weight: " << weights[i]
                    << " value: " << values[i];
          bin_weight += weights[i];
          bin_value += values[i];
        }
      }
      LOG(INFO) << "Packed bin weight: " << bin_weight;
      LOG(INFO) << "Packed bin value: " << bin_value;
      total_weight += bin_weight;
    }
    LOG(INFO) << "Total packed weight: " << total_weight;
  } else {
    LOG(INFO) << "The problem does not have an optimal solution.";
  }
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::MultipleKnapsackMip();
  return EXIT_SUCCESS;
}

Java

// Solve a multiple knapsack problem using a MIP solver.
package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;

/** Multiple knapsack problem. */
public class MultipleKnapsackMip {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Instantiate the data problem.
    final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    final int numItems = weights.length;
    final int[] allItems = IntStream.range(0, numItems).toArray();

    final double[] binCapacities = {100, 100, 100, 100, 100};
    final int numBins = binCapacities.length;
    final int[] allBins = IntStream.range(0, numBins).toArray();

    // Create the linear solver with the SCIP backend.
    MPSolver solver = MPSolver.createSolver("SCIP");
    if (solver == null) {
      System.out.println("Could not create solver SCIP");
      return;
    }

    // Variables.
    MPVariable[][] x = new MPVariable[numItems][numBins];
    for (int i : allItems) {
      for (int b : allBins) {
        x[i][b] = solver.makeBoolVar("x_" + i + "_" + b);
      }
    }

    // Constraints.
    // Each item is assigned to at most one bin.
    for (int i : allItems) {
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      for (int b : allBins) {
        constraint.setCoefficient(x[i][b], 1);
      }
    }

    // The amount packed in each bin cannot exceed its capacity.
    for (int b : allBins) {
      MPConstraint constraint = solver.makeConstraint(0, binCapacities[b], "");
      for (int i : allItems) {
        constraint.setCoefficient(x[i][b], weights[i]);
      }
    }

    // Objective.
    // Maximize total value of packed items.
    MPObjective objective = solver.objective();
    for (int i : allItems) {
      for (int b : allBins) {
        objective.setCoefficient(x[i][b], values[i]);
      }
    }
    objective.setMaximization();

    final MPSolver.ResultStatus status = solver.solve();

    // Check that the problem has an optimal solution.
    if (status == MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("Total packed value: " + objective.value());
      double totalWeight = 0;
      for (int b : allBins) {
        double binWeight = 0;
        double binValue = 0;
        System.out.println("Bin " + b);
        for (int i : allItems) {
          if (x[i][b].solutionValue() == 1) {
            System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]);
            binWeight += weights[i];
            binValue += values[i];
          }
        }
        System.out.println("Packed bin weight: " + binWeight);
        System.out.println("Packed bin value: " + binValue);
        totalWeight += binWeight;
      }
      System.out.println("Total packed weight: " + totalWeight);
    } else {
      System.err.println("The problem does not have an optimal solution.");
    }
  }

  private MultipleKnapsackMip() {}
}

C#

// Solve a multiple knapsack problem using a MIP solver.
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

public class MultipleKnapsackMip
{
    public static void Main()
    {
        // Instantiate the data problem.
        double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
        double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
        int NumItems = Weights.Length;
        int[] allItems = Enumerable.Range(0, NumItems).ToArray();

        double[] BinCapacities = { 100, 100, 100, 100, 100 };
        int NumBins = BinCapacities.Length;
        int[] allBins = Enumerable.Range(0, NumBins).ToArray();

        // Create the linear solver with the SCIP backend.
        Solver solver = Solver.CreateSolver("SCIP");
        if (solver is null)
        {
            return;
        }

        // Variables.
        Variable[,] x = new Variable[NumItems, NumBins];
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                x[i, b] = solver.MakeBoolVar($"x_{i}_{b}");
            }
        }

        // Constraints.
        // Each item is assigned to at most one bin.
        foreach (int i in allItems)
        {
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            foreach (int b in allBins)
            {
                constraint.SetCoefficient(x[i, b], 1);
            }
        }

        // The amount packed in each bin cannot exceed its capacity.
        foreach (int b in allBins)
        {
            Constraint constraint = solver.MakeConstraint(0, BinCapacities[b], "");
            foreach (int i in allItems)
            {
                constraint.SetCoefficient(x[i, b], Weights[i]);
            }
        }

        // Objective.
        Objective objective = solver.Objective();
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                objective.SetCoefficient(x[i, b], Values[i]);
            }
        }
        objective.SetMaximization();

        Solver.ResultStatus resultStatus = solver.Solve();

        // Check that the problem has an optimal solution.
        if (resultStatus == Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine($"Total packed value: {solver.Objective().Value()}");
            double TotalWeight = 0.0;
            foreach (int b in allBins)
            {
                double BinWeight = 0.0;
                double BinValue = 0.0;
                Console.WriteLine("Bin " + b);
                foreach (int i in allItems)
                {
                    if (x[i, b].SolutionValue() == 1)
                    {
                        Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                        BinWeight += Weights[i];
                        BinValue += Values[i];
                    }
                }
                Console.WriteLine("Packed bin weight: " + BinWeight);
                Console.WriteLine("Packed bin value: " + BinValue);
                TotalWeight += BinWeight;
            }
            Console.WriteLine("Total packed weight: " + TotalWeight);
        }
        else
        {
            Console.WriteLine("The problem does not have an optimal solution!");
        }
    }
}

CP SAT ソリューション

以降のセクションでは、CP-SAT ソルバーを使用して問題を解く方法について説明します。

ライブラリのインポート

次のコードは、必要なライブラリをインポートします。

Python

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <map>
#include <numeric>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class MultipleKnapsackSat
{
    public static void Main(String[] args)
    {
        // Instantiate the data problem.
        int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
        int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
        int NumItems = Weights.Length;
        int[] allItems = Enumerable.Range(0, NumItems).ToArray();

        int[] BinCapacities = { 100, 100, 100, 100, 100 };
        int NumBins = BinCapacities.Length;
        int[] allBins = Enumerable.Range(0, NumBins).ToArray();

        // Model.
        CpModel model = new CpModel();

        // Variables.
        ILiteral[,] x = new ILiteral[NumItems, NumBins];
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                x[i, b] = model.NewBoolVar($"x_{i}_{b}");
            }
        }

        // Constraints.
        // Each item is assigned to at most one bin.
        foreach (int i in allItems)
        {
            List<ILiteral> literals = new List<ILiteral>();
            foreach (int b in allBins)
            {
                literals.Add(x[i, b]);
            }
            model.AddAtMostOne(literals);
        }

        // The amount packed in each bin cannot exceed its capacity.
        foreach (int b in allBins)
        {
            List<ILiteral> items = new List<ILiteral>();
            foreach (int i in allItems)
            {
                items.Add(x[i, b]);
            }
            model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
        }

        // Objective.
        LinearExprBuilder obj = LinearExpr.NewBuilder();
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                obj.AddTerm(x[i, b], Values[i]);
            }
        }
        model.Maximize(obj);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        // Print solution.
        // Check that the problem has a feasible solution.
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
            double TotalWeight = 0.0;
            foreach (int b in allBins)
            {
                double BinWeight = 0.0;
                double BinValue = 0.0;
                Console.WriteLine($"Bin {b}");
                foreach (int i in allItems)
                {
                    if (solver.BooleanValue(x[i, b]))
                    {
                        Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                        BinWeight += Weights[i];
                        BinValue += Values[i];
                    }
                }
                Console.WriteLine("Packed bin weight: " + BinWeight);
                Console.WriteLine("Packed bin value: " + BinValue);
                TotalWeight += BinWeight;
            }
            Console.WriteLine("Total packed weight: " + TotalWeight);
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}

モデルを宣言する

次のコードは CP-SAT モデルを宣言しています。

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

データを作成する

次のコードで、問題のデータを設定します。

Python

data = {}
data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
assert len(data["weights"]) == len(data["values"])
num_items = len(data["weights"])
all_items = range(num_items)

data["bin_capacities"] = [100, 100, 100, 100, 100]
num_bins = len(data["bin_capacities"])
all_bins = range(num_bins)

C++

const std::vector<int> weights = {
    {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}};
const std::vector<int> values = {
    {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}};
const int num_items = static_cast<int>(weights.size());
std::vector<int> all_items(num_items);
std::iota(all_items.begin(), all_items.end(), 0);

const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
const int num_bins = static_cast<int>(bin_capacities.size());
std::vector<int> all_bins(num_bins);
std::iota(all_bins.begin(), all_bins.end(), 0);

Java

final int[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
final int[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
final int numItems = weights.length;
final int[] allItems = IntStream.range(0, numItems).toArray();

final int[] binCapacities = {100, 100, 100, 100, 100};
final int numBins = binCapacities.length;
final int[] allBins = IntStream.range(0, numBins).toArray();

C#

int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();

int[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();

costs 配列は費用の表に対応します。 タスクにワーカーを割り当てるように指示しています。

変数を作成する

次のコードは、問題のバイナリ整数変数を作成します。

Python

# x[i, b] = 1 if item i is packed in bin b.
x = {}
for i in all_items:
    for b in all_bins:
        x[i, b] = model.new_bool_var(f"x_{i}_{b}")

C++

// x[i, b] = 1 if item i is packed in bin b.
std::map<std::tuple<int, int>, BoolVar> x;
for (int i : all_items) {
  for (int b : all_bins) {
    auto key = std::make_tuple(i, b);
    x[key] = cp_model.NewBoolVar().WithName(absl::StrFormat("x_%d_%d", i, b));
  }
}

Java

Literal[][] x = new Literal[numItems][numBins];
for (int i : allItems) {
  for (int b : allBins) {
    x[i][b] = model.newBoolVar("x_" + i + "_" + b);
  }
}

C#

ILiteral[,] x = new ILiteral[NumItems, NumBins];
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        x[i, b] = model.NewBoolVar($"x_{i}_{b}");
    }
}

制約を作成する

次のコードは、問題の制約を作成します。

Python

# Each item is assigned to at most one bin.
for i in all_items:
    model.add_at_most_one(x[i, b] for b in all_bins)

# The amount packed in each bin cannot exceed its capacity.
for b in all_bins:
    model.add(
        sum(x[i, b] * data["weights"][i] for i in all_items)
        <= data["bin_capacities"][b]
    )

C++

// Each item is assigned to at most one bin.
for (int i : all_items) {
  std::vector<BoolVar> copies;
  for (int b : all_bins) {
    copies.push_back(x[std::make_tuple(i, b)]);
  }
  cp_model.AddAtMostOne(copies);
}

// The amount packed in each bin cannot exceed its capacity.
for (int b : all_bins) {
  LinearExpr bin_weight;
  for (int i : all_items) {
    bin_weight += x[std::make_tuple(i, b)] * weights[i];
  }
  cp_model.AddLessOrEqual(bin_weight, bin_capacities[b]);
}

Java

// Each item is assigned to at most one bin.
for (int i : allItems) {
  List<Literal> bins = new ArrayList<>();
  for (int b : allBins) {
    bins.add(x[i][b]);
  }
  model.addAtMostOne(bins);
}

// The amount packed in each bin cannot exceed its capacity.
for (int b : allBins) {
  LinearExprBuilder load = LinearExpr.newBuilder();
  for (int i : allItems) {
    load.addTerm(x[i][b], weights[i]);
  }
  model.addLessOrEqual(load, binCapacities[b]);
}

C#

// Each item is assigned to at most one bin.
foreach (int i in allItems)
{
    List<ILiteral> literals = new List<ILiteral>();
    foreach (int b in allBins)
    {
        literals.Add(x[i, b]);
    }
    model.AddAtMostOne(literals);
}

// The amount packed in each bin cannot exceed its capacity.
foreach (int b in allBins)
{
    List<ILiteral> items = new List<ILiteral>();
    foreach (int i in allItems)
    {
        items.Add(x[i, b]);
    }
    model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
}

目的関数を作成する

次のコードは、問題の目的関数を作成します。

Python

# maximize total value of packed items.
objective = []
for i in all_items:
    for b in all_bins:
        objective.append(cp_model.LinearExpr.term(x[i, b], data["values"][i]))
model.maximize(cp_model.LinearExpr.sum(objective))

C++

// Maximize total value of packed items.
LinearExpr objective;
for (int i : all_items) {
  for (int b : all_bins) {
    objective += x[std::make_tuple(i, b)] * values[i];
  }
}
cp_model.Maximize(objective);

Java

// Maximize total value of packed items.
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int i : allItems) {
  for (int b : allBins) {
    obj.addTerm(x[i][b], values[i]);
  }
}
model.maximize(obj);

C#

LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        obj.AddTerm(x[i, b], Values[i]);
    }
}
model.Maximize(obj);

目的関数の値は、モデルに割り当てられたすべての変数の 1 とします。

ソルバーを呼び出す

次のコードはソルバーを呼び出します。

Python

solver = cp_model.CpSolver()
status = solver.solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

Java

CpSolver solver = new CpSolver();
final CpSolverStatus status = solver.solve(model);

C#

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);

解答を印刷

次のコードは、問題の解答を表示します。

Python

if status == cp_model.OPTIMAL:
    print(f"Total packed value: {solver.objective_value}")
    total_weight = 0
    for b in all_bins:
        print(f"Bin {b}")
        bin_weight = 0
        bin_value = 0
        for i in all_items:
            if solver.value(x[i, b]) > 0:
                print(
                    f'Item:{i} weight:{data["weights"][i]} value:{data["values"][i]}'
                )
                bin_weight += data["weights"][i]
                bin_value += data["values"][i]
        print(f"Packed bin weight: {bin_weight}")
        print(f"Packed bin value: {bin_value}\n")
        total_weight += bin_weight
    print(f"Total packed weight: {total_weight}")
else:
    print("The problem does not have an optimal solution.")

C++

if (response.status() == CpSolverStatus::OPTIMAL ||
    response.status() == CpSolverStatus::FEASIBLE) {
  LOG(INFO) << "Total packed value: " << response.objective_value();
  double total_weight = 0.0;
  for (int b : all_bins) {
    LOG(INFO) << "Bin " << b;
    double bin_weight = 0.0;
    double bin_value = 0.0;
    for (int i : all_items) {
      auto key = std::make_tuple(i, b);
      if (SolutionIntegerValue(response, x[key]) > 0) {
        LOG(INFO) << "Item " << i << " weight: " << weights[i]
                  << " value: " << values[i];
        bin_weight += weights[i];
        bin_value += values[i];
      }
    }
    LOG(INFO) << "Packed bin weight: " << bin_weight;
    LOG(INFO) << "Packed bin value: " << bin_value;
    total_weight += bin_weight;
  }
  LOG(INFO) << "Total packed weight: " << total_weight;
} else {
  LOG(INFO) << "The problem does not have an optimal solution.";
}

Java

// Check that the problem has an optimal solution.
if (status == CpSolverStatus.OPTIMAL) {
  System.out.println("Total packed value: " + solver.objectiveValue());
  long totalWeight = 0;
  for (int b : allBins) {
    long binWeight = 0;
    long binValue = 0;
    System.out.println("Bin " + b);
    for (int i : allItems) {
      if (solver.booleanValue(x[i][b])) {
        System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]);
        binWeight += weights[i];
        binValue += values[i];
      }
    }
    System.out.println("Packed bin weight: " + binWeight);
    System.out.println("Packed bin value: " + binValue);
    totalWeight += binWeight;
  }
  System.out.println("Total packed weight: " + totalWeight);
} else {
  System.err.println("The problem does not have an optimal solution.");
}

C#

// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
    Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
    double TotalWeight = 0.0;
    foreach (int b in allBins)
    {
        double BinWeight = 0.0;
        double BinValue = 0.0;
        Console.WriteLine($"Bin {b}");
        foreach (int i in allItems)
        {
            if (solver.BooleanValue(x[i, b]))
            {
                Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                BinWeight += Weights[i];
                BinValue += Values[i];
            }
        }
        Console.WriteLine("Packed bin weight: " + BinWeight);
        Console.WriteLine("Packed bin value: " + BinValue);
        TotalWeight += BinWeight;
    }
    Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
    Console.WriteLine("No solution found.");
}

プログラムの出力は次のとおりです。

Total packed value: 395.0
Bin  0

Item 3 - weight: 36  value: 50
Item 13 - weight: 36  value: 30
Packed bin weight: 72
Packed bin value: 80

Bin  1

Item 5 - weight: 48  value: 30
Item 7 - weight: 42  value: 40
Packed bin weight: 90
Packed bin value: 70

Bin  2

Item 1 - weight: 30  value: 30
Item 10 - weight: 30  value: 45
Item 14 - weight: 36  value: 25
Packed bin weight: 96
Packed bin value: 100

Bin  3

Item 2 - weight: 42  value: 25
Item 12 - weight: 42  value: 20
Packed bin weight: 84
Packed bin value: 45

Bin  4

Item 4 - weight: 36  value: 35
Item 8 - weight: 36  value: 30
Item 9 - weight: 24  value: 35
Packed bin weight: 96
Packed bin value: 100

Total packed weight: 438

プログラムを完了する

CP-SAT ソリューションの全プログラムは次のとおりです。

Python

"""Solves a multiple knapsack problem using the CP-SAT solver."""
from ortools.sat.python import cp_model


def main() -> None:
    data = {}
    data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    assert len(data["weights"]) == len(data["values"])
    num_items = len(data["weights"])
    all_items = range(num_items)

    data["bin_capacities"] = [100, 100, 100, 100, 100]
    num_bins = len(data["bin_capacities"])
    all_bins = range(num_bins)

    model = cp_model.CpModel()

    # Variables.
    # x[i, b] = 1 if item i is packed in bin b.
    x = {}
    for i in all_items:
        for b in all_bins:
            x[i, b] = model.new_bool_var(f"x_{i}_{b}")

    # Constraints.
    # Each item is assigned to at most one bin.
    for i in all_items:
        model.add_at_most_one(x[i, b] for b in all_bins)

    # The amount packed in each bin cannot exceed its capacity.
    for b in all_bins:
        model.add(
            sum(x[i, b] * data["weights"][i] for i in all_items)
            <= data["bin_capacities"][b]
        )

    # Objective.
    # maximize total value of packed items.
    objective = []
    for i in all_items:
        for b in all_bins:
            objective.append(cp_model.LinearExpr.term(x[i, b], data["values"][i]))
    model.maximize(cp_model.LinearExpr.sum(objective))

    solver = cp_model.CpSolver()
    status = solver.solve(model)

    if status == cp_model.OPTIMAL:
        print(f"Total packed value: {solver.objective_value}")
        total_weight = 0
        for b in all_bins:
            print(f"Bin {b}")
            bin_weight = 0
            bin_value = 0
            for i in all_items:
                if solver.value(x[i, b]) > 0:
                    print(
                        f'Item:{i} weight:{data["weights"][i]} value:{data["values"][i]}'
                    )
                    bin_weight += data["weights"][i]
                    bin_value += data["values"][i]
            print(f"Packed bin weight: {bin_weight}")
            print(f"Packed bin value: {bin_value}\n")
            total_weight += bin_weight
        print(f"Total packed weight: {total_weight}")
    else:
        print("The problem does not have an optimal solution.")


if __name__ == "__main__":
    main()

C++

// Solves a multiple knapsack problem using the CP-SAT solver.
#include <stdlib.h>

#include <map>
#include <numeric>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void MultipleKnapsackSat() {
  const std::vector<int> weights = {
      {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}};
  const std::vector<int> values = {
      {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}};
  const int num_items = static_cast<int>(weights.size());
  std::vector<int> all_items(num_items);
  std::iota(all_items.begin(), all_items.end(), 0);

  const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
  const int num_bins = static_cast<int>(bin_capacities.size());
  std::vector<int> all_bins(num_bins);
  std::iota(all_bins.begin(), all_bins.end(), 0);

  CpModelBuilder cp_model;

  // Variables.
  // x[i, b] = 1 if item i is packed in bin b.
  std::map<std::tuple<int, int>, BoolVar> x;
  for (int i : all_items) {
    for (int b : all_bins) {
      auto key = std::make_tuple(i, b);
      x[key] = cp_model.NewBoolVar().WithName(absl::StrFormat("x_%d_%d", i, b));
    }
  }

  // Constraints.
  // Each item is assigned to at most one bin.
  for (int i : all_items) {
    std::vector<BoolVar> copies;
    for (int b : all_bins) {
      copies.push_back(x[std::make_tuple(i, b)]);
    }
    cp_model.AddAtMostOne(copies);
  }

  // The amount packed in each bin cannot exceed its capacity.
  for (int b : all_bins) {
    LinearExpr bin_weight;
    for (int i : all_items) {
      bin_weight += x[std::make_tuple(i, b)] * weights[i];
    }
    cp_model.AddLessOrEqual(bin_weight, bin_capacities[b]);
  }

  // Objective.
  // Maximize total value of packed items.
  LinearExpr objective;
  for (int i : all_items) {
    for (int b : all_bins) {
      objective += x[std::make_tuple(i, b)] * values[i];
    }
  }
  cp_model.Maximize(objective);

  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL ||
      response.status() == CpSolverStatus::FEASIBLE) {
    LOG(INFO) << "Total packed value: " << response.objective_value();
    double total_weight = 0.0;
    for (int b : all_bins) {
      LOG(INFO) << "Bin " << b;
      double bin_weight = 0.0;
      double bin_value = 0.0;
      for (int i : all_items) {
        auto key = std::make_tuple(i, b);
        if (SolutionIntegerValue(response, x[key]) > 0) {
          LOG(INFO) << "Item " << i << " weight: " << weights[i]
                    << " value: " << values[i];
          bin_weight += weights[i];
          bin_value += values[i];
        }
      }
      LOG(INFO) << "Packed bin weight: " << bin_weight;
      LOG(INFO) << "Packed bin value: " << bin_value;
      total_weight += bin_weight;
    }
    LOG(INFO) << "Total packed weight: " << total_weight;
  } else {
    LOG(INFO) << "The problem does not have an optimal solution.";
  }

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
}
}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::MultipleKnapsackSat();
  return EXIT_SUCCESS;
}

Java

// Solves a multiple knapsack problem using the CP-SAT solver.
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Sample showing how to solve a multiple knapsack problem. */
public class MultipleKnapsackSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Instantiate the data problem.
    final int[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    final int[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    final int numItems = weights.length;
    final int[] allItems = IntStream.range(0, numItems).toArray();

    final int[] binCapacities = {100, 100, 100, 100, 100};
    final int numBins = binCapacities.length;
    final int[] allBins = IntStream.range(0, numBins).toArray();

    CpModel model = new CpModel();

    // Variables.
    Literal[][] x = new Literal[numItems][numBins];
    for (int i : allItems) {
      for (int b : allBins) {
        x[i][b] = model.newBoolVar("x_" + i + "_" + b);
      }
    }

    // Constraints.
    // Each item is assigned to at most one bin.
    for (int i : allItems) {
      List<Literal> bins = new ArrayList<>();
      for (int b : allBins) {
        bins.add(x[i][b]);
      }
      model.addAtMostOne(bins);
    }

    // The amount packed in each bin cannot exceed its capacity.
    for (int b : allBins) {
      LinearExprBuilder load = LinearExpr.newBuilder();
      for (int i : allItems) {
        load.addTerm(x[i][b], weights[i]);
      }
      model.addLessOrEqual(load, binCapacities[b]);
    }

    // Objective.
    // Maximize total value of packed items.
    LinearExprBuilder obj = LinearExpr.newBuilder();
    for (int i : allItems) {
      for (int b : allBins) {
        obj.addTerm(x[i][b], values[i]);
      }
    }
    model.maximize(obj);

    CpSolver solver = new CpSolver();
    final CpSolverStatus status = solver.solve(model);

    // Check that the problem has an optimal solution.
    if (status == CpSolverStatus.OPTIMAL) {
      System.out.println("Total packed value: " + solver.objectiveValue());
      long totalWeight = 0;
      for (int b : allBins) {
        long binWeight = 0;
        long binValue = 0;
        System.out.println("Bin " + b);
        for (int i : allItems) {
          if (solver.booleanValue(x[i][b])) {
            System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]);
            binWeight += weights[i];
            binValue += values[i];
          }
        }
        System.out.println("Packed bin weight: " + binWeight);
        System.out.println("Packed bin value: " + binValue);
        totalWeight += binWeight;
      }
      System.out.println("Total packed weight: " + totalWeight);
    } else {
      System.err.println("The problem does not have an optimal solution.");
    }
  }

  private MultipleKnapsackSat() {}
}

C#

// Solves a multiple knapsack problem using the CP-SAT solver.
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class MultipleKnapsackSat
{
    public static void Main(String[] args)
    {
        // Instantiate the data problem.
        int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
        int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
        int NumItems = Weights.Length;
        int[] allItems = Enumerable.Range(0, NumItems).ToArray();

        int[] BinCapacities = { 100, 100, 100, 100, 100 };
        int NumBins = BinCapacities.Length;
        int[] allBins = Enumerable.Range(0, NumBins).ToArray();

        // Model.
        CpModel model = new CpModel();

        // Variables.
        ILiteral[,] x = new ILiteral[NumItems, NumBins];
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                x[i, b] = model.NewBoolVar($"x_{i}_{b}");
            }
        }

        // Constraints.
        // Each item is assigned to at most one bin.
        foreach (int i in allItems)
        {
            List<ILiteral> literals = new List<ILiteral>();
            foreach (int b in allBins)
            {
                literals.Add(x[i, b]);
            }
            model.AddAtMostOne(literals);
        }

        // The amount packed in each bin cannot exceed its capacity.
        foreach (int b in allBins)
        {
            List<ILiteral> items = new List<ILiteral>();
            foreach (int i in allItems)
            {
                items.Add(x[i, b]);
            }
            model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
        }

        // Objective.
        LinearExprBuilder obj = LinearExpr.NewBuilder();
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                obj.AddTerm(x[i, b], Values[i]);
            }
        }
        model.Maximize(obj);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        // Print solution.
        // Check that the problem has a feasible solution.
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
            double TotalWeight = 0.0;
            foreach (int b in allBins)
            {
                double BinWeight = 0.0;
                double BinValue = 0.0;
                Console.WriteLine($"Bin {b}");
                foreach (int i in allItems)
                {
                    if (solver.BooleanValue(x[i, b]))
                    {
                        Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                        BinWeight += Weights[i];
                        BinValue += Values[i];
                    }
                }
                Console.WriteLine("Packed bin weight: " + BinWeight);
                Console.WriteLine("Packed bin value: " + BinValue);
                TotalWeight += BinWeight;
            }
            Console.WriteLine("Total packed weight: " + TotalWeight);
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}