Bin Packing#

This example solves the known hard problem of bin packing to demonstrate using a Leap hybrid CQM solver on a constrained problem with binary variables.

The bin-packing problem is to pack into a number of bins of limited capacity, \(c\), a collection of items. Each item, \(i\), with weight, \(w_i\), should be assigned to bin, \(b_j\), in such a way as to minimize the number of bins used.

Example Requirements#

The code in this example requires that your development environment have Ocean software and be configured to access SAPI, as described in the Initial Set Up section.

Solution Steps#

Section Workflow Steps: Formulation and Sampling describes the problem-solving workflow as consisting of two main steps: (1) Formulate the problem as an objective function in a supported model and (2) Solve your model with a D-Wave solver.

This example formulates the bin-packing problem as a constrained quadratic model and uses the LeapHybridCQMSampler to find good solutions.

Formulate the Problem#

First, set up the problem parameters.

  • num_items is the number of items.

  • weights assigns weights, \(w_i\), to each item, i, randomly within a configurable range, item_weight_range.

  • bin_capacity is the bin capacity, \(c\), set based on the average weight.

>>> import numpy as np
>>> num_items = 15
>>> item_weight_range = [3, 7]
>>> weights = list(np.random.randint(*item_weight_range, num_items))
>>> bin_capacity = int(10 * np.mean(weights))
>>> print("Problem: pack a total weight of {} into bins of capacity {}.".format(
...       sum(weights), bin_capacity))              
Problem: pack a total weight of 77 into bins of capacity 51.

Instantiate a CQM.

>>> from dimod import ConstrainedQuadraticModel
>>> cqm = ConstrainedQuadraticModel()

You can now formulate an objective function to optimize and constraints any feasible solution must meet, and set these in your CQM.

Objective Function#

The objective function to minimize is the number of used bins. Because a bin is either used or not, you can indicate bin usage with binary variables.

Binary variable[1] bin_used_<j> indicates that bin \(b_j\) is in use. The worst possible case is that each item requires an entire bin to itself, so the maximum number of bins (and the number of binary variables bin_used_<j> to instantiate) is equal to the number of items, num_items.

>>> from dimod import Binary
>>> bin_used = [Binary(f'bin_used_{j}') for j in range(num_items)]

To minimize the number of used bins is to minimize the sum of bin_used_<j> variables with value 1 (True, meaning the bin is being used):

\[\min (\sum_j b_j)\]
>>> cqm.set_objective(sum(bin_used))

Constraints#

The bin-packing problem has two constraints:

  1. Each item can go into only one bin. This again is a binary outcome: item \(i\) is either in bin \(b_j\) or not. You can express this constraint, using binary variables, \(x_{i,j}\), as

    \[\sum_j x_{i,j} == 1.\]

    That is, over all \(j\) bins, there is just one \(x_{i,j}\) with value True (or item_<i>_in_bin_<j> == 1 in the code below) for each \(i\).

>>> item_in_bin = [[Binary(f'item_{i}_in_bin_{j}') for j in range(num_items)]
...      for i in range(num_items)]
>>> for i in range(num_items):
...     one_bin_per_item = cqm.add_constraint(sum(item_in_bin[i]) == 1, label=f'item_placing_{i}')

  1. Each bin has limited capacity. You can express this constraint for each bin, \(b_j\), by summing over \(i\) per value of \(j\):

    \[\sum_i x_{i, j} * w_i <= c\]

    That is, for each bin \(b_j\), the sum of weights for those items placed in the bin (item_<i>_in_bin_<j> == 1) does not exceed capacity.

>>> for j in range(num_items):
...     bin_up_to_capacity = cqm.add_constraint(
...         sum(weights[i] * item_in_bin[i][j] for i in range(num_items)) - bin_used[j] * bin_capacity <= 0,
...         label=f'capacity_bin_{j}')

For 15 items and allowing for the worst case of 15 bins, this CQM requires over 200 binary variables:

>>> len(cqm.variables)
240

Given that bin capacity is defined above as ten times the average weight, one could easily reduce the complexity of this model by setting the number of bins much smaller.

Solve the Problem by Sampling#

D-Wave’s quantum cloud service provides cloud-based hybrid solvers you can submit arbitrary QMs to. These solvers, which implement state-of-the-art classical algorithms together with intelligent allocation of the quantum processing unit (QPU) to parts of the problem where it benefits most, are designed to accommodate even very large problems. Leap’s solvers can relieve you of the burden of any current and future development and optimization of hybrid algorithms that best solve your problem.

Ocean software’s dwave-system LeapHybridCQMSampler class enables you to easily incorporate Leap’s hybrid CQM solvers into your application:

>>> from dwave.system import LeapHybridCQMSampler
>>> sampler = LeapHybridCQMSampler()

Submit the CQM to the selected solver. For one particular execution, with a maximum allowed runtime of 3 minutes, the CQM hybrid sampler returned 47 samples, out of which 31 were solutions that met all the constraints:

>>> sampleset = sampler.sample_cqm(cqm,
...                                time_limit=180,
...                                label="SDK Examples - Bin Packing")  
>>> feasible_sampleset = sampleset.filter(lambda row: row.is_feasible)  
>>> if len(feasible_sampleset):      
...    best = feasible_sampleset.first
...    print("{} feasible solutions of {}.".format(
...       len(feasible_sampleset), len(sampleset)))
31 feasible solutions of 47.

The best solution found a packing that required 2 bins:

>>> selected_bins = [key for key, val in best.sample.items() if 'bin_used' in key and val]   
>>> print("{} bins are used.".format(len(selected_bins)))     
2 bins are used.

The code below defines a simple function, get_indices, that returns the indices signifying the bin and item from variable names. This is used below in parsing the solutions returned from the hybrid solver.

>>> def get_indices(name):
...     return [int(digs) for digs in name.split('_') if digs.isdigit()]

For the best feasible solution, print the packing.

>>> for bin in selected_bins:                        
...     in_bin = [key for key, val in best.sample.items() if
...        "_in_bin" in key and
...        get_indices(key)[1] == get_indices(bin)[0]
...        and val]
...     b = get_indices(in_bin[0])[1]
...     w = [weights[get_indices(item)[0]] for item in in_bin]
...     print("Bin {} has weights {} for a total of {}.".format(b, w, sum(w)))
Bin 1 has weights [4, 4, 6, 4, 6, 4, 6] for a total of 34.
Bin 14 has weights [5, 6, 4, 6, 4, 6, 6, 6] for a total of 43.

The items were distributed in a way that kept each bin below its capacity.