פתרון בעיות של כמה נסיכים

בקטע הזה מוסבר איך לפתור את בעיית תרמיל ה-KMS במספר תיקי גב באמצעות פותר MIP וגם פותר CP-SAT. במקרה כזה, מקובל להתייחס למאגרי תגים בתור bins, ולא מאשר תרמילים.

בדוגמה הבאה מוסבר איך למצוא את הדרך האופטימלית לארוז פריטים בחמישה פחים.

דוגמה

כמו בדוגמה הקודמת, צריך להתחיל עם של פריטים בעלי משקולות וערכים שונים. הבעיה היא לארוז קבוצת משנה של הפריטים לחמישה פחים, שכל אחד מהם יכול להכיל עד 100 פריטים, כך שהערך הכולל הארוז הוא הערך המקסימלי.

בקטעים הבאים מוצגים קטעים של תוכניות שפותרות את הבעיה הזו. למידע על התוכניות המלאות, ראו השלמת תוכניות.

פתרון MIP

בקטעים הבאים מתואר איך לפתור את הבעיה באמצעות MPSolver wrapper

ייבוא הספריות

הקוד הבא מייבא את הספריות הנדרשות.

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 הוא סל. לחשבון הפתרון, הערך x[(i, j)] יהיה 1 אם הפריט i מוצב בסל j ו-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]);
    }
}

המגבלות הן:

• ניתן להכניס כל פריט לכל פח. האילוץ הזה מוגדר על ידי דרישה שהסכום של 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");
    }
}