বিন প্যাকিং সমস্যা

মাল্টিপল ন্যাপস্যাক সমস্যার মতো, বিন প্যাকিং সমস্যার মধ্যেও আইটেমগুলিকে বিনে প্যাক করা জড়িত। যাইহোক, বিন প্যাকিং সমস্যা একটি ভিন্ন উদ্দেশ্য আছে: সব আইটেম রাখা হবে যে সব কম বিন খুঁজে.

নিম্নলিখিত দুটি সমস্যার মধ্যে পার্থক্য সংক্ষিপ্ত করে:

• একাধিক ন্যাপস্যাক সমস্যা: আইটেমগুলির একটি উপসেটকে একটি নির্দিষ্ট সংখ্যক বিনের মধ্যে প্যাক করুন, বিভিন্ন ক্ষমতা সহ, যাতে প্যাক করা আইটেমগুলির মোট মূল্য সর্বাধিক হয়৷

• বিন প্যাকিং সমস্যা: প্রয়োজন অনুযায়ী একটি সাধারণ ক্ষমতা সহ যতগুলি বিন দেওয়া হয়েছে, সবকটি আইটেম ধারণ করবে এমন কম সংখ্যক খুঁজে বের করুন। এই সমস্যায়, আইটেমগুলিকে মান নির্ধারণ করা হয় না, কারণ উদ্দেশ্যটি মান জড়িত নয়।

পরবর্তী উদাহরণ দেখায় কিভাবে একটি বিন প্যাকিং সমস্যা সমাধান করতে হয়।

উদাহরণ

এই উদাহরণে, বিভিন্ন ওজনের আইটেমগুলিকে একটি সাধারণ ক্ষমতার সাথে বিনের সেটে প্যাক করা দরকার। ধরে নিই যে সমস্ত আইটেম রাখার জন্য পর্যাপ্ত বিন রয়েছে, সমস্যাটি হল সবচেয়ে কম যা যথেষ্ট হবে তা খুঁজে বের করা।

নিম্নলিখিত বিভাগগুলি এই সমস্যার সমাধান করে এমন প্রোগ্রামগুলি উপস্থাপন করে। সম্পূর্ণ প্রোগ্রামের জন্য, সম্পূর্ণ প্রোগ্রাম দেখুন।

এই উদাহরণটি MPSolver র‍্যাপার ব্যবহার করে।

লাইব্রেরি আমদানি করুন

নিচের কোডটি প্রয়োজনীয় লাইব্রেরি আমদানি করে।

পাইথন

from ortools.linear_solver import pywraplp

সি++

#include <iostream>
#include <memory>
#include <numeric>
#include <ostream>
#include <vector>

#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

জাভা

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;

ডেটা তৈরি করুন

নীচের কোডটি উদাহরণের জন্য ডেটা তৈরি করে।

পাইথন

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

সি++

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

জাভা

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

তথ্য নিম্নলিখিত অন্তর্ভুক্ত:

• weights : আইটেমগুলির ওজন ধারণকারী একটি ভেক্টর।
• bin_capacity : একটি একক সংখ্যা যা বিনের ক্ষমতা প্রদান করে।

আইটেমগুলিতে কোনও মান বরাদ্দ নেই কারণ বিনের সংখ্যা হ্রাস করার লক্ষ্যে মান জড়িত নয়।

নোট করুন যে num_bins আইটেম সংখ্যা সেট করা হয়. এর কারণ যদি সমস্যাটির সমাধান থাকে, তবে প্রতিটি আইটেমের ওজন অবশ্যই বিন ধারণক্ষমতার কম বা সমান হতে হবে। সেক্ষেত্রে, আপনার প্রয়োজন হতে পারে সর্বাধিক সংখ্যক বিনের আইটেমের সংখ্যা, কারণ আপনি সর্বদা প্রতিটি আইটেমকে একটি পৃথক বিনে রাখতে পারেন।

সমাধানকারী ঘোষণা করুন

নিম্নলিখিত কোড সমাধানকারী ঘোষণা করে।

পাইথন

  # Create the mip solver with the SCIP backend.
  solver = pywraplp.Solver.CreateSolver("SCIP")

  if not solver:
      return

সি++

  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

জাভা

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

ভেরিয়েবল তৈরি করুন

নিম্নলিখিত কোড প্রোগ্রামের জন্য ভেরিয়েবল তৈরি করে।

পাইথন

# 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)

সি++

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, "");
}

জাভা

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

মাল্টিপল ন্যাপস্যাক উদাহরণের মতো, আপনি x[(i, j)] ভেরিয়েবলের একটি অ্যারে সংজ্ঞায়িত করেন, যার মান 1 হয় যদি i bin j এ স্থাপন করা হয় এবং অন্যথায় 0।

বিন প্যাকিংয়ের জন্য, আপনি ভেরিয়েবলের একটি অ্যারেও সংজ্ঞায়িত করুন, y[j] , যার মান 1 যদি বিন j ব্যবহার করা হয়-অর্থাৎ, যদি এটিতে কোনো আইটেম প্যাক করা হয়-এবং অন্যথায় 0। y[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"]
    )

সি++

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

জাভা

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

সীমাবদ্ধতাগুলি নিম্নরূপ:

• প্রতিটি আইটেম ঠিক একটি বিনে স্থাপন করা আবশ্যক. এই সীমাবদ্ধতাটি সমস্ত বিন j এ x[i][j] এর যোগফল 1-এর সমান হওয়া প্রয়োজন দ্বারা সেট করা হয়েছে। মনে রাখবেন যে এটি একাধিক ন্যাপস্যাক সমস্যা থেকে পৃথক, যেখানে যোগফল শুধুমাত্র এর থেকে কম বা সমান হওয়া প্রয়োজন 1, কারণ সমস্ত আইটেম প্যাক করতে হবে না।

• প্রতিটি বিনে প্যাক করা মোট ওজন তার ক্ষমতা অতিক্রম করতে পারে না। এটি মাল্টিপল ন্যাপস্যাক সমস্যার মতো একই সীমাবদ্ধতা, কিন্তু এই ক্ষেত্রে আপনি অসমতার ডান দিকের বিন ক্ষমতাকে y[j] দ্বারা গুণ করুন।

  কেন y[j] দ্বারা গুণ করা হয়? কারণ এটি y[j] 1 এর সমান করতে বাধ্য করে যদি কোনো আইটেম বিন j এ প্যাক করা হয়। এটি তাই কারণ যদি y[j] 0 হয়, অসমতার ডান দিকটি 0 হবে, যখন বাম দিকের বিন ওজন 0-এর চেয়ে বেশি হবে, সীমাবদ্ধতা লঙ্ঘন করবে৷ এটি y[j] ভেরিয়েবলকে সমস্যার উদ্দেশ্যের সাথে সংযুক্ত করে, আপাতত সমাধানকারী বিনের সংখ্যা কমানোর চেষ্টা করবে যার জন্য y[j] হল 1।

উদ্দেশ্য সংজ্ঞায়িত করুন

নিম্নলিখিত কোড সমস্যার জন্য উদ্দেশ্য ফাংশন সংজ্ঞায়িত করে।

পাইথন

# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))

সি++

// 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);

জাভা

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();

যেহেতু বিন j ব্যবহার করা হলে y[j] হল 1 এবং অন্যথায় 0, y[j] এর যোগফল হল ব্যবহৃত বিনের সংখ্যা। উদ্দেশ্য হল যোগফল কমানো।

সমাধানকারীকে কল করুন এবং সমাধানটি মুদ্রণ করুন

নিম্নলিখিত কোডটি সমাধানকারীকে কল করে এবং সমাধানটি প্রিন্ট করে।

পাইথন

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.")

সি++

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;

জাভা

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

সমাধানটি সমস্ত আইটেম প্যাক করার জন্য প্রয়োজনীয় বিনের ন্যূনতম সংখ্যা দেখায়। ব্যবহৃত প্রতিটি বিনের জন্য, সমাধানটি এতে প্যাক করা আইটেমগুলি এবং মোট বিন ওজন দেখায়।

প্রোগ্রামের আউটপুট

আপনি যখন প্রোগ্রাম চালান, এটি নিম্নলিখিত আউটপুট প্রদর্শন করে।

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

সম্পূর্ণ প্রোগ্রাম

বিন প্যাকিং সমস্যার সম্পূর্ণ প্রোগ্রামগুলি নীচে দেখানো হয়েছে।

পাইথন

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()
 

সি++

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

জাভা

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