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 http://www.apache.org/licenses/LICENSE-2.0.
#
# 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 docplex.mp.model 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
else:

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

        pass


[docs]class BinPacking(OptimizationApplication): """Optimization application for the "bin packing" [1] problem. References: [1]: "Bin packing", `https://en.wikipedia.org/wiki/Bin_packing_problem <https://en.wikipedia.org/wiki/Bin_packing_problem>`_ """ 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: axes.bar( _, 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