Giống như vấn đề nhiều knapsack, vấn đề đóng gói thùng rác cũng liên quan đến việc đóng gói các mục vào thùng rác. Tuy nhiên, vấn đề đóng gói thùng rác có một mục tiêu khác: tìm các thùng rác ít nhất sẽ chứa tất cả các mục.
Sau đây là tóm tắt sự khác biệt giữa hai vấn đề:
Bài toán về nhiều túi rác: Đóng một nhóm nhỏ các mục vào một số lượng cố định các thùng, với dung lượng khác nhau, để tổng giá trị của các mục đã đóng gói là tối đa.
Vấn đề về việc đóng gói thùng: Vì có nhiều thùng có dung lượng chung như cần thiết, hãy tìm thùng rác chứa được tất cả các vật dụng ít nhất. Trong bài toán này, các mục không được gán giá trị, vì mục tiêu không liên quan đến giá trị.
Ví dụ tiếp theo cho biết cách giải quyết một vấn đề về đóng gói thùng rác.
Ví dụ:
Ở ví dụ này, các mục có trọng lượng khác nhau cần được đóng gói vào một tập hợp các thùng có sức chứa chung. Giả sử có đủ thùng để chứa tất cả các mục, vấn đề là tìm ít tệp nhất là đủ.
Các phần sau đây trình bày các chương trình giải quyết vấn đề này. Để biết toàn bộ chương trình, hãy xem phần Hoàn thành chương trình.
Ví dụ này sử dụng trình bao bọc MPSolver.
Nhập thư viện
Mã bên dưới nhập các thư viện bắt buộc.
Python
from ortools.linear_solver import pywraplp
C++
#include <iostream> #include <memory> #include <numeric> #include <ostream> #include <vector> #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;
C#
using System; using Google.OrTools.LinearSolver;
Tạo dữ liệu
Mã dưới đây sẽ tạo dữ liệu cho ví dụ này.
Python
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
data["weights"] = weights
data["items"] = list(range(len(weights)))
data["bins"] = data["items"]
data["bin_capacity"] = 100
return data
C++
struct DataModel {
const std::vector<double> weights = {48, 30, 19, 36, 36, 27,
42, 42, 36, 24, 30};
const int num_items = weights.size();
const int num_bins = weights.size();
const int bin_capacity = 100;
};
Java
static class DataModel {
public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
public final int numItems = weights.length;
public final int numBins = weights.length;
public final int binCapacity = 100;
}
C#
class DataModel
{
public static double[] Weights = { 48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30 };
public int NumItems = Weights.Length;
public int NumBins = Weights.Length;
public double BinCapacity = 100.0;
}
Các dữ liệu này bao gồm:
weights: Một vectơ chứa trọng số của các mục.bin_capacity: Một số cho biết dung tích của các thùng.
Không có giá trị nào được chỉ định cho các mục vì mục tiêu giảm thiểu số lượng thùng rác không liên quan đến giá trị.
Lưu ý rằng num_bins được đặt thành số lượng mục. Lý do là nếu bài toán có một nghiệm, thì trọng số của mỗi mục phải nhỏ hơn hoặc bằng dung lượng thùng rác. Trong trường hợp đó, số thùng rác tối đa bạn có thể cần là số mục, vì bạn luôn có thể đặt mỗi mục vào một thùng riêng.
Khai báo trình giải
Mã sau đây khai báo trình giải toán.
Python
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
C++
// Create the mip solver with the SCIP backend.
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;
}
Tạo các biến
Mã sau đây tạo các biến cho chương trình.
Python
# Variables
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data["items"]:
for j in data["bins"]:
x[(i, j)] = solver.IntVar(0, 1, "x_%i_%i" % (i, j))
# y[j] = 1 if bin j is used.
y = {}
for j in data["bins"]:
y[j] = solver.IntVar(0, 1, "y[%i]" % j)
C++
std::vector<std::vector<const MPVariable*>> x(
data.num_items, std::vector<const MPVariable*>(data.num_bins));
for (int i = 0; i < data.num_items; ++i) {
for (int j = 0; j < data.num_bins; ++j) {
x[i][j] = solver->MakeIntVar(0.0, 1.0, "");
}
}
// y[j] = 1 if bin j is used.
std::vector<const MPVariable*> y(data.num_bins);
for (int j = 0; j < data.num_bins; ++j) {
y[j] = solver->MakeIntVar(0.0, 1.0, "");
}
Java
MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
for (int j = 0; j < data.numBins; ++j) {
x[i][j] = solver.makeIntVar(0, 1, "");
}
}
MPVariable[] y = new MPVariable[data.numBins];
for (int j = 0; j < data.numBins; ++j) {
y[j] = solver.makeIntVar(0, 1, "");
}
C#
Variable[,] x = new Variable[data.NumItems, data.NumBins];
for (int i = 0; i < data.NumItems; i++)
{
for (int j = 0; j < data.NumBins; j++)
{
x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
}
}
Variable[] y = new Variable[data.NumBins];
for (int j = 0; j < data.NumBins; j++)
{
y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
}
Như trong ví dụ về nhiều knapsack, bạn xác định một mảng biến x[(i,
j)] có giá trị là 1 nếu mục i được đặt trong thùng j và ngược lại.
Đối với việc đóng gói thùng rác, bạn cũng xác định một loạt các biến y[j] có giá trị là 1 nếu sử dụng thùng rác j, tức là nếu có bất kỳ mục nào được đóng gói trong đó, và 0 nếu không. Tổng của y[j] sẽ là số thùng được sử dụng.
Xác định các điều kiện ràng buộc
Mã sau đây xác định các điều kiện ràng buộc cho vấn đề:
Python
# Constraints
# Each item must be in exactly one bin.
for i in data["items"]:
solver.Add(sum(x[i, j] for j in data["bins"]) == 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data["bins"]:
solver.Add(
sum(x[(i, j)] * data["weights"][i] for i in data["items"])
<= y[j] * data["bin_capacity"]
)
C++
// Create the constraints.
// Each item is in exactly one bin.
for (int i = 0; i < data.num_items; ++i) {
LinearExpr sum;
for (int j = 0; j < data.num_bins; ++j) {
sum += x[i][j];
}
solver->MakeRowConstraint(sum == 1.0);
}
// For each bin that is used, the total packed weight can be at most
// the bin capacity.
for (int j = 0; j < data.num_bins; ++j) {
LinearExpr weight;
for (int i = 0; i < data.num_items; ++i) {
weight += data.weights[i] * LinearExpr(x[i][j]);
}
solver->MakeRowConstraint(weight <= LinearExpr(y[j]) * data.bin_capacity);
}
Java
double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int i = 0; i < data.numItems; ++i) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int j = 0; j < data.numBins; ++j) {
constraint.setCoefficient(x[i][j], 1);
}
}
// The bin capacity contraint for bin j is
// sum_i w_i x_ij <= C*y_j
// To define this constraint, first subtract the left side from the right to get
// 0 <= C*y_j - sum_i w_i x_ij
//
// Note: Since sum_i w_i x_ij is positive (and y_j is 0 or 1), the right side must
// be less than or equal to C. But it's not necessary to add this constraint
// because it is forced by the other constraints.
for (int j = 0; j < data.numBins; ++j) {
MPConstraint constraint = solver.makeConstraint(0, infinity, "");
constraint.setCoefficient(y[j], data.binCapacity);
for (int i = 0; i < data.numItems; ++i) {
constraint.setCoefficient(x[i][j], -data.weights[i]);
}
}
C#
for (int i = 0; i < data.NumItems; ++i)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
for (int j = 0; j < data.NumBins; ++j)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
for (int j = 0; j < data.NumBins; ++j)
{
Constraint constraint = solver.MakeConstraint(0, Double.PositiveInfinity, "");
constraint.SetCoefficient(y[j], data.BinCapacity);
for (int i = 0; i < data.NumItems; ++i)
{
constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
}
}
Các ràng buộc bao gồm:
- Mỗi mục phải được đặt vào đúng một thùng. Quy tắc ràng buộc này được đặt ra bằng cách yêu cầu tổng của
x[i][j]trên tất cả các thùngjbằng 1. Xin lưu ý rằng vấn đề này khác với nhiều vấn đề về knapsack, trong đó tổng chỉ cần nhỏ hơn hoặc bằng 1, vì không phải tất cả các mục đều phải được đóng gói. Tổng trọng lượng đóng gói trong mỗi thùng không được vượt quá sức chứa của thùng. Đây là điều kiện ràng buộc tương tự như trong bài toán về knapsack, nhưng trong trường hợp này, bạn nhân dung lượng thùng rác ở bên phải với bất đẳng thức
y[j].Tại sao nhân với
y[j]? Bởi vì nó buộcy[j]bằng 1 nếu bất kỳ mục nào được đóng gói trong thùngj. Lý do là nếuy[j]bằng 0, cạnh phải của bất đẳng thức sẽ bằng 0, trong khi trọng số thùng ở phía bên trái sẽ lớn hơn 0, vi phạm điều kiện ràng buộc. Thao tác này sẽ kết nối các biếny[j]với mục tiêu của bài toán. Hiện tại, trình giải toán sẽ cố gắng giảm thiểu số lượng thùng rác choy[j]là 1.
Xác định mục tiêu
Mã sau đây xác định hàm mục tiêu cho vấn đề.
Python
# Objective: minimize the number of bins used. solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))
C++
// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
LinearExpr num_bins_used;
for (int j = 0; j < data.num_bins; ++j) {
num_bins_used += y[j];
}
objective->MinimizeLinearExpr(num_bins_used);
Java
MPObjective objective = solver.objective();
for (int j = 0; j < data.numBins; ++j) {
objective.setCoefficient(y[j], 1);
}
objective.setMinimization();
C#
Objective objective = solver.Objective();
for (int j = 0; j < data.NumBins; ++j)
{
objective.SetCoefficient(y[j], 1);
}
objective.SetMinimization();
Vì y[j] là 1 nếu sử dụng bin j và nếu không thì 0, tổng của y[j] là số lượng thùng được sử dụng. Mục tiêu là giảm thiểu tổng số.
Gọi trình giải toán và in giải pháp
Mã sau đây gọi trình giải toán và in giải pháp.
Python
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_bins = 0
for j in data["bins"]:
if y[j].solution_value() == 1:
bin_items = []
bin_weight = 0
for i in data["items"]:
if x[i, j].solution_value() > 0:
bin_items.append(i)
bin_weight += data["weights"][i]
if bin_items:
num_bins += 1
print("Bin number", j)
print(" Items packed:", bin_items)
print(" Total weight:", bin_weight)
print()
print()
print("Number of bins used:", num_bins)
print("Time = ", solver.WallTime(), " milliseconds")
else:
print("The problem does not have an optimal solution.")
C++
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
std::cerr << "The problem does not have an optimal solution!";
return;
}
std::cout << "Number of bins used: " << objective->Value() << std::endl
<< std::endl;
double total_weight = 0;
for (int j = 0; j < data.num_bins; ++j) {
if (y[j]->solution_value() == 1) {
std::cout << "Bin " << j << std::endl << std::endl;
double bin_weight = 0;
for (int i = 0; i < data.num_items; ++i) {
if (x[i][j]->solution_value() == 1) {
std::cout << "Item " << i << " - Weight: " << data.weights[i]
<< std::endl;
bin_weight += data.weights[i];
}
}
std::cout << "Packed bin weight: " << bin_weight << std::endl
<< std::endl;
total_weight += bin_weight;
}
}
std::cout << "Total packed weight: " << total_weight << std::endl;
Java
final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Number of bins used: " + objective.value());
double totalWeight = 0;
for (int j = 0; j < data.numBins; ++j) {
if (y[j].solutionValue() == 1) {
System.out.println("\nBin " + j + "\n");
double binWeight = 0;
for (int i = 0; i < data.numItems; ++i) {
if (x[i][j].solutionValue() == 1) {
System.out.println("Item " + i + " - weight: " + data.weights[i]);
binWeight += data.weights[i];
}
}
System.out.println("Packed bin weight: " + binWeight);
totalWeight += binWeight;
}
}
System.out.println("\nTotal packed weight: " + totalWeight);
} else {
System.err.println("The problem does not have an optimal solution.");
}
C#
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine("The problem does not have an optimal solution!");
return;
}
Console.WriteLine($"Number of bins used: {solver.Objective().Value()}");
double TotalWeight = 0.0;
for (int j = 0; j < data.NumBins; ++j)
{
double BinWeight = 0.0;
if (y[j].SolutionValue() == 1)
{
Console.WriteLine($"Bin {j}");
for (int i = 0; i < data.NumItems; ++i)
{
if (x[i, j].SolutionValue() == 1)
{
Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]}");
BinWeight += DataModel.Weights[i];
}
}
Console.WriteLine($"Packed bin weight: {BinWeight}");
TotalWeight += BinWeight;
}
}
Console.WriteLine($"Total packed weight: {TotalWeight}");
Giải pháp này cho thấy số lượng thùng rác tối thiểu cần có để đóng gói tất cả các mặt hàng. Đối với mỗi thùng được sử dụng, giải pháp sẽ thể hiện các mục trong gói và tổng trọng lượng thùng.
Kết quả của chương trình
Khi chạy chương trình, bạn sẽ thấy kết quả sau.
Bin number 0 Items packed: [1, 5, 10] Total weight: 87 Bin number 1 Items packed: [0, 6] Total weight: 90 Bin number 2 Items packed: [2, 4, 7] Total weight: 97 Bin number 3 Items packed: [3, 8, 9] Total weight: 96 Number of bins used: 4.0
Hoàn thành chương trình
Dưới đây là chương trình hoàn chỉnh cho vấn đề đóng gói thùng rác.
Python
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
data["weights"] = weights
data["items"] = list(range(len(weights)))
data["bins"] = data["items"]
data["bin_capacity"] = 100
return data
def main():
data = create_data_model()
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
# Variables
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data["items"]:
for j in data["bins"]:
x[(i, j)] = solver.IntVar(0, 1, "x_%i_%i" % (i, j))
# y[j] = 1 if bin j is used.
y = {}
for j in data["bins"]:
y[j] = solver.IntVar(0, 1, "y[%i]" % j)
# Constraints
# Each item must be in exactly one bin.
for i in data["items"]:
solver.Add(sum(x[i, j] for j in data["bins"]) == 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data["bins"]:
solver.Add(
sum(x[(i, j)] * data["weights"][i] for i in data["items"])
<= y[j] * data["bin_capacity"]
)
# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_bins = 0
for j in data["bins"]:
if y[j].solution_value() == 1:
bin_items = []
bin_weight = 0
for i in data["items"]:
if x[i, j].solution_value() > 0:
bin_items.append(i)
bin_weight += data["weights"][i]
if bin_items:
num_bins += 1
print("Bin number", j)
print(" Items packed:", bin_items)
print(" Total weight:", bin_weight)
print()
print()
print("Number of bins used:", num_bins)
print("Time = ", solver.WallTime(), " milliseconds")
else:
print("The problem does not have an optimal solution.")
if __name__ == "__main__":
main()
C++
#include <iostream>
#include <memory>
#include <numeric>
#include <ostream>
#include <vector>
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
struct DataModel {
const std::vector<double> weights = {48, 30, 19, 36, 36, 27,
42, 42, 36, 24, 30};
const int num_items = weights.size();
const int num_bins = weights.size();
const int bin_capacity = 100;
};
void BinPackingMip() {
DataModel data;
// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}
std::vector<std::vector<const MPVariable*>> x(
data.num_items, std::vector<const MPVariable*>(data.num_bins));
for (int i = 0; i < data.num_items; ++i) {
for (int j = 0; j < data.num_bins; ++j) {
x[i][j] = solver->MakeIntVar(0.0, 1.0, "");
}
}
// y[j] = 1 if bin j is used.
std::vector<const MPVariable*> y(data.num_bins);
for (int j = 0; j < data.num_bins; ++j) {
y[j] = solver->MakeIntVar(0.0, 1.0, "");
}
// Create the constraints.
// Each item is in exactly one bin.
for (int i = 0; i < data.num_items; ++i) {
LinearExpr sum;
for (int j = 0; j < data.num_bins; ++j) {
sum += x[i][j];
}
solver->MakeRowConstraint(sum == 1.0);
}
// For each bin that is used, the total packed weight can be at most
// the bin capacity.
for (int j = 0; j < data.num_bins; ++j) {
LinearExpr weight;
for (int i = 0; i < data.num_items; ++i) {
weight += data.weights[i] * LinearExpr(x[i][j]);
}
solver->MakeRowConstraint(weight <= LinearExpr(y[j]) * data.bin_capacity);
}
// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
LinearExpr num_bins_used;
for (int j = 0; j < data.num_bins; ++j) {
num_bins_used += y[j];
}
objective->MinimizeLinearExpr(num_bins_used);
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
std::cerr << "The problem does not have an optimal solution!";
return;
}
std::cout << "Number of bins used: " << objective->Value() << std::endl
<< std::endl;
double total_weight = 0;
for (int j = 0; j < data.num_bins; ++j) {
if (y[j]->solution_value() == 1) {
std::cout << "Bin " << j << std::endl << std::endl;
double bin_weight = 0;
for (int i = 0; i < data.num_items; ++i) {
if (x[i][j]->solution_value() == 1) {
std::cout << "Item " << i << " - Weight: " << data.weights[i]
<< std::endl;
bin_weight += data.weights[i];
}
}
std::cout << "Packed bin weight: " << bin_weight << std::endl
<< std::endl;
total_weight += bin_weight;
}
}
std::cout << "Total packed weight: " << total_weight << std::endl;
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::BinPackingMip();
return EXIT_SUCCESS;
}
Java
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;
/** Bin packing problem. */
public class BinPackingMip {
static class DataModel {
public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
public final int numItems = weights.length;
public final int numBins = weights.length;
public final int binCapacity = 100;
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
final DataModel data = new DataModel();
// 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;
}
MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
for (int j = 0; j < data.numBins; ++j) {
x[i][j] = solver.makeIntVar(0, 1, "");
}
}
MPVariable[] y = new MPVariable[data.numBins];
for (int j = 0; j < data.numBins; ++j) {
y[j] = solver.makeIntVar(0, 1, "");
}
double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int i = 0; i < data.numItems; ++i) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int j = 0; j < data.numBins; ++j) {
constraint.setCoefficient(x[i][j], 1);
}
}
// The bin capacity contraint for bin j is
// sum_i w_i x_ij <= C*y_j
// To define this constraint, first subtract the left side from the right to get
// 0 <= C*y_j - sum_i w_i x_ij
//
// Note: Since sum_i w_i x_ij is positive (and y_j is 0 or 1), the right side must
// be less than or equal to C. But it's not necessary to add this constraint
// because it is forced by the other constraints.
for (int j = 0; j < data.numBins; ++j) {
MPConstraint constraint = solver.makeConstraint(0, infinity, "");
constraint.setCoefficient(y[j], data.binCapacity);
for (int i = 0; i < data.numItems; ++i) {
constraint.setCoefficient(x[i][j], -data.weights[i]);
}
}
MPObjective objective = solver.objective();
for (int j = 0; j < data.numBins; ++j) {
objective.setCoefficient(y[j], 1);
}
objective.setMinimization();
final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Number of bins used: " + objective.value());
double totalWeight = 0;
for (int j = 0; j < data.numBins; ++j) {
if (y[j].solutionValue() == 1) {
System.out.println("\nBin " + j + "\n");
double binWeight = 0;
for (int i = 0; i < data.numItems; ++i) {
if (x[i][j].solutionValue() == 1) {
System.out.println("Item " + i + " - weight: " + data.weights[i]);
binWeight += data.weights[i];
}
}
System.out.println("Packed bin weight: " + binWeight);
totalWeight += binWeight;
}
}
System.out.println("\nTotal packed weight: " + totalWeight);
} else {
System.err.println("The problem does not have an optimal solution.");
}
}
private BinPackingMip() {}
}
C#
using System;
using Google.OrTools.LinearSolver;
public class BinPackingMip
{
class DataModel
{
public static double[] Weights = { 48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30 };
public int NumItems = Weights.Length;
public int NumBins = Weights.Length;
public double BinCapacity = 100.0;
}
public static void Main()
{
DataModel data = new DataModel();
// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}
Variable[,] x = new Variable[data.NumItems, data.NumBins];
for (int i = 0; i < data.NumItems; i++)
{
for (int j = 0; j < data.NumBins; j++)
{
x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
}
}
Variable[] y = new Variable[data.NumBins];
for (int j = 0; j < data.NumBins; j++)
{
y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
}
for (int i = 0; i < data.NumItems; ++i)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
for (int j = 0; j < data.NumBins; ++j)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
for (int j = 0; j < data.NumBins; ++j)
{
Constraint constraint = solver.MakeConstraint(0, Double.PositiveInfinity, "");
constraint.SetCoefficient(y[j], data.BinCapacity);
for (int i = 0; i < data.NumItems; ++i)
{
constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
}
}
Objective objective = solver.Objective();
for (int j = 0; j < data.NumBins; ++j)
{
objective.SetCoefficient(y[j], 1);
}
objective.SetMinimization();
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine("The problem does not have an optimal solution!");
return;
}
Console.WriteLine($"Number of bins used: {solver.Objective().Value()}");
double TotalWeight = 0.0;
for (int j = 0; j < data.NumBins; ++j)
{
double BinWeight = 0.0;
if (y[j].SolutionValue() == 1)
{
Console.WriteLine($"Bin {j}");
for (int i = 0; i < data.NumItems; ++i)
{
if (x[i, j].SolutionValue() == 1)
{
Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]}");
BinWeight += DataModel.Weights[i];
}
}
Console.WriteLine($"Packed bin weight: {BinWeight}");
TotalWeight += BinWeight;
}
}
Console.WriteLine($"Total packed weight: {TotalWeight}");
}
}