Bagian ini menunjukkan cara menyelesaikan masalah knapsack untuk beberapa ransel menggunakan pemecah MIP dan pemecah CP-SAT. Dalam hal ini, biasanya merujuk ke container sebagai bin, bukan knapsack.
Contoh berikutnya menunjukkan cara menemukan cara optimal untuk mengemas item ke dalam lima tempat sampah.
Contoh
Seperti pada contoh sebelumnya, Anda memulai dengan kumpulan item dengan bobot dan nilai yang berbeda. Masalahnya adalah mengemas subkumpulan item menjadi lima tempat, yang masing-masing memiliki kapasitas maksimum 100, sehingga total nilai yang dikemas adalah nilai maksimum.
Bagian berikut menampilkan bagian program yang mengatasi masalah ini. Untuk program selengkapnya, lihat Menyelesaikan program.
Solusi MIP
Bagian berikut menjelaskan cara menyelesaikan masalah menggunakan wrapper Resolver MP.
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
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;
Membuat data
Kode berikut membuat data untuk masalah tersebut.
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();
Data tersebut mencakup hal berikut:
weights: Vektor yang berisi bobot item.values: Vektor yang berisi nilai item.capacities: Vektor yang berisi kapasitas tempat sampah.
Dalam contoh ini, semua kelompok memiliki kapasitas yang sama, tetapi hal tersebut tidak benar secara umum.
Mendeklarasikan pemecah MIP
Kode berikut mendeklarasikan pemecah 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;
}
Membuat variabel
Kode berikut membuat variabel untuk masalah.
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}");
}
}
Setiap x[(i, j)] adalah variabel 0-1, dengan i sebagai item dan j berupa sampah. Dalam
solusi ini, x[(i, j)] akan menjadi 1 jika item i ditempatkan di bin j, dan 0
jika tidak.
Menentukan batasan
Kode berikut menentukan batasan untuk masalah tersebut:
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]);
}
}
Batasannya adalah sebagai berikut:
- Setiap item dapat ditempatkan di maksimum satu tempat sampah. Batasan ini ditetapkan dengan
memerlukan jumlah
x[i, j]atas semua kelompokjagar kurang dari atau sama dengan 1. - Total berat yang dikemas dalam setiap tempat sampah tidak boleh melebihi kapasitasnya. Batasan ini ditetapkan dengan mengharuskan jumlah bobot item yang ditempatkan di sampah
jkurang dari atau sama dengan kapasitas tempat sampah.
Tentukan tujuan
Kode berikut menentukan fungsi objektif untuk masalah tersebut, yang merupakan nilai total item yang dikemas.
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();
Perhatikan bahwa x[i, j] * data['values'][i] menambahkan nilai item i ke objektif jika item ditempatkan di tempat sampah j. Jika i tidak ditempatkan di tempat sampah mana pun, nilainya tidak akan berkontribusi pada objektif.
Panggil pemecah soal
Kode berikut memanggil pemecah soal.
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();
Cetak solusi
Kode berikut akan mencetak solusi untuk masalah tersebut.
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!");
}
Untuk setiap kelompok, kode ini menampilkan item yang ditempatkan dalam kelompok tersebut, beserta nilai total dan berat kumpulan. Kode ini juga menampilkan nilai total keseluruhan dan bobot item yang dikemas.
Saat Anda menjalankan program, program akan menampilkan output berikut.
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
Selesaikan program
Program lengkap untuk beberapa ransel ditampilkan di bawah ini.
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!");
}
}
}
Solusi CP SAT
Bagian berikut menjelaskan cara menyelesaikan soal menggunakan pemecah soal CP-SAT.
Mengimpor library
Kode berikut mengimpor library yang diperlukan.
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");
}
}
Mendeklarasikan model
Kode berikut mendeklarasikan model CP-SAT.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Membuat data
Kode berikut menyiapkan data untuk masalah tersebut.
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();
Array costs sesuai dengan tabel biaya
untuk menetapkan pekerja ke tugas, yang ditunjukkan di atas.
Membuat variabel
Kode berikut membuat variabel bilangan bulat biner untuk masalah.
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}");
}
}
Membuat batasan
Kode berikut membuat batasan untuk masalah tersebut.
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]);
}
Membuat fungsi tujuan
Kode berikut membuat fungsi tujuan untuk masalah.
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);
Nilai fungsi tujuan adalah total biaya di atas semua variabel yang diberi nilai 1 oleh pemecah soal.
Panggil pemecah soal
Kode berikut memanggil pemecah soal.
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);
Cetak solusi
Kode berikut akan mencetak solusi untuk masalah tersebut.
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.");
}
Berikut adalah output program.
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
Selesaikan program
Berikut adalah program lengkap untuk solusi 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");
}
}