يعرض هذا القسم كيفية حل مشكلة حقائب الظهر المتعددة للحقائب باستخدام كل من أداة حل MIP وأداة تحليل CP-SAT. في هذه الحالة، من الشائع الإشارة إلى الحاويات على أنها حاويات، بدلاً من حقائب الظهر.
يوضح المثال التالي كيفية إيجاد الطريقة المثلى لتغليف العناصر في خمس سلات.
مثال
كما في المثال السابق، تبدأ بمجموعة من العناصر بأوزان وقيم مختلفة. وتكمن المشكلة في تجميع مجموعة فرعية من العناصر في خمس سلات، كل منها يبلغ الحد الأقصى للسعة 100، بحيث يصبح إجمالي القيمة المجمّعة حدًا أقصى.
تقدم الأقسام التالية أقسامًا من البرامج التي تحل هذه المشكلة. للاطلاع على البرامج الكاملة، راجع إكمال البرامج.
حل MIP
تصف الأقسام التالية كيفية حل المشكلة باستخدام برنامج تضمين MPSolver.
استيراد المكتبات
تعمل الشفرة التالية على استيراد المكتبات المطلوبة.
لغة 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;
إنشاء البيانات
تعمل الشفرة التالية على إنشاء بيانات المشكلة.
لغة 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();
وتشمل البيانات ما يلي:
weights: متّجه يحتوي على قيم ترجيح العناصر.values: متّجه يشتمل على قيم العناصر.capacities: متّجه يحتوي على سعات الصناديق.
في هذا المثال، جميع الحاويات لها السعة نفسها، ولكن لا يلزم أن يكون ذلك صحيحًا بشكل عام.
الإعلان عن برنامج تعيين MIP
تعلن الشفرة التالية عن برنامج تعيين 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;
}
إنشاء المتغيرات
ينشئ الرمز التالي المتغيّرات للمشكلة.
لغة 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}");
}
}
كل x[(i, j)] عبارة عن متغيّر 0-1، حيث يكون i عنصرًا وj عبارة عن سلة. في
الحلّ، ستكون قيمة x[(i, j)] 1 في حال وضع العنصر i في الحاوية j، وعلى 0
في الحالات الأخرى.
تحديد القيود
تحدد الشفرة التالية القيود المفروضة على المشكلة:
لغة 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]);
}
}
فيما يلي القيود:
- يمكن وضع كل عنصر في حاوية واحدة على الأكثر. ويتم ضبط هذا القيد من خلال طلب مجموع
x[i, j]على جميع الصناديقjبأن يكون أقل من أو يساوي 1. - لا يمكن أن يتجاوز إجمالي الوزن المغلّف في كل حاوية سعته. ويتم ضبط هذه القيود من خلال طلب أن يكون مجموع أوزان العناصر الموضوعة في الحاوية
jأقل من أو يساوي قيمة الحاوية.
تحديد الهدف
تحدد الشفرة التالية الوظيفة الموضوعية للمشكلة، وهي القيمة الإجمالية للسلع المعبأة.
لغة 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 إلى الهدف إذا تم وضع العنصر في الحاوية j. وإذا لم يتم وضع i في أي سلة، لا تساهم قيمتها في الهدف.
استدعاء أداة الحل
تستدعي الشفرة التالية أداة الحل.
لغة 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();
طباعة الحل
تطبع الشفرة التالية الحل للمشكلة.
لغة 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!");
}
بالنسبة إلى كل حاوية، تعرض الشفرة العناصر الموضوعة في الحاوية، فضلاً عن إجمالي قيمة ووزن الصندوق. يعرض الرمز أيضًا القيمة الإجمالية والوزن الإجمالي للعناصر المعبأة.
عند تشغيل البرنامج، يتم عرض الناتج التالي.
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
إكمال البرامج
في ما يلي البرامج الكاملة لحقائب الظهر المتعددة.
لغة 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!");
}
}
}
حل CP SAT
تصف الأقسام التالية كيفية حل المشكلة باستخدام برنامج تعيين CP-SAT.
استيراد المكتبات
تعمل الشفرة التالية على استيراد المكتبات المطلوبة.
لغة 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");
}
}
توضيح النموذج
توضح الشفرة التالية نموذج CP-SAT.
لغة Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
لغة Java
CpModel model = new CpModel();
#C
CpModel model = new CpModel();
إنشاء البيانات
تعمل الشفرة التالية على إعداد بيانات المشكلة.
لغة 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();
يتطابق المصفوفة costs مع جدول التكاليف
لتعيين العاملين للمهام المبيّن أعلاه.
إنشاء المتغيرات
ينشئ الرمز التالي متغيرات عدد صحيح ثنائي للمشكلة.
لغة 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}");
}
}
إنشاء القيود
ينشئ الرمز التالي قيودًا للمشكلة.
لغة 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]);
}
إنشاء الدالة الهدف
تعمل الشفرة التالية على إنشاء الدالة الموضوعية للمشكلة.
لغة 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);
قيمة الدالة الهدف هي إجمالي التكلفة على جميع المتغيرات التي خصصت لها أداة الحل القيمة 1.
استدعاء أداة الحل
تستدعي الشفرة التالية أداة الحل.
لغة 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);
طباعة الحل
تطبع الشفرة التالية الحل للمشكلة.
لغة 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.");
}
إليك مخرجات البرنامج.
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
إكمال البرامج
في ما يلي البرامج الكاملة لحل 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");
}
}