Résoudre un problème de sac à dos multiple

Cette section explique comment résoudre le problème de plusieurs sacs à dos. en utilisant à la fois le solutionur MIP et le résolveur CP-SAT. Dans ce cas, il est courant de faire référence aux conteneurs en tant que classes, au lieu de que des sacs à dos.

L'exemple suivant montre comment trouver la meilleure façon de regrouper les éléments dans cinq bacs.

Exemple

Comme dans l'exemple précédent, vous commencez avec collection d’éléments de poids et de valeurs variables. Le problème est d'emballer un sous-ensemble d'éléments dans cinq bins, chacun d'entre eux ayant une capacité maximale de 100, afin que la valeur totale empaquetée soit un maximum.

Les sections suivantes présentent des sections de programmes qui résolvent ce problème. Pour connaître les programmes complets, consultez l'article Terminer les programmes.

Solution MIP

Les sections suivantes décrivent comment résoudre le problème à l'aide des Wrapper MPSolver.

Importer les bibliothèques

Le code suivant importe les bibliothèques requises.

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;

Créer les données

Le code suivant crée les données correspondant au problème.

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();

Ces données incluent les éléments suivants:

  • weights: vecteur contenant les pondérations des éléments.
  • values: vecteur contenant les valeurs des éléments.
  • capacities: vecteur contenant les capacités des classes.

Dans cet exemple, tous les bins ont la même capacité, mais cela n'a pas besoin d'être vrai. en général.

Déclarer la solution MIP

Le code suivant déclare le résolveur 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;
}

Créer les variables

Le code suivant crée les variables correspondant au problème.

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}");
    }
}

Chaque x[(i, j)] est une variable de 0 à 1, où i est un élément et j un bin. Dans la solution, x[(i, j)] sera égal à 1 si l'élément i est placé dans la classe j, et 0 ; sinon.

Définir les contraintes

Le code suivant définit les contraintes du problème:

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]);
    }
}

Les contraintes sont les suivantes:

  • Chaque élément ne peut être placé que dans un seul bin. Cette contrainte est définie par nécessitant que la somme des x[i, j] sur tous les bins j soit inférieure ou égale à à 1.
  • Le poids total de chaque compartiment ne peut pas dépasser sa capacité. Ce est définie en exigeant la somme des pondérations des éléments placés dans la classe j doit être inférieure ou égale à la capacité du bin.

Définir l’objectif

Le code suivant définit la fonction objectif du problème, à savoir la valeur totale des articles emballés.

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();

Notez que x[i, j] * data['values'][i] ajoute la valeur de l'élément i au objectif si l'élément est placé dans la classe j. Si i n'est placé dans aucun bin, son la valeur ne contribue pas à l’objectif.

Appeler le résolveur

Le code suivant appelle le résolveur.

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();

Le code suivant affiche la solution au problème.

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!");
}

Pour chaque bin, le code affiche les éléments placés dans ce bin, ainsi que les la valeur totale et la pondération. Le code affiche également la valeur totale globale et poids des articles emballés.

Lorsque vous exécutez le programme, le résultat suivant s'affiche :

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

Terminer les programmes

Les programmes complets pour plusieurs sacs à dos sont présentés ci-dessous.

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!");
        }
    }
}

Solution CP SAT

Les sections suivantes décrivent comment résoudre le problème à l'aide du résolveur CP-SAT.

Importer les bibliothèques

Le code suivant importe les bibliothèques requises.

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");
    }
}

Déclarer le modèle

Le code suivant déclare le modèle CP-SAT.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

Créer les données

Le code suivant configure les données du problème.

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();

Le tableau costs correspond au tableau des coûts permettant d'attribuer des nœuds de calcul à des tâches, comme illustré ci-dessus.

Créer les variables

Le code suivant crée des variables entières binaires pour le problème.

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}");
    }
}

Créer les contraintes

Le code suivant crée les contraintes pour le problème.

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]);
}

Créer la fonction objectif

Le code suivant crée la fonction objectif pour le problème.

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);

La valeur de la fonction objectif est le coût total pour toutes les variables auxquelles est attribuée valeur 1 par le résolveur.

Appeler le résolveur

Le code suivant appelle le résolveur.

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);

Le code suivant affiche la solution au problème.

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.");
}

Voici la sortie du programme.

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

Terminer les programmes

Voici les programmes complets de la solution 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");
    }
}