Source code for qiskit_optimization.applications.bin_packing

# This code is part of a Qiskit project.
# (C) Copyright IBM 2021, 2023.
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""An application class for the bin packing."""

from typing import List, Union, Optional

import numpy as np
from import Model

import qiskit_optimization.optionals as _optionals
from qiskit_optimization.algorithms import OptimizationResult
from qiskit_optimization.problems.quadratic_program import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp
from .optimization_application import OptimizationApplication

if _optionals.HAS_MATPLOTLIB:
    from matplotlib.pyplot import Figure

    class Figure:  # type: ignore
        """Empty Figure class
        Replacement Figure for when matplotlib is not present.


[docs]class BinPacking(OptimizationApplication): """Optimization application for the "bin packing" [1] problem. References: [1]: "Bin packing", ` <>`_ """ def __init__( self, weights: List[int], max_weight: int, max_number_of_bins: Optional[int] = None ) -> None: """ Args: weights: A list of the weights of items max_weight: The maximum bin weight capacity max_number_of_bins: The maximum number of bins by default equal to the number of items """ self._weights = weights self._max_weight = max_weight if max_number_of_bins is None: self._max_number_of_bins = len(weights) else: self._max_number_of_bins = max_number_of_bins
[docs] def to_quadratic_program(self) -> QuadraticProgram: """Convert a bin packing problem instance into a :class:`~qiskit_optimization.problems.QuadraticProgram` Returns: The :class:`~qiskit_optimization.problems.QuadraticProgram` created from the bin packing problem instance. """ mdl = Model(name="BinPacking") num_bins = self._max_number_of_bins num_items = len(self._weights) y = mdl.binary_var_list(num_bins, name="y") mdl.minimize(mdl.sum(y)) x = mdl.binary_var_matrix(num_items, num_bins, name="x") for i in range(num_items): # First set of constraints: the items must be in any bin mdl.add_constraint(mdl.sum(x[i, j] for j in range(num_bins)) == 1) for j in range(num_bins): # Second set of constraints: weight constraints mdl.add_constraint( mdl.sum(self._weights[i] * x[i, j] for i in range(num_items)) <= self._max_weight * y[j] ) op = from_docplex_mp(mdl) return op
[docs] def interpret(self, result: Union[OptimizationResult, np.ndarray]) -> List[List[int]]: """Interpret a result as item indices Args: result : The calculated result of the problem Returns: items_in_bins: A list of lists with the items in each bin """ x = self._result_to_x(result) num_items = len(self._weights) num_bins = self._max_number_of_bins bins = x[:num_bins] items = np.array(x[num_bins:]).reshape((num_items, num_bins)) items_in_bins = [ [i for i in range(num_items) if bins[j] and items[i, j]] for j in range(num_bins) ] return items_in_bins
[docs] @_optionals.HAS_MATPLOTLIB.require_in_call def get_figure(self, result: Union[OptimizationResult, np.ndarray]) -> Figure: """Get plot of the solution of the Bin Packing Problem. Args: result : The calculated result of the problem Returns: fig: A plot of the solution, where x and y represent the bins and sum of the weights respectively. """ import matplotlib.pyplot as plt colors = plt.colormaps["jet"].resampled(len(self._weights)) items_in_bins = self.interpret(result) num_bins = len(items_in_bins) fig, axes = plt.subplots() for _, bin_i in enumerate(items_in_bins): sum_items = 0 for item in bin_i: _, self._weights[item], bottom=sum_items, label=f"Item {item}", color=colors(item), ) sum_items += self._weights[item] axes.hlines( self._max_weight, -0.5, num_bins - 0.5, linestyle="--", color="tab:red", label="Max Weight", ) axes.set_xticks(np.arange(num_bins)) axes.set_xlabel("Bin") axes.set_ylabel("Weight") axes.legend() return fig