Vấn đề khi đóng gói thùng

Giống như bài toán nhiều ba lô, bài toán đóng gói thùng rác cũng liên quan đến đang đóng gói hàng vào thùng. Tuy nhiên, vấn đề đóng gói thùng rác có một mục tiêu: tìm ít thùng nhất có thể chứa tất cả các mục.

Dưới đây là tóm tắt sự khác biệt giữa hai vấn đề:

• Bài toán về ba lô ba lô: Đóng gói một tập hợp con các mặt hàng vào một số lượng cố định các thùng có dung tích khác nhau sao cho tổng giá trị của các mặt hàng được đóng gói là tối đa.

• Vấn đề về việc đóng gói thùng: Khi có nhiều thùng có sức chứa chung cần thiết, tìm ít ảnh nhất chứa tất cả ảnh và video. Trong bài tập này, các mục không được chỉ định giá trị vì mục tiêu không liên quan đến giá trị.

Ví dụ tiếp theo cho thấy cách giải một bài toán về việc đóng gói thùng rác.

Ví dụ:

Trong ví dụ này, các mặt hàng 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ó dung lượng chung. Giả sử có đủ thùng để chứa tất cả vấn đề là tìm ra ít mục nhất vừa đủ.

Các phần sau đây trình bày những chương trình giải quyết vấn đề này. Để xem đầy đủ chương trình, hãy xem Hoàn tất chương trình.

Ví dụ này sử dụng trình bao bọc MPSolver.

Nhập thư viện

Đoạn mã dưới đây 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

Đoạn mã dưới đây tạo dữ liệu cho ví dụ.

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;
}

Dữ liệu này bao gồm:

• weights: Vectơ chứa trọng số của các mục.
• bin_capacity: Một số duy nhất biểu thị sức chứa 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ố thùng không liên quan đến giá trị.

Xin lưu ý rằng num_bins được đặt thành số mục. Điều này là do nếu bài toán có lời giải, khi đó trọng số của mỗi mục phải nhỏ hơn hoặc bằng so với sức chứa của thùng. Trong trường hợp đó, số thùng tối đa bạn có thể cần là số lượng 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.

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 biến

Đoạ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ề ba lô, bạn xác định một mảng gồm các biến x[(i, j)], có giá trị là 1 nếu mục i được đặt trong thùng j và nếu không thì là 0.

Để đóng gói thùng, bạn cũng xác định một mảng các biến, y[j], có giá trị là 1 nếu thùng j được sử dụng (tức là nếu có mục nào được đóng gói trong thùng rác đó) và giá trị 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

Đoạn mã sau đây xác định các quy tắc ràng buộc cho bài toán này:

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ác quy tắc ràng buộc như sau:

• Mỗi mục phải được cho vào đúng một thùng. Hạn chế này được đặt bởi yêu cầu tổng của x[i][j] trên tất cả các thùng j phải bằng 1. Ghi chú điều này khác với bài toán ba lô, trong đó tổng là chỉ bắt buộc phải 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à giới hạn tương tự như trong bài toán ba lô, nhưng trong trường hợp này bạn nhân dung lượng của thùng ở bên phải của các bất đẳng thức với y[j].

  Tại sao nhân với y[j]? Bởi vì phương thức này buộc y[j] bằng 1 nếu có mục nào đó là đóng gói trong thùng j. Nguyên nhân là do nếu y[j] bằng 0, thì phía bên phải của bất đẳng thức sẽ là 0, trong khi trọng số của thùng ở bên trái sẽ là lớn hơn 0 thì vi phạm giới hạn. Thao tác này sẽ kết nối các biến y[j] mục tiêu của bài tập, hiện nay, người giải quyết sẽ cố gắng giảm thiểu số lượng thùng trong đó y[j] là 1.

Xác định mục tiêu

Mã sau đây xác định hàm mục tiêu của bài toán này.

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 có sử dụng bin j và là 0 nếu không sử dụng bin j, nên tổng của y[j] sẽ là số lượng thùng được sử dụng. Mục tiêu là giảm thiểu tổng.

Gọi trình giải và in lời giải

Đoạn mã sau đây gọi trình giải và in đáp án.

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 biết số thùng 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ẽ hiển thị các mục được đóng gói trong đó và tổng trọng lượng của 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 tất chương trình

Dưới đây là các chương trình hoàn chỉnh cho vấn đề về việc đó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}");
    }
}