Questa sezione mostra come risolvere il problema degli zaini per più zaini utilizzando sia il risolutore MIP che il risolutore CP-SAT. In questo caso, spesso fanno riferimento ai container come bin, anziché come zaini.
L'esempio seguente mostra come trovare il modo ottimale per confezionare gli articoli in cinque contenitori.
Esempio
Come nell'esempio precedente, inizi con una raccolta di elementi con ponderazioni e valori diversi. Il problema consiste nel creare un sottoinsieme di elementi in cinque contenitori, ognuno dei quali ha una capacità massima di 100, in modo che il valore totale pacchettizzato sia un massimo.
Le seguenti sezioni presentano sezioni di programmi che risolvono questo problema. Per la versione completa dei programmi, vedi Programmi completi.
Soluzione MIP
Le seguenti sezioni descrivono come risolvere il problema utilizzando il wrapper MPSolver.
Importa le librerie
Il codice seguente importa le librerie necessarie.
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;
Creare i dati
Il seguente codice crea i dati per il problema.
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();
tra cui:
weights: un vettore che contiene le ponderazioni degli elementi.values: un vettore che contiene i valori degli elementi.capacities: un vettore contenente le capacità dei bin.
In questo esempio, tutti i contenitori hanno la stessa capacità, ma in generale non è necessario che siano vere.
Dichiara il risolutore MIP
Nel codice seguente viene dichiarato il risolutore 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;
}
Creare le variabili
Il seguente codice crea le variabili per il problema.
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}");
}
}
Ogni x[(i, j)] è una variabile 0-1, dove i è un elemento e j è un cestino. Nella soluzione, x[(i, j)] sarà 1 se l'elemento i è posizionato nel cestino j, altrimenti 0.
Definisci i vincoli
Il seguente codice definisce i vincoli per il problema:
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]);
}
}
I vincoli sono i seguenti:
- Ogni elemento può essere posizionato al massimo in un contenitore. Questo vincolo è impostato richiedendo che la somma di
x[i, j]per tutti i binjsia inferiore o uguale a 1. - Il peso totale imballato in ogni contenitore non può superare la sua capacità. Questo
vincolo viene impostato richiedendo che la somma delle ponderazioni degli elementi inseriti nel cestino
jsia inferiore o uguale alla capacità del contenitore.
Definisci l'obiettivo
Il seguente codice definisce la funzione oggettiva del problema, ovvero il valore totale degli articoli pacchettizzati.
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();
Tieni presente che x[i, j] * data['values'][i] aggiunge il valore i dell'elemento all'obiettivo se quest'ultimo viene posizionato nel cestino j. Se i non viene inserito in alcun contenitore, il suo valore non contribuisce all'obiettivo.
Richiama il risolutore
Il codice seguente richiama il risolutore.
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();
Stampa la soluzione
Il seguente codice stampa la soluzione al problema.
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: {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!");
}
Per ogni bin, il codice mostra gli elementi posizionati in quel bin, nonché il valore totale e la ponderazione del bin. Il codice mostra anche il valore complessivo e la ponderazione degli articoli pacchettizzati.
Quando esegui il programma, viene visualizzato il seguente output.
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
Completare i programmi
Di seguito sono riportati i programmi completi per più zaini.
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: {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!");
}
}
}
Soluzione CP SAT
Le seguenti sezioni descrivono come risolvere il problema utilizzando il risolutore CP-SAT.
Importa le librerie
Il codice seguente importa le librerie necessarie.
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");
}
}
Dichiara il modello
Nel codice seguente viene dichiarato il modello CP-SAT.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Creare i dati
Il seguente codice configura i dati per il problema.
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 = 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();
L'array costs corrisponde alla tabella dei costi
per l'assegnazione dei worker alle attività, come mostrato in precedenza.
Creare le variabili
Il seguente codice crea variabili binarie del problema per il problema in questione.
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] = model.NewBoolVar(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}");
}
}
Creare i vincoli
Il seguente codice crea i vincoli per il problema.
Python
# Each item is assigned to at most one bin.
for i in data["all_items"]:
model.AddAtMostOne(x[i, b] for b in data["all_bins"])
# The amount packed in each bin cannot exceed its capacity.
for b in data["all_bins"]:
model.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) {
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]);
}
Crea la funzione dell'obiettivo
Il seguente codice crea la funzione oggettiva del problema.
Python
# Maximize total value of packed items.
objective = []
for i in data["all_items"]:
for b in data["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);
Il valore della funzione oggettiva è il costo totale su tutte le variabili a cui viene assegnato il valore 1 dal risolutore.
Richiama il risolutore
Il codice seguente richiama il risolutore.
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);
Stampa la soluzione
Il seguente codice stampa la soluzione al problema.
Python
if status == cp_model.OPTIMAL:
print(f"Total packed value: {solver.ObjectiveValue()}")
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 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.");
}
Ecco l'output del programma.
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
Completare i programmi
Ecco i programmi completi per la soluzione CP-SAT.
Python
"""Solves a multiple knapsack problem using the CP-SAT solver."""
from ortools.sat.python import cp_model
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"])
model = cp_model.CpModel()
# 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] = model.NewBoolVar(f"x_{i}_{b}")
# Constraints.
# Each item is assigned to at most one bin.
for i in data["all_items"]:
model.AddAtMostOne(x[i, b] for b in data["all_bins"])
# The amount packed in each bin cannot exceed its capacity.
for b in data["all_bins"]:
model.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 = []
for i in data["all_items"]:
for b in data["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.ObjectiveValue()}")
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 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");
}
}