Bengali
ভাষাসমূহ
English
Bengali
Japanese
Shortcuts

Source code for qiskit_optimization.applications.bin_packing

# This code is part of Qiskit.
#
# (C) Copyright IBM 2021.
#
# 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
from qiskit.exceptions import MissingOptionalLibraryError

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

try:
    import matplotlib.pyplot as plt
    from matplotlib.pyplot import Figure

    _HAS_MATPLOTLIB = True
except ImportError:
    _HAS_MATPLOTLIB = False

    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] 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. Raises: MissingOptionalLibraryError: if matplotlib is not installed. """ if not _HAS_MATPLOTLIB: raise MissingOptionalLibraryError( libname="matplotlib", name="GraphOptimizationApplication", pip_install="pip install 'qiskit-optimization[matplotlib]'", ) colors = plt.cm.get_cmap("jet", 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

© Copyright 2018, 2021, Qiskit Optimization Development Team.

Built with Sphinx using a theme provided by Read the Docs.