The Bin Packing Problem

Like the multiple knapsack problem, the bin packing problem also involves packing items into bins. However, the bin packing problem has a different objective: find the fewest bins that will hold all the items.

The following summarizes the differences between the two problems:

  • Multiple knapsack problem: Pack a subset of the items into a fixed number of bins, with varying capacities, so that the total value of the packed items is a maximum.

  • Bin packing problem: Given as many bins with a common capacity as necessary, find the fewest that will hold all the items. In this problem, the items aren't assigned values, because the objective doesn't involve value.

The next example shows how to solve a bin packing problem.

Example

In this example, items of various weights need to be packed into a set of bins with a common capacity. Assuming that there are enough bins to hold all the items, the problem is to find the fewest that will suffice.

Create the data

The code below creates the data for the example.

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 double[] Weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
  public double[] BinCapacity = 100;
  public int NumItems = Weights.Length;
  public int NumBins = Weights.Length;
}

The data includes the following:

  • weights: A vector containing the weights of the items.
  • bin_capacity: A single number giving the capacity of the bins.

There are no values assigned to the items because the goal of minimizing the number of bins doesn't involve value.

Note that num_bins is set to the number of items. This is because if the problem has a solution, then the weight of every item must be less than or equal to the bin capacity. In that case, the maximum number of bins you could need is the number of items, because you could always put each item in a separate bin.

Declare the solver

The example uses the mixed integer programming solver. The following code declares the solver.

Python

  # Create the mip solver with the CBC backend.
  solver = pywraplp.Solver('simple_mip_program',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
     

C++

  // Create the mip solver with the CBC backend.
  MPSolver solver("simple_mip_program",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);
     

Java

// MOE:begin_strip
// Create the linear solver with the SCIP backend.
MPSolver solver = new MPSolver("SimpleMipProgram",
    MPSolver.OptimizationProblemType.SCIP_MIXED_INTEGER_PROGRAMMING);
/* MOE:end_strip_and_replace
// Create the linear solver with the CBC backend.
MPSolver solver = new MPSolver("SimpleMipProgram",
    MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING); */

C#

  // Create the linear solver with the CBC backend.
  Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
      

Create the variables

The following code creates the variables for the program.

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#

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] = MakeIntVar(0, 1, String.Format("x_{0}_{1}", i, j));
  }
}
MPVariable[] y = new MPVariable[data.NumBins];
for (int j = 0; j < data.NumBins; j++)
  {
    y[j] = MakeIntVar(0, 1, String.Format("y_{0}", j));
  }

As in the multiple knapsack example, you define an array of variables x[(i, j)], whose value is 1 if item i is placed in bin j, and 0 otherwise.

For bin packing, you also define an array of variables, y[j], whose value is 1 if bin j is used—that is, if any items are packed in it—and 0 otherwise. The sum of the y[j] will be the number of bins used.

Define the constraints

The following code defines the constraints for the problem:

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) {
  LinearExpr sum;
  for (int j = 0; j < data.NumBins; ++j) {
    sum += x[i][j];
  }
}
solver.MakeRowConstraint(sum == 1.0);
for (int i = 0; i < data.NumConstraints; ++i)
{
  MPConstraint constraint = solver.MakeConstraint(0, data.Bounds[i], "");
  for (int j = 0; j < data.NumVars; ++j)
  {
    constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i][j]);
  }
}
for (int j = 0; j < data.NumBins; ++j)
{
  LinearExpr Weight;
  for (int i = 0; i < data.NumItems; ++i)
  {
    Weight += data.Weights[i]*LinearExpr(x[i][j]);
  }
solver.MakeRowConstraint(Weight <= data.BinCapacities[j]);
}

The constraints are the following:

  • Each item must be placed in exactly one bin. This constraint is set by requiring that the sum of x[i][j] over all bins j is equal to 1. Note that this differs from the multiple knapsack problem, in which the sum is only required to be less than or equal to 1, because not all items have to be packed.
  • The total weight packed in each bin can't exceed its capacity. This is the same constraint as in the multiple knapsack problem, but in this case you multiply the bin capacity on the right side of the inequalities by y[j].

    Why multiply by y[j]? Because it forces y[j] to equal 1 if any item is packed in bin j. This is so because if y[j] were 0, the right side of the inequality would be 0, while the bin weight on the left side would be greater than 0, violating the constraint. This connects the variables y[j] to the objective of the problem, for now the solver will try to minimize the number of bins for which y[j] is 1.

Define the objective

The following code defines the objective function for the problem.

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 = solver.Objective();
LinearExpr NumBinsUsed;
  for (int j = 0; j < data.NumBins; ++j)
  {
    NumBinsUsed += y[j];
  }
}
objective.MinimizeLinearExpr(NumBinsUsed);

Since y[j] is 1 if bin j is used, and 0 otherwise, the sum of the y[j] is the number of bins used. The objective is to minimize the sum.

Call the solver and print the solution

The following code calls the solver and prints the solution.

Python

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_weight > 0:
        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());
int TotalWeight = 0;
for (int j = 0; j < data.NumBins; ++j)
{
  int BinWeight = 0;
  if (y[j] == 1)
  {
    Console.WriteLine("Bin " + j);
    for (int i = 0; i < data.NumItems; ++i)
    {
      if (x[i][j].SolutionValue() == 1)
      {
        Console.WriteLine("Item " + i + " weight: " + data.Weights[i]
                                  + "  values: " + data.Values[i];
        BinWeight += data.Weights[i];
      }
    }
    Console.WriteLine("Packed bin weight: " + BinWeight);
    TotalWeight += BinWeight;
  }
  Console.WriteLine("Total packed weight: " + TotalWeight);

The solution shows the minimum number of bins required to pack all the items. For each bin that is used, the solution shows the items packed in it, and the total bin weight.

Output of the program

When you run the program, it displays the following output.

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

Complete programs

The complete programs for the bin packing problem are shown below.

Python

from __future__ import print_function
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 CBC backend.
  solver = pywraplp.Solver('simple_mip_program',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
  # 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']]))

  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_weight > 0:
          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 "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 CBC backend.
  MPSolver solver("simple_mip_program",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);
  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

import com.google.wrappers.util.operationsresearch.linearsolver.MPConstraint;
import com.google.wrappers.util.operationsresearch.linearsolver.MPObjective;
import com.google.wrappers.util.operationsresearch.linearsolver.MPSolver;
import com.google.wrappers.util.operationsresearch.linearsolver.MPVariable;
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 {
  final DataModel data = new DataModel();
// MOE:begin_strip
// Create the linear solver with the SCIP backend.
MPSolver solver = new MPSolver("SimpleMipProgram",
    MPSolver.OptimizationProblemType.SCIP_MIXED_INTEGER_PROGRAMMING);
/* MOE:end_strip_and_replace
// Create the linear solver with the CBC backend.
MPSolver solver = new MPSolver("SimpleMipProgram",
    MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING); */
    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 double[] Weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
    public double[] BinCapacity = 100;
    public int NumItems = Weights.Length;
    public int NumBins = Weights.Length;
  }
  public static void Main()
  {
    DataModel data = new DataModel();
    // Create the linear solver with the CBC backend.
    Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
    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] = MakeIntVar(0, 1, String.Format("x_{0}_{1}", i, j));
      }
    }
    MPVariable[] y = new MPVariable[data.NumBins];
    for (int j = 0; j < data.NumBins; j++)
      {
        y[j] = MakeIntVar(0, 1, String.Format("y_{0}", j));
      }

    for (int i = 0; i < data.NumItems; ++i) {
      LinearExpr sum;
      for (int j = 0; j < data.NumBins; ++j) {
        sum += x[i][j];
      }
    }
    solver.MakeRowConstraint(sum == 1.0);
    for (int i = 0; i < data.NumConstraints; ++i)
    {
      MPConstraint constraint = solver.MakeConstraint(0, data.Bounds[i], "");
      for (int j = 0; j < data.NumVars; ++j)
      {
        constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i][j]);
      }
    }
    for (int j = 0; j < data.NumBins; ++j)
    {
      LinearExpr Weight;
      for (int i = 0; i < data.NumItems; ++i)
      {
        Weight += data.Weights[i]*LinearExpr(x[i][j]);
      }
    solver.MakeRowConstraint(Weight <= data.BinCapacities[j]);
    }

    objective = solver.Objective();
    LinearExpr NumBinsUsed;
      for (int j = 0; j < data.NumBins; ++j)
      {
        NumBinsUsed += y[j];
      }
    }
    objective.MinimizeLinearExpr(NumBinsUsed);

    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());
    int TotalWeight = 0;
    for (int j = 0; j < data.NumBins; ++j)
    {
      int BinWeight = 0;
      if (y[j] == 1)
      {
        Console.WriteLine("Bin " + j);
        for (int i = 0; i < data.NumItems; ++i)
        {
          if (x[i][j].SolutionValue() == 1)
          {
            Console.WriteLine("Item " + i + " weight: " + data.Weights[i]
                                      + "  values: " + data.Values[i];
            BinWeight += data.Weights[i];
          }
        }
        Console.WriteLine("Packed bin weight: " + BinWeight);
        TotalWeight += BinWeight;
      }
      Console.WriteLine("Total packed weight: " + TotalWeight);
    }
  }
}