# Scaling for Production¶

This section provides guidance on coding your application for performance on problems of the industrial scale supported by Leap’s quantum-classical hybrid solvers.

While the code examples below focus on constrained quadratic models (CQMs), most the guidance is also applicable to binary quadratic models (BQMs) and quadratic models (QMs).

This section does not discuss algorithmic complexity or problem formulation. For information about problem formulation, the Getting Started with D-Wave Solvers guide provides an introduction and the Problem-Solving Handbook guide describes more advanced techniques.

## Simple Example Application¶

Tip

You can run the following code by downloading the Jupyter Notebook.

The code below formulates a simple bin packing problem, as explained in the Ocean SDK’s Bin Packing example.

For simplicity, assume that each bin has a capacity of 1 and start by generating weights for the items you wish to pack. A packing problem with n items results in a CQM with $$n \times (n+1)$$ binary variables.

import numpy as np

num_items = 100  # results in 10100 binary variables

weights = np.random.default_rng(42).random(num_items)


## Initial Code¶

The first implementation is written for readability and pedagogy. As shown below, this comes at the cost of speed.

import typing

import dimod

"""Generate a bin packing problem as a constrained quadratic model."""

n = len(weights)

# y_j indicates that bin j is used
y = [dimod.Binary(f'y_{j}') for j in range(n)]

# x_i,j indicates that item i is put in bin j
x = [[dimod.Binary(f'x_{i},{j}') for j in range(n)] for i in range(n)]

# minimize the number of bins used
cqm.set_objective(sum(y))

# each item can go in only one bin
for i in range(n):

# each bin has a capacity that must be respected
for j in range(n):
cqm.add_constraint(sum(weights[i] * x[i][j] for i in range(n)) - y[j] <= 0,
label=f'capacity_bin_{j}')

return cqm


Time the construction:

In : %timeit bin_packing(weights)
385 ms ± 9.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


Note

Because runtimes are highly system dependent, running the code on your system will likely result in different values. The results shown here are illustrative.

## Use the quicksum Function¶

The easiest improvement you can make is to substitute quicksum() for the Python sum(), which creates a large number of intermediate objects not created by quicksum().

import typing

import dimod

"""Generate a bin packing problem as a constrained quadratic model."""

n = len(weights)

# y_j indicates that bin j is used
y = [dimod.Binary(f'y_{j}') for j in range(n)]

# x_i,j indicates that item i is put in bin j
x = [[dimod.Binary(f'x_{i},{j}') for j in range(n)] for i in range(n)]

# minimize the number of bins used
cqm.set_objective(dimod.quicksum(y))

# each item can only go in one bin
for i in range(n):

# each bin has a capacity that must be respected
for j in range(n):
cqm.add_constraint(dimod.quicksum(weights[i] * x[i][j] for i in range(n)) - y[j] <= 0,
label=f'capacity_bin_{j}')

return cqm


This simple change already reduces the runtime.

In : %timeit bin_packing(weights)
294 ms ± 9.39 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


## Construct Models Directly¶

You can achieve an even bigger improvement by skipping symbolic construction altogether, working directly with variable labels and a single BQM object.

The following small example demonstrates the performance difference. See Symbolic Math for a discussion of the difference between variables and labels.

import dimod

return dimod.quicksum(2*dimod.Binary(v) for v in range(num_variables))

bqm.add_linear_from((v, 2) for v in range(num_variables))
return bqm

In : %timeit make_bqm_symbolic(1000)
12.7 ms ± 213 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In : %timeit make_bqm_labels(1000)
194 µs ± 2.32 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


Apply this same model construction to the binpacking example:

import typing

import dimod

"""Generate a bin packing problem as a constrained quadratic model."""

n = len(weights)

# y_j indicates that bin j is used
y_labels = [f'y_{j}' for j in range(n)]

# x_i,j indicates that item i is put in bin j
x_labels = [[f'x_{i},{j}' for j in range(n)] for i in range(n)]

# minimize the number of bins used
objective.add_linear_from(((v, 1) for v in y_labels), default_vartype='BINARY')
cqm.set_objective(objective)

# each item can only go in one bin
for i in range(n):
lhs.add_linear_from(((v, 1) for v in x_labels[i]), default_vartype='BINARY')

# each bin has a capacity that must be respected
for j in range(n):
lhs.add_linear_from(((x_labels[i][j], weights[i]) for i in range(n)), default_vartype='BINARY')

return cqm


This change significantly reduces runtime.

In : %timeit bin_packing(weights)
95.5 ms ± 2.87 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)


By default, the add_constraint() method creates a copy of the objects you give it to avert mutation of objects that might be used elsewhere in your code. If these objects are used solely for the construction of constraints, as in this case, you can safely skip the copying.

import typing

import dimod

"""Generate a bin packing problem as a constrained quadratic model."""

n = len(weights)

# y_j indicates that bin j is used
y_labels = [f'y_{j}' for j in range(n)]

# x_i,j indicates that item i is put in bin j
x_labels = [[f'x_{i},{j}' for j in range(n)] for i in range(n)]

# we wish to minimize the number of bins used
objective.add_linear_from(((v, 1) for v in y_labels), default_vartype='BINARY')
cqm.set_objective(objective)

# each item can only go in one bin
for i in range(n):
lhs.add_linear_from(((v, 1) for v in x_labels[i]), default_vartype='BINARY')

# each bin has a capacity that must be respected
for j in range(n):

In : %timeit bin_packing(weights)