En esta sección, se muestra cómo resolver el problema de la mochila para múltiples mochilas mediante el solucionador de MIP y el solucionador de CP-SAT. En este caso, es común referirse a los contenedores como discretizaciones, en lugar de mochilas.
En el siguiente ejemplo, se muestra cómo encontrar la forma óptima de agrupar los elementos en cinco discretizaciones.
Ejemplo
Al igual que en el ejemplo anterior, se comienza con una colección de elementos de diferentes pesos y valores. El problema es empaquetar un subconjunto de los elementos en cinco discretizaciones, cada una de las cuales tiene una capacidad máxima de 100, para que el valor empaquetado total sea el máximo.
En las siguientes secciones, se presentan secciones de programas que resuelven este problema. Para ver los programas completos, consulta Programas completos.
Solución del MIP
En las siguientes secciones, se describe cómo resolver el problema con el wrapper de MPSolver.
Importa las bibliotecas
El siguiente código importa las bibliotecas requeridas.
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;
Crea los datos
El siguiente código crea los datos del 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();
Los datos incluyen lo siguiente:
weights: Un vector que contiene los pesos de los elementos.values: Un vector que contiene los valores de los elementos.capacities: Un vector que contiene las capacidades de las discretizaciones.
En este ejemplo, todos los contenedores tienen la misma capacidad, pero no es necesario que sea así en general.
Declara el agente de resolución de MIP
En el siguiente código, se declara la resolución de problemas del 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;
}
Crea las variables
El siguiente código crea las variables del 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}");
}
}
Cada x[(i, j)] es una variable de 0 a 1, en la que i es un elemento y j es un contenedor. En la solución, x[(i, j)] será 1 si el elemento i se coloca en la papelera j; de lo contrario, 0.
Define las restricciones
El siguiente código define las restricciones del 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]);
}
}
Las restricciones son las siguientes:
- Cada artículo puede colocarse como máximo un contenedor. Para esta restricción, se requiere que la suma de
x[i, j]en todas las discretizacionesjsea menor o igual que 1. - El peso total empaquetado en cada discretización no puede superar su capacidad. Para esta restricción, se requiere que la suma de los pesos de los elementos ubicados en la discretización
jsea menor o igual que la capacidad de la discretización.
Define el objetivo
El siguiente código define la función objetivo del problema, que es el valor total de los elementos empaquetados.
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();
Ten en cuenta que x[i, j] * data['values'][i] agrega el valor del elemento i al objetivo si el elemento se coloca en la papelera j. Si i no se coloca en ninguna discretización, su valor no contribuye al objetivo.
Invoca la resolución
El siguiente código invoca el agente de resolución.
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();
Imprimir la solución
El siguiente código imprime la solución 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!");
}
Para cada discretización, el código muestra los elementos que se colocaron, así como el valor y el peso totales de la discretización. El código también muestra el valor total general y el peso de los elementos empaquetados.
Cuando ejecutes el programa, se mostrará el siguiente resultado.
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
Programas completos
A continuación, se muestran los programas completos para las mochilas.
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!");
}
}
}
Solución de PC SAT
En las siguientes secciones, se describe cómo resolver el problema con el solucionador de CP-SAT.
Importa las bibliotecas
El siguiente código importa las bibliotecas requeridas.
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");
}
}
Declara el modelo
El siguiente código declara el modelo CP-SAT.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Crea los datos
El siguiente código configura los datos para el 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();
El arreglo costs corresponde a la tabla de costos por los trabajadores asignados a las tareas que se muestran arriba.
Crea las variables
El siguiente código crea variables binarias binarias para el 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] = 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}");
}
}
Crea las restricciones
El siguiente código crea las restricciones para el 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 función objetiva
El siguiente código crea la función objetiva 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);
El valor de la función objetivo es el costo total de todas las variables que el solucionador asigna al valor 1.
Invoca la resolución
El siguiente código invoca el agente de resolución.
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);
Imprimir la solución
El siguiente código imprime la solución 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.");
}
Este es el resultado del programa.
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
Programas completos
Estos son los programas completos para la solución 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");
}
}