class BppDataCenter:
def __init__(self, num_bins,
num_items,
bin_capacity,
item_sizes):
self._num_bins = num_bins
self._num_items = num_items
self._bin_capacity = bin_capacity
self._item_sizes = item_sizes
@property
def num_bins(self): return self._num_bins
@property
def num_items(self): return self._num_items
@property
def bin_capacity(self): return self._bin_capacity
@property
def item_sizes(self): return self._item_sizes13 The Bin Packing Problem
The bin packing problem (BPP) is a classic optimization problem in computer science that involves packing a set of items into a minimum number of bins or containers, subject to certain constraints. The problem is also known as the container loading problem, or the bin packing optimization problem.
In the bin packing problem, we are given a set of items, each with a weight or size, and a set of bins, each with a fixed capacity. The goal is to pack the items into the bins such that the number of bins used is minimized.
The problem is NP-hard, which means that there is no known algorithm that can solve it in polynomial time. However, several heuristic algorithms have been developed that can provide good solutions in practice.
The bin packing problem has many real-world applications, such as optimizing the use of storage space in warehouses, minimizing the number of trucks needed for transportation, and optimizing the use of computer memory. It is also a fundamental problem in the study of computational complexity theory and has been extensively studied in the fields of operations research, computer science, and mathematics.
To formally express the bin packing problem (BPP), we use the notation of a set of items that need to be packed into a set of bins. The set of items is denoted as \(\mathcal{I}\), while the set of bins is denoted as \(\mathcal{J}\). Each item \(i\) in \(\mathcal{I}\) has a size denoted as \(s_i\), and each bin \(j\) in \(\mathcal{J}\) has a fixed capacity denoted as \(Q\). To solve the problem, we introduce two decision variables: \(y_j\) and \(x_{ij}\).
- The variable \(y_j\) is a binary variable that takes the value 1 if the bin \(j\) is used and 0 otherwise.
- The variable \(x_{ij}\) is a binary variable that takes the value 1 if item \(i\) is placed into bin \(j\) and 0 otherwise.
Using these decision variables, the BPP can be formulated as follows.
\[\begin{align} \text{min.} &\quad \sum_{j \in \mathcal{J}} y_j \label{bin-obj} \\ \text{s.t.} &\quad \sum_{i \in \mathcal{I}} s_i x_{ij} \leq Q y_j, \ \forall j \in \mathcal{J} \label{bin-cons1} \\ &\quad \sum_{j \in \mathcal{J}} x_{ij} = 1, \ \forall i \in \mathcal{I} \label{bin-cons2} \\ &\quad y_j \in \{0, 1\}, \ \forall j \in \mathcal{J} \label{bin-cons3} \\ &\quad x_{ij} \in \{0, 1\}, \ \forall i \in \mathcal{I}, j \in \mathcal{J} \label{bin-cons4} \end{align}\]
The objective function of the problem is to minimize the number of bins used, which is represented by the summation of the binary decision variable \(y_j\), where \(j\) denotes the bins used in the solution.
The problem has four constraints that need to be satisfied. The first constraint (\(\ref{bin-cons1}\)) ensures that the total size of items placed in each bin \(j\) does not exceed its capacity \(Q\), multiplied by the binary decision variable \(y_j\). This constraint ensures that items are only placed in bins that are actually used, i.e., those for which \(y_j=1\). The second constraint (\(\ref{bin-cons2}\)) ensures that each item is placed in exactly one bin. The third constraint (\(\ref{bin-cons3}\)) restricts the binary variable \(y_j\) to only take the values 0 or 1. This constraint ensures that only the used bins are counted in the objective function. The fourth constraint (\(\ref{bin-cons4}\)) restricts the binary variable \(x_{ij}\) to only take the values 0 or 1. This constraint ensures that each item is either placed in a bin or not.
The following Python class BppDataCenter is designed to hold data for an instance of the bin packing problem. The constructor of the class takes in four arguments: num_bins, num_items, bin_capacity, and item_sizes.
num_binsis an integer that specifies the number of bins available in the problem instance.num_itemsis an integer that specifies the number of items that need to be packed into the bins.bin_capacityis an integer that specifies the maximum capacity of each bin.item_sizesis a list of integers that specifies the size of each item.
The class has four properties that allow access to the instance variables:
num_binsreturns the number of bins.num_itemsreturns the number of items.bin_capacityreturns the maximum capacity of each bin.item_sizesreturns the list of item sizes.
Overall, this class is a convenient way to encapsulate the data of a bin packing problem instance in a single object, making it easier to pass the data to functions or algorithms that solve the problem.
This Python class BppSolver uses the Google OR-Tools library to solve the Bin Packing Problem. It takes an instance of BppDataCenter class as input, which holds the problem data. The class has several methods to build the optimization model, solve it, and return the optimal objective value, variables and constraints.
The build_model() method creates the optimization model by first initializing a solver object, then creating decision variables using Boolean variables BoolVar(), defining the objective function using the Minimize() method, and defining constraints using the Add() method.
The optimize() method solves the optimization model using the Solve() method of the solver object, and returns the optimal objective value, variables, and constraints. It uses the solution_value() method of the variables to extract the optimal values of the variables.
The create_variables() method creates decision variables for the model using BoolVar() method from the solver object. It creates binary variables \(y\) and \(x\) for the problem. Variable \(y\) indicates whether a bin is used or not, while variable \(x\) indicates whether an item is placed in a particular bin.
The create_objective() method creates an objective function for the model using the Minimize method. It aims to minimize the number of used bins.
The create_constraints() method creates constraints for the model using the Add method. It creates two constraints for each bin. The first constraint ensures that the sum of the sizes of the items placed in a bin does not exceed the bin capacity. The second constraint ensures that each item is placed in exactly one bin.
import numpy as np
from itertools import product
from ortools.linear_solver import pywraplp
class BppSolver:
def __init__(self, data_center):
self._data_center = data_center
self._solver = None
self._var_y = None
self._var_x = None
self._opt_obj = None
self._opt_y = None
self._opt_x = None
def build_model(self):
self._solver = pywraplp.Solver.CreateSolver('SCIP')
self._create_variables()
self._create_objective()
self._create_constraints()
def optimize(self):
num_bins = self._data_center.num_bins
num_items = self._data_center.num_items
status = self._solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
self._opt_obj = self._solver.Objective().Value()
self._opt_y = [
self._var_y[b].solution_value()
for b in range(num_bins)
]
self._opt_x = np.zeros((num_items, num_bins))
for i, b in product(range(num_items),
range(num_bins)):
self._opt_x[i][b] = \
self._var_x[i][b].solution_value()
def _create_variables(self):
num_bins = self._data_center.num_bins
self._var_y = [
self._solver.BoolVar(name=f'y_{b}')
for b in range(num_bins)
]
num_items = self._data_center.num_items
self._var_x = np.empty((num_items, num_bins),
dtype=object)
for i, b in product(range(num_items),
range(num_bins)):
self._var_x[i][b] = \
self._solver.BoolVar(name=f'x_{i, b}')
def _create_objective(self):
self._solver.Minimize(
self._solver.Sum(
self._var_y
)
)
def _create_constraints(self):
num_bins = self._data_center.num_bins
num_items = self._data_center.num_items
bin_capacity = self._data_center.bin_capacity
item_sizes = self._data_center.item_sizes
for b in range(num_bins):
expr = [
item_sizes[i] *
self._var_x[i][b]
for i in range(num_items)
]
self._solver.Add(
self._solver.Sum(expr) <= \
bin_capacity * self._var_y[b]
)
for i in range(num_items):
expr = [
self._var_x[i][b]
for b in range(num_bins)
]
self._solver.Add(
self._solver.Sum(expr) == 1
)
In the code below, we try to solve a BPP instance using the above class. The file binpack1.txt contains several instances and they are all too large to solve within reasonable time. We will solve a truncated version of the first instance in the file by considering only the first 15 items. The optimal objective value is 6.
import re
data_file = "./data/bpp/binpack1.txt"
with open(data_file) as f:
num_instanes = int(f.readline())
for inst in range(num_instanes):
inst_name = f.readline()[:-1]
print(f"Solving instance: {inst_name}")
bin_capacity, \
num_items, \
min_num_bins = f.readline().split()
sizes = []
for i in range(int(num_items)):
line = f.readline()
number = int(re.findall(r'\d+', line)[0])
sizes.append(number)
data_center = BppDataCenter(
num_bins=int(min_num_bins),
num_items=15,
bin_capacity=int(bin_capacity),
item_sizes=sizes
)
solver = BppSolver(data_center)
solver.build_model()
solver.optimize()
print(f'Optimal objective value = {solver._opt_obj}')
breakSolving instance: u120_00
Optimal objective value = 6.0