Bu bölümde birden fazla sırt çantası için sırt çantasının nasıl çözüleceği gösterilmektedir hem MIP çözücü hem de CP-SAT çözücüyü kullanmaktır. Bu durumda, kapsayıcılara yerine bins sırt çantalarından çok daha iyidir.
Sonraki örnekte öğeleri beş bölmeye yerleştirmenin en iyi yolunun nasıl bulunacağı gösterilmektedir.
Örnek
Önceki örnekte olduğu gibi, bir Çeşitli ağırlık ve değerlere sahip öğeler koleksiyonu. Sorun, bu belgeyi Bu öğelerin her biri maksimum 100 kapasiteye sahip beş bölmeye Böylece paketlenen toplam değer maksimum değer olur.
Aşağıdaki bölümlerde bu sorunu çözen program bölümleri sunulmaktadır. Programların tam listesi için Programları tamamlama başlıklı makaleye bakın.
MIP çözümü
Aşağıdaki bölümlerde, MPSolver sarmalayıcı.
Kitaplıkları içe aktarma
Aşağıdaki kodda gerekli kitaplıkları içe aktarır.
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;
Verileri oluşturma
Aşağıdaki kod, sorunla ilgili verileri oluşturur.
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();Veriler şunları içerir:
weights: Öğelerin ağırlıklarını içeren bir vektör.values: Öğelerin değerlerini içeren bir vektör.capacities: Bölmelerin kapasitelerini içeren bir vektör.
Bu örnekte tüm bölmeler aynı kapasiteye sahiptir ancak bu kapasitenin doğru olması gerekmez. emin olabilirsiniz.
MIP çözücüyü tanımlama
Aşağıdaki kod MIP çözücüyü tanımlar.
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; }
Değişkenleri oluşturma
Aşağıdaki kod, sorun için değişkenleri oluşturur.
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}");
}
}Her x[(i, j)] 0-1 arası bir değişkendir. i bir öğe, j ise bir bölmedir. İçinde
i öğesi j bölmesine yerleştirilirse x[(i, j)] 1 ve 0 olur
aksi takdirde.
Kısıtlamaları tanımlama
Aşağıdaki kod, soruna ilişkin kısıtlamaları tanımlar:
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]); } }
Kısıtlamalar şunlardır:
- Her öğe en fazla bir bölmeye yerleştirilebilir. Bu kısıtlama,
tüm
jbölmeleri içinx[i, j]toplamının en az veya eşit olması gerekir 1 olarak ayarladı. - Her bir bölmede paketlenen toplam ağırlık kapasitesini aşamaz. Bu
sınırlama, bölmeye yerleştirilen öğelerin ağırlıklarının toplamının zorunlu kılınmasıyla ayarlanır.
j, bölmenin kapasitesinden küçük veya ona eşit olmalıdır.
Hedefi tanımlama
Aşağıdaki kod, problem için hedef işlevini tanımlar. toplam değeri için belirlemelisiniz.
Python
# Maximize total value of packed items. objective = solver.Objective() for i in data["all_items"]: for b in data["all_bins"]: objective.SetCoefficient(x[i, b], data["values"][i]) objective.SetMaximization()
C++
// Maximize total value of packed items. MPObjective* const objective = solver->MutableObjective(); LinearExpr objective_value; for (int i : all_items) { for (int b : all_bins) { objective_value += LinearExpr(x[i][b]) * values[i]; } } objective->MaximizeLinearExpr(objective_value);
Java
// Maximize total value of packed items. MPObjective objective = solver.objective(); for (int i : allItems) { for (int b : allBins) { objective.setCoefficient(x[i][b], values[i]); } } objective.setMaximization();
C#
Objective objective = solver.Objective(); foreach (int i in allItems) { foreach (int b in allBins) { objective.SetCoefficient(x[i, b], Values[i]); } } objective.SetMaximization();
x[i, j] * data['values'][i] işlevinin, i öğesinin değerini
hedef j bölmesine yerleştirilir. i herhangi bir bölmeye yerleştirilmezse,
hedefe katkıda bulunmaz.
Çözücüyü çağır
Aşağıdaki kod çözücüyü çağırır.
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();
Çözümü yazdırın
Aşağıdaki kod sorunun çözümünü yazdırır.
Python
if status == pywraplp.Solver.OPTIMAL: print(f"Total packed value: {objective.Value()}") total_weight = 0 for b in data["all_bins"]: print(f"Bin {b}") bin_weight = 0 bin_value = 0 for i in data["all_items"]: if x[i, b].solution_value() > 0: print( f"Item {i} weight: {data['weights'][i]} value:" f" {data['values'][i]}" ) bin_weight += data["weights"][i] bin_value += data["values"][i] print(f"Packed bin weight: {bin_weight}") print(f"Packed bin value: {bin_value}\n") total_weight += bin_weight print(f"Total packed weight: {total_weight}") else: print("The problem does not have an optimal solution.")
C++
if (result_status == MPSolver::OPTIMAL) { LOG(INFO) << "Total packed value: " << objective->Value(); double total_weight = 0.0; for (int b : all_bins) { LOG(INFO) << "Bin " << b; double bin_weight = 0.0; double bin_value = 0.0; for (int i : all_items) { if (x[i][b]->solution_value() > 0) { LOG(INFO) << "Item " << i << " weight: " << weights[i] << " value: " << values[i]; bin_weight += weights[i]; bin_value += values[i]; } } LOG(INFO) << "Packed bin weight: " << bin_weight; LOG(INFO) << "Packed bin value: " << bin_value; total_weight += bin_weight; } LOG(INFO) << "Total packed weight: " << total_weight; } else { LOG(INFO) << "The problem does not have an optimal solution."; }
Java
// Check that the problem has an optimal solution. if (status == MPSolver.ResultStatus.OPTIMAL) { System.out.println("Total packed value: " + objective.value()); double totalWeight = 0; for (int b : allBins) { double binWeight = 0; double binValue = 0; System.out.println("Bin " + b); for (int i : allItems) { if (x[i][b].solutionValue() == 1) { System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]); binWeight += weights[i]; binValue += values[i]; } } System.out.println("Packed bin weight: " + binWeight); System.out.println("Packed bin value: " + binValue); totalWeight += binWeight; } System.out.println("Total packed weight: " + totalWeight); } else { System.err.println("The problem does not have an optimal solution."); }
C#
// Check that the problem has an optimal solution. if (resultStatus == Solver.ResultStatus.OPTIMAL) { Console.WriteLine($"Total packed value: {solver.Objective().Value()}"); double TotalWeight = 0.0; foreach (int b in allBins) { double BinWeight = 0.0; double BinValue = 0.0; Console.WriteLine("Bin " + b); foreach (int i in allItems) { if (x[i, b].SolutionValue() == 1) { Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}"); BinWeight += Weights[i]; BinValue += Values[i]; } } Console.WriteLine("Packed bin weight: " + BinWeight); Console.WriteLine("Packed bin value: " + BinValue); TotalWeight += BinWeight; } Console.WriteLine("Total packed weight: " + TotalWeight); } else { Console.WriteLine("The problem does not have an optimal solution!"); }
Kod, her bir bölme için, bu bölmeye yerleştirilen öğeleri ve toplam değer ve ağırlık. Kod, aynı zamanda genel toplam değeri ve ağırlıklandırmasına yardımcı olur.
Programı çalıştırdığınızda aşağıdaki çıktı gösterilir.
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
Programları tamamlama
Birden fazla sırt çantasıyla ilgili programların tamamını aşağıda görebilirsiniz.
Python
"""Solve a multiple knapsack problem using a MIP solver.""" from ortools.linear_solver import pywraplp def main(): data = {} data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36] data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25] assert len(data["weights"]) == len(data["values"]) data["num_items"] = len(data["weights"]) data["all_items"] = range(data["num_items"]) data["bin_capacities"] = [100, 100, 100, 100, 100] data["num_bins"] = len(data["bin_capacities"]) data["all_bins"] = range(data["num_bins"]) # Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver("SCIP") if solver is None: print("SCIP solver unavailable.") return # Variables. # x[i, b] = 1 if item i is packed in bin b. x = {} for i in data["all_items"]: for b in data["all_bins"]: x[i, b] = solver.BoolVar(f"x_{i}_{b}") # Constraints. # Each item is assigned to at most one bin. for i in data["all_items"]: solver.Add(sum(x[i, b] for b in data["all_bins"]) <= 1) # The amount packed in each bin cannot exceed its capacity. for b in data["all_bins"]: solver.Add( sum(x[i, b] * data["weights"][i] for i in data["all_items"]) <= data["bin_capacities"][b] ) # Objective. # Maximize total value of packed items. objective = solver.Objective() for i in data["all_items"]: for b in data["all_bins"]: objective.SetCoefficient(x[i, b], data["values"][i]) objective.SetMaximization() print(f"Solving with {solver.SolverVersion()}") status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print(f"Total packed value: {objective.Value()}") total_weight = 0 for b in data["all_bins"]: print(f"Bin {b}") bin_weight = 0 bin_value = 0 for i in data["all_items"]: if x[i, b].solution_value() > 0: print( f"Item {i} weight: {data['weights'][i]} value:" f" {data['values'][i]}" ) bin_weight += data["weights"][i] bin_value += data["values"][i] print(f"Packed bin weight: {bin_weight}") print(f"Packed bin value: {bin_value}\n") total_weight += bin_weight print(f"Total packed weight: {total_weight}") else: print("The problem does not have an optimal solution.") if __name__ == "__main__": main()
C++
// Solve a multiple knapsack problem using a MIP solver. #include <iostream> #include <memory> #include <numeric> #include <vector> #include "absl/strings/str_format.h" #include "ortools/linear_solver/linear_expr.h" #include "ortools/linear_solver/linear_solver.h" namespace operations_research { void MultipleKnapsackMip() { const std::vector<int> weights = { {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}}; const std::vector<int> values = { {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}}; const int num_items = weights.size(); std::vector<int> all_items(num_items); std::iota(all_items.begin(), all_items.end(), 0); const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}}; const int num_bins = bin_capacities.size(); std::vector<int> all_bins(num_bins); std::iota(all_bins.begin(), all_bins.end(), 0); // Create the mip solver with the SCIP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP")); if (!solver) { LOG(WARNING) << "SCIP solver unavailable."; return; } // Variables. // x[i][b] = 1 if item i is packed in bin b. std::vector<std::vector<const MPVariable*>> x( num_items, std::vector<const MPVariable*>(num_bins)); for (int i : all_items) { for (int b : all_bins) { x[i][b] = solver->MakeBoolVar(absl::StrFormat("x_%d_%d", i, b)); } } // Constraints. // Each item is assigned to at most one bin. for (int i : all_items) { LinearExpr sum; for (int b : all_bins) { sum += x[i][b]; } solver->MakeRowConstraint(sum <= 1.0); } // The amount packed in each bin cannot exceed its capacity. for (int b : all_bins) { LinearExpr bin_weight; for (int i : all_items) { bin_weight += LinearExpr(x[i][b]) * weights[i]; } solver->MakeRowConstraint(bin_weight <= bin_capacities[b]); } // Objective. // Maximize total value of packed items. MPObjective* const objective = solver->MutableObjective(); LinearExpr objective_value; for (int i : all_items) { for (int b : all_bins) { objective_value += LinearExpr(x[i][b]) * values[i]; } } objective->MaximizeLinearExpr(objective_value); const MPSolver::ResultStatus result_status = solver->Solve(); if (result_status == MPSolver::OPTIMAL) { LOG(INFO) << "Total packed value: " << objective->Value(); double total_weight = 0.0; for (int b : all_bins) { LOG(INFO) << "Bin " << b; double bin_weight = 0.0; double bin_value = 0.0; for (int i : all_items) { if (x[i][b]->solution_value() > 0) { LOG(INFO) << "Item " << i << " weight: " << weights[i] << " value: " << values[i]; bin_weight += weights[i]; bin_value += values[i]; } } LOG(INFO) << "Packed bin weight: " << bin_weight; LOG(INFO) << "Packed bin value: " << bin_value; total_weight += bin_weight; } LOG(INFO) << "Total packed weight: " << total_weight; } else { LOG(INFO) << "The problem does not have an optimal solution."; } } } // namespace operations_research int main(int argc, char** argv) { operations_research::MultipleKnapsackMip(); return EXIT_SUCCESS; }
Java
// Solve a multiple knapsack problem using a MIP solver. package com.google.ortools.linearsolver.samples; import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable; import java.util.stream.IntStream; /** Multiple knapsack problem. */ public class MultipleKnapsackMip { public static void main(String[] args) { Loader.loadNativeLibraries(); // Instantiate the data problem. final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}; final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}; final int numItems = weights.length; final int[] allItems = IntStream.range(0, numItems).toArray(); final double[] binCapacities = {100, 100, 100, 100, 100}; final int numBins = binCapacities.length; final int[] allBins = IntStream.range(0, numBins).toArray(); // Create the linear solver with the SCIP backend. MPSolver solver = MPSolver.createSolver("SCIP"); if (solver == null) { System.out.println("Could not create solver SCIP"); return; } // Variables. MPVariable[][] x = new MPVariable[numItems][numBins]; for (int i : allItems) { for (int b : allBins) { x[i][b] = solver.makeBoolVar("x_" + i + "_" + b); } } // Constraints. // Each item is assigned to at most one bin. for (int i : allItems) { MPConstraint constraint = solver.makeConstraint(0, 1, ""); for (int b : allBins) { constraint.setCoefficient(x[i][b], 1); } } // The amount packed in each bin cannot exceed its capacity. for (int b : allBins) { MPConstraint constraint = solver.makeConstraint(0, binCapacities[b], ""); for (int i : allItems) { constraint.setCoefficient(x[i][b], weights[i]); } } // Objective. // Maximize total value of packed items. MPObjective objective = solver.objective(); for (int i : allItems) { for (int b : allBins) { objective.setCoefficient(x[i][b], values[i]); } } objective.setMaximization(); final MPSolver.ResultStatus status = solver.solve(); // Check that the problem has an optimal solution. if (status == MPSolver.ResultStatus.OPTIMAL) { System.out.println("Total packed value: " + objective.value()); double totalWeight = 0; for (int b : allBins) { double binWeight = 0; double binValue = 0; System.out.println("Bin " + b); for (int i : allItems) { if (x[i][b].solutionValue() == 1) { System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]); binWeight += weights[i]; binValue += values[i]; } } System.out.println("Packed bin weight: " + binWeight); System.out.println("Packed bin value: " + binValue); totalWeight += binWeight; } System.out.println("Total packed weight: " + totalWeight); } else { System.err.println("The problem does not have an optimal solution."); } } private MultipleKnapsackMip() {} }
C#
// Solve a multiple knapsack problem using a MIP solver. using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver; public class MultipleKnapsackMip { public static void Main() { // Instantiate the data problem. double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 }; double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 }; int NumItems = Weights.Length; int[] allItems = Enumerable.Range(0, NumItems).ToArray(); double[] BinCapacities = { 100, 100, 100, 100, 100 }; int NumBins = BinCapacities.Length; int[] allBins = Enumerable.Range(0, NumBins).ToArray(); // Create the linear solver with the SCIP backend. Solver solver = Solver.CreateSolver("SCIP"); if (solver is null) { return; } // Variables. Variable[,] x = new Variable[NumItems, NumBins]; foreach (int i in allItems) { foreach (int b in allBins) { x[i, b] = solver.MakeBoolVar($"x_{i}_{b}"); } } // Constraints. // Each item is assigned to at most one bin. foreach (int i in allItems) { Constraint constraint = solver.MakeConstraint(0, 1, ""); foreach (int b in allBins) { constraint.SetCoefficient(x[i, b], 1); } } // The amount packed in each bin cannot exceed its capacity. foreach (int b in allBins) { Constraint constraint = solver.MakeConstraint(0, BinCapacities[b], ""); foreach (int i in allItems) { constraint.SetCoefficient(x[i, b], Weights[i]); } } // Objective. Objective objective = solver.Objective(); foreach (int i in allItems) { foreach (int b in allBins) { objective.SetCoefficient(x[i, b], Values[i]); } } objective.SetMaximization(); Solver.ResultStatus resultStatus = solver.Solve(); // Check that the problem has an optimal solution. if (resultStatus == Solver.ResultStatus.OPTIMAL) { Console.WriteLine($"Total packed value: {solver.Objective().Value()}"); double TotalWeight = 0.0; foreach (int b in allBins) { double BinWeight = 0.0; double BinValue = 0.0; Console.WriteLine("Bin " + b); foreach (int i in allItems) { if (x[i, b].SolutionValue() == 1) { Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}"); BinWeight += Weights[i]; BinValue += Values[i]; } } Console.WriteLine("Packed bin weight: " + BinWeight); Console.WriteLine("Packed bin value: " + BinValue); TotalWeight += BinWeight; } Console.WriteLine("Total packed weight: " + TotalWeight); } else { Console.WriteLine("The problem does not have an optimal solution!"); } } }
CP SAT çözümü
Aşağıdaki bölümlerde, CP-SAT çözücüyü kullanarak sorunun nasıl çözüleceği açıklanmaktadır.
Kitaplıkları içe aktarma
Aşağıdaki kodda gerekli kitaplıkları içe aktarır.
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"); } }
Modeli açıklama
Aşağıdaki kod CP-SAT modelini tanımlar.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Verileri oluşturma
Aşağıdaki kod, sorunla ilgili verileri ayarlar.
Python
data = {} data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36] data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25] assert len(data["weights"]) == len(data["values"]) num_items = len(data["weights"]) all_items = range(num_items) data["bin_capacities"] = [100, 100, 100, 100, 100] num_bins = len(data["bin_capacities"]) all_bins = range(num_bins)
C++
const std::vector<int> weights = { {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}}; const std::vector<int> values = { {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}}; const int num_items = static_cast<int>(weights.size()); std::vector<int> all_items(num_items); std::iota(all_items.begin(), all_items.end(), 0); const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}}; const int num_bins = static_cast<int>(bin_capacities.size()); std::vector<int> all_bins(num_bins); std::iota(all_bins.begin(), all_bins.end(), 0);
Java
final int[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
final int[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
final int numItems = weights.length;
final int[] allItems = IntStream.range(0, numItems).toArray();
final int[] binCapacities = {100, 100, 100, 100, 100};
final int numBins = binCapacities.length;
final int[] allBins = IntStream.range(0, numBins).toArray();C#
int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();
int[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();costs dizisi, maliyet tablosuna karşılık gelir
nasıl belirleyebileceğiniz aşağıda gösterilmiştir.
Değişkenleri oluşturma
Aşağıdaki kod, problem için ikili tam sayı değişkenleri oluşturur.
Python
# x[i, b] = 1 if item i is packed in bin b. x = {} for i in all_items: for b in all_bins: x[i, b] = model.new_bool_var(f"x_{i}_{b}")
C++
// x[i, b] = 1 if item i is packed in bin b. std::map<std::tuple<int, int>, BoolVar> x; for (int i : all_items) { for (int b : all_bins) { auto key = std::make_tuple(i, b); x[key] = cp_model.NewBoolVar().WithName(absl::StrFormat("x_%d_%d", i, b)); } }
Java
Literal[][] x = new Literal[numItems][numBins]; for (int i : allItems) { for (int b : allBins) { x[i][b] = model.newBoolVar("x_" + i + "_" + b); } }
C#
ILiteral[,] x = new ILiteral[NumItems, NumBins];
foreach (int i in allItems)
{
foreach (int b in allBins)
{
x[i, b] = model.NewBoolVar($"x_{i}_{b}");
}
}Kısıtlamaları oluşturma
Aşağıdaki kod, sorun için kısıtlamalar oluşturur.
Python
# Each item is assigned to at most one bin. for i in all_items: model.add_at_most_one(x[i, b] for b in all_bins) # The amount packed in each bin cannot exceed its capacity. for b in all_bins: model.add( sum(x[i, b] * data["weights"][i] for i in all_items) <= data["bin_capacities"][b] )
C++
// Each item is assigned to at most one bin. for (int i : all_items) { std::vector<BoolVar> copies; for (int b : all_bins) { copies.push_back(x[std::make_tuple(i, b)]); } cp_model.AddAtMostOne(copies); } // The amount packed in each bin cannot exceed its capacity. for (int b : all_bins) { LinearExpr bin_weight; for (int i : all_items) { bin_weight += x[std::make_tuple(i, b)] * weights[i]; } cp_model.AddLessOrEqual(bin_weight, bin_capacities[b]); }
Java
// Each item is assigned to at most one bin. for (int i : allItems) { List<Literal> bins = new ArrayList<>(); for (int b : allBins) { bins.add(x[i][b]); } model.addAtMostOne(bins); } // The amount packed in each bin cannot exceed its capacity. for (int b : allBins) { LinearExprBuilder load = LinearExpr.newBuilder(); for (int i : allItems) { load.addTerm(x[i][b], weights[i]); } model.addLessOrEqual(load, binCapacities[b]); }
C#
// Each item is assigned to at most one bin. foreach (int i in allItems) { List<ILiteral> literals = new List<ILiteral>(); foreach (int b in allBins) { literals.Add(x[i, b]); } model.AddAtMostOne(literals); } // The amount packed in each bin cannot exceed its capacity. foreach (int b in allBins) { List<ILiteral> items = new List<ILiteral>(); foreach (int i in allItems) { items.Add(x[i, b]); } model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]); }
Hedef işlevini oluşturma
Aşağıdaki kod, problem için hedef işlevini oluşturur.
Python
# maximize total value of packed items. objective = [] for i in all_items: for b in all_bins: objective.append(cp_model.LinearExpr.term(x[i, b], data["values"][i])) model.maximize(cp_model.LinearExpr.sum(objective))
C++
// Maximize total value of packed items. LinearExpr objective; for (int i : all_items) { for (int b : all_bins) { objective += x[std::make_tuple(i, b)] * values[i]; } } cp_model.Maximize(objective);
Java
// Maximize total value of packed items. LinearExprBuilder obj = LinearExpr.newBuilder(); for (int i : allItems) { for (int b : allBins) { obj.addTerm(x[i][b], values[i]); } } model.maximize(obj);
C#
LinearExprBuilder obj = LinearExpr.NewBuilder(); foreach (int i in allItems) { foreach (int b in allBins) { obj.AddTerm(x[i, b], Values[i]); } } model.Maximize(obj);
Hedef fonksiyonun değeri, bu fonksiyonun atandığı tüm değişkenlere göre çözücü tarafından 1 değeri.
Çözücüyü çağır
Aşağıdaki kod çözücüyü çağırır.
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);
Çözümü yazdırın
Aşağıdaki kod sorunun çözümünü yazdırır.
Python
if status == cp_model.OPTIMAL: print(f"Total packed value: {solver.objective_value}") total_weight = 0 for b in all_bins: print(f"Bin {b}") bin_weight = 0 bin_value = 0 for i in all_items: if solver.value(x[i, b]) > 0: print( f'Item:{i} weight:{data["weights"][i]} value:{data["values"][i]}' ) bin_weight += data["weights"][i] bin_value += data["values"][i] print(f"Packed bin weight: {bin_weight}") print(f"Packed bin value: {bin_value}\n") total_weight += bin_weight print(f"Total packed weight: {total_weight}") else: print("The problem does not have an optimal solution.")
C++
if (response.status() == CpSolverStatus::OPTIMAL || response.status() == CpSolverStatus::FEASIBLE) { LOG(INFO) << "Total packed value: " << response.objective_value(); double total_weight = 0.0; for (int b : all_bins) { LOG(INFO) << "Bin " << b; double bin_weight = 0.0; double bin_value = 0.0; for (int i : all_items) { auto key = std::make_tuple(i, b); if (SolutionIntegerValue(response, x[key]) > 0) { LOG(INFO) << "Item " << i << " weight: " << weights[i] << " value: " << values[i]; bin_weight += weights[i]; bin_value += values[i]; } } LOG(INFO) << "Packed bin weight: " << bin_weight; LOG(INFO) << "Packed bin value: " << bin_value; total_weight += bin_weight; } LOG(INFO) << "Total packed weight: " << total_weight; } else { LOG(INFO) << "The problem does not have an optimal solution."; }
Java
// Check that the problem has an optimal solution. if (status == CpSolverStatus.OPTIMAL) { System.out.println("Total packed value: " + solver.objectiveValue()); long totalWeight = 0; for (int b : allBins) { long binWeight = 0; long binValue = 0; System.out.println("Bin " + b); for (int i : allItems) { if (solver.booleanValue(x[i][b])) { System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]); binWeight += weights[i]; binValue += values[i]; } } System.out.println("Packed bin weight: " + binWeight); System.out.println("Packed bin value: " + binValue); totalWeight += binWeight; } System.out.println("Total packed weight: " + totalWeight); } else { System.err.println("The problem does not have an optimal solution."); }
C#
// Check that the problem has a feasible solution. if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine($"Total packed value: {solver.ObjectiveValue}"); double TotalWeight = 0.0; foreach (int b in allBins) { double BinWeight = 0.0; double BinValue = 0.0; Console.WriteLine($"Bin {b}"); foreach (int i in allItems) { if (solver.BooleanValue(x[i, b])) { Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}"); BinWeight += Weights[i]; BinValue += Values[i]; } } Console.WriteLine("Packed bin weight: " + BinWeight); Console.WriteLine("Packed bin value: " + BinValue); TotalWeight += BinWeight; } Console.WriteLine("Total packed weight: " + TotalWeight); } else { Console.WriteLine("No solution found."); }
İşte programın çıktısı.
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
Programları tamamlama
CP-SAT çözümüne yönelik programların tamamını aşağıda bulabilirsiniz.
Python
"""Solves a multiple knapsack problem using the CP-SAT solver.""" from ortools.sat.python import cp_model def main() -> None: data = {} data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36] data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25] assert len(data["weights"]) == len(data["values"]) num_items = len(data["weights"]) all_items = range(num_items) data["bin_capacities"] = [100, 100, 100, 100, 100] num_bins = len(data["bin_capacities"]) all_bins = range(num_bins) model = cp_model.CpModel() # Variables. # x[i, b] = 1 if item i is packed in bin b. x = {} for i in all_items: for b in all_bins: x[i, b] = model.new_bool_var(f"x_{i}_{b}") # Constraints. # Each item is assigned to at most one bin. for i in all_items: model.add_at_most_one(x[i, b] for b in all_bins) # The amount packed in each bin cannot exceed its capacity. for b in all_bins: model.add( sum(x[i, b] * data["weights"][i] for i in all_items) <= data["bin_capacities"][b] ) # Objective. # maximize total value of packed items. objective = [] for i in all_items: for b in all_bins: objective.append(cp_model.LinearExpr.term(x[i, b], data["values"][i])) model.maximize(cp_model.LinearExpr.sum(objective)) solver = cp_model.CpSolver() status = solver.solve(model) if status == cp_model.OPTIMAL: print(f"Total packed value: {solver.objective_value}") total_weight = 0 for b in all_bins: print(f"Bin {b}") bin_weight = 0 bin_value = 0 for i in all_items: if solver.value(x[i, b]) > 0: print( f'Item:{i} weight:{data["weights"][i]} value:{data["values"][i]}' ) bin_weight += data["weights"][i] bin_value += data["values"][i] print(f"Packed bin weight: {bin_weight}") print(f"Packed bin value: {bin_value}\n") total_weight += bin_weight print(f"Total packed weight: {total_weight}") else: print("The problem does not have an optimal solution.") if __name__ == "__main__": main()
C++
// Solves a multiple knapsack problem using the CP-SAT solver. #include <stdlib.h> #include <map> #include <numeric> #include <tuple> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" namespace operations_research { namespace sat { void MultipleKnapsackSat() { const std::vector<int> weights = { {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}}; const std::vector<int> values = { {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}}; const int num_items = static_cast<int>(weights.size()); std::vector<int> all_items(num_items); std::iota(all_items.begin(), all_items.end(), 0); const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}}; const int num_bins = static_cast<int>(bin_capacities.size()); std::vector<int> all_bins(num_bins); std::iota(all_bins.begin(), all_bins.end(), 0); CpModelBuilder cp_model; // Variables. // x[i, b] = 1 if item i is packed in bin b. std::map<std::tuple<int, int>, BoolVar> x; for (int i : all_items) { for (int b : all_bins) { auto key = std::make_tuple(i, b); x[key] = cp_model.NewBoolVar().WithName(absl::StrFormat("x_%d_%d", i, b)); } } // Constraints. // Each item is assigned to at most one bin. for (int i : all_items) { std::vector<BoolVar> copies; for (int b : all_bins) { copies.push_back(x[std::make_tuple(i, b)]); } cp_model.AddAtMostOne(copies); } // The amount packed in each bin cannot exceed its capacity. for (int b : all_bins) { LinearExpr bin_weight; for (int i : all_items) { bin_weight += x[std::make_tuple(i, b)] * weights[i]; } cp_model.AddLessOrEqual(bin_weight, bin_capacities[b]); } // Objective. // Maximize total value of packed items. LinearExpr objective; for (int i : all_items) { for (int b : all_bins) { objective += x[std::make_tuple(i, b)] * values[i]; } } cp_model.Maximize(objective); const CpSolverResponse response = Solve(cp_model.Build()); if (response.status() == CpSolverStatus::OPTIMAL || response.status() == CpSolverStatus::FEASIBLE) { LOG(INFO) << "Total packed value: " << response.objective_value(); double total_weight = 0.0; for (int b : all_bins) { LOG(INFO) << "Bin " << b; double bin_weight = 0.0; double bin_value = 0.0; for (int i : all_items) { auto key = std::make_tuple(i, b); if (SolutionIntegerValue(response, x[key]) > 0) { LOG(INFO) << "Item " << i << " weight: " << weights[i] << " value: " << values[i]; bin_weight += weights[i]; bin_value += values[i]; } } LOG(INFO) << "Packed bin weight: " << bin_weight; LOG(INFO) << "Packed bin value: " << bin_value; total_weight += bin_weight; } LOG(INFO) << "Total packed weight: " << total_weight; } else { LOG(INFO) << "The problem does not have an optimal solution."; } // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << CpSolverResponseStats(response); } } // namespace sat } // namespace operations_research int main() { operations_research::sat::MultipleKnapsackSat(); return EXIT_SUCCESS; }
Java
// Solves a multiple knapsack problem using the CP-SAT solver. package com.google.ortools.sat.samples; import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream; /** Sample showing how to solve a multiple knapsack problem. */ public class MultipleKnapsackSat { public static void main(String[] args) { Loader.loadNativeLibraries(); // Instantiate the data problem. final int[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36}; final int[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25}; final int numItems = weights.length; final int[] allItems = IntStream.range(0, numItems).toArray(); final int[] binCapacities = {100, 100, 100, 100, 100}; final int numBins = binCapacities.length; final int[] allBins = IntStream.range(0, numBins).toArray(); CpModel model = new CpModel(); // Variables. Literal[][] x = new Literal[numItems][numBins]; for (int i : allItems) { for (int b : allBins) { x[i][b] = model.newBoolVar("x_" + i + "_" + b); } } // Constraints. // Each item is assigned to at most one bin. for (int i : allItems) { List<Literal> bins = new ArrayList<>(); for (int b : allBins) { bins.add(x[i][b]); } model.addAtMostOne(bins); } // The amount packed in each bin cannot exceed its capacity. for (int b : allBins) { LinearExprBuilder load = LinearExpr.newBuilder(); for (int i : allItems) { load.addTerm(x[i][b], weights[i]); } model.addLessOrEqual(load, binCapacities[b]); } // Objective. // Maximize total value of packed items. LinearExprBuilder obj = LinearExpr.newBuilder(); for (int i : allItems) { for (int b : allBins) { obj.addTerm(x[i][b], values[i]); } } model.maximize(obj); CpSolver solver = new CpSolver(); final CpSolverStatus status = solver.solve(model); // Check that the problem has an optimal solution. if (status == CpSolverStatus.OPTIMAL) { System.out.println("Total packed value: " + solver.objectiveValue()); long totalWeight = 0; for (int b : allBins) { long binWeight = 0; long binValue = 0; System.out.println("Bin " + b); for (int i : allItems) { if (solver.booleanValue(x[i][b])) { System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]); binWeight += weights[i]; binValue += values[i]; } } System.out.println("Packed bin weight: " + binWeight); System.out.println("Packed bin value: " + binValue); totalWeight += binWeight; } System.out.println("Total packed weight: " + totalWeight); } else { System.err.println("The problem does not have an optimal solution."); } } private MultipleKnapsackSat() {} }
C#
// Solves a multiple knapsack problem using the CP-SAT solver. using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat; public class MultipleKnapsackSat { public static void Main(String[] args) { // Instantiate the data problem. int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 }; int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 }; int NumItems = Weights.Length; int[] allItems = Enumerable.Range(0, NumItems).ToArray(); int[] BinCapacities = { 100, 100, 100, 100, 100 }; int NumBins = BinCapacities.Length; int[] allBins = Enumerable.Range(0, NumBins).ToArray(); // Model. CpModel model = new CpModel(); // Variables. ILiteral[,] x = new ILiteral[NumItems, NumBins]; foreach (int i in allItems) { foreach (int b in allBins) { x[i, b] = model.NewBoolVar($"x_{i}_{b}"); } } // Constraints. // Each item is assigned to at most one bin. foreach (int i in allItems) { List<ILiteral> literals = new List<ILiteral>(); foreach (int b in allBins) { literals.Add(x[i, b]); } model.AddAtMostOne(literals); } // The amount packed in each bin cannot exceed its capacity. foreach (int b in allBins) { List<ILiteral> items = new List<ILiteral>(); foreach (int i in allItems) { items.Add(x[i, b]); } model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]); } // Objective. LinearExprBuilder obj = LinearExpr.NewBuilder(); foreach (int i in allItems) { foreach (int b in allBins) { obj.AddTerm(x[i, b], Values[i]); } } model.Maximize(obj); // Solve CpSolver solver = new CpSolver(); CpSolverStatus status = solver.Solve(model); // Print solution. // Check that the problem has a feasible solution. if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine($"Total packed value: {solver.ObjectiveValue}"); double TotalWeight = 0.0; foreach (int b in allBins) { double BinWeight = 0.0; double BinValue = 0.0; Console.WriteLine($"Bin {b}"); foreach (int i in allItems) { if (solver.BooleanValue(x[i, b])) { Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}"); BinWeight += Weights[i]; BinValue += Values[i]; } } Console.WriteLine("Packed bin weight: " + BinWeight); Console.WriteLine("Packed bin value: " + BinValue); TotalWeight += BinWeight; } Console.WriteLine("Total packed weight: " + TotalWeight); } else { Console.WriteLine("No solution found."); } Console.WriteLine("Statistics"); Console.WriteLine($" conflicts: {solver.NumConflicts()}"); Console.WriteLine($" branches : {solver.NumBranches()}"); Console.WriteLine($" wall time: {solver.WallTime()}s"); } }