22. Introducción.#
En este notebook, vamos a mostrar un ejemplo sobre cómo mejorar el rendimiento de la programación hecha con Ocean a la hora de resolver un problema de programación lineal. Al mismo tiempo vamos a ver una serie de pautas que el lector puede seguir a la hora de resolver otro enfoque del problema de la mochila que ya se ha visto en otros ejemplos.
Para ello vamos a resolver el típico problema de tipo bin packing que básicamente consiste en distribuir de forma óptima una serie de paquetes, con unos determinados pesos en unos contenedores con una limitación de capacidad dada. La referencia a este problema se puede ver en https://en.wikipedia.org/wiki/Bin_packing_problem.
Inicialmente lo resolvemos como se indica en este enlace: https://docs.ocean.dwavesys.com/en/stable/examples/hybrid_cqm_binpacking.html.
La función objetivo en este caso va a consistir en minimizar el número de contenedores (bins) utilizados. Puesto que un contenedor puede ser utilizado o no, podemos denotar esa situación mediante una variable de tipo binario, por lo tanto la variable bin_used_<j> indicará si el contenedor \(b_j\) va a ser utilizado o no. Vamos a definir inicialmente una serie de valores para este problema
import numpy as np
num_items = 15 # Es el número de items para cargar que vamos a utilizar
item_weight_range = [3, 7] # Rango de pesos
weights = list(np.random.randint(*item_weight_range, num_items))
bin_capacity = int(10 * np.mean(weights)) # Capacidad de los bins
print("Problem: pack a total weight of {} into bins of capacity {}.".format(
sum(weights), bin_capacity))
Problem: pack a total weight of 73 into bins of capacity 48.
# Veamos los pesos que obtenemos
weights
[6, 6, 3, 3, 6, 6, 4, 5, 4, 6, 6, 5, 3, 4, 6]
Como estamos en presencia de un problema de optimización lineal con restricciones, utilizamos un modelo de tipo ConstrainedQuadraticModel conocido también como CQM
from dimod import ConstrainedQuadraticModel
cqm = ConstrainedQuadraticModel()
23. Función objetivo.#
Tal y como hemos explicado anteriormente, vamos a definir la variable \(b_j\) de tipo binario e indicativo si se utiliza o no el contenedor j de la siguiente manera
from dimod import Binary
bin_used = [Binary(f'bin_used_{j}') for j in range(num_items)]
Veamos cual es el contenido de las variables que acabamos de generar
bin_used
[BinaryQuadraticModel({'bin_used_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'bin_used_14': 1.0}, {}, 0.0, 'BINARY')]
La función objetivo tendrá el siguiente formato:
\[min(\sum {b_j}) \]
Es decir:
cqm.set_objective(sum(bin_used))
Como hemos visto anteriormente las variables generadas son del tipo BinaryQuadraticModel, pero veamos qué ocurre si a estas variables les multiplicamos por una determinada cantidad
4.5*bin_used[0]
BinaryQuadraticModel({'bin_used_0': 4.5}, {}, 0.0, 'BINARY')
o incluso si multiplicamos dos de esta variables
4.5*bin_used[0]*bin_used[1]
BinaryQuadraticModel({'bin_used_0': 0.0, 'bin_used_1': 0.0}, {('bin_used_1', 'bin_used_0'): 4.5}, 0.0, 'BINARY')
Si multiplicamos tres variables tendriamos un error porque no sería un término cuadrático
4.5*bin_used[0]*bin_used[1]*bin_used[3]
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[9], line 1
----> 1 4.5*bin_used[0]*bin_used[1]*bin_used[3]
File c:\users\francisco\desktop\dwaveocean\ocean\lib\site-packages\dimod\binary\binary_quadratic_model.py:345, in BinaryQuadraticModel.__mul__(self, other)
343 if isinstance(other, BinaryQuadraticModel):
344 if not (self.is_linear() and other.is_linear()):
--> 345 raise TypeError(
346 "cannot multiply BQMs with interactions")
347 elif other.num_variables and other.vartype != self.vartype:
348 # promote self
349 return QuadraticModel.from_bqm(self) * other
TypeError: cannot multiply BQMs with interactions
24. Restricciones.#
A continuación procedemos a implementar las restricciones que deben tenerse en cuenta en este modelo.
En primer lugar se debe cargar cada item en un sólo bin o contenedor. Entonces si designamos por \(x_{i,j}\) la variable binaria relativa a que el objeto o item i va en el contenedor j, entonces para cada i la suma en j de estas variables debe ser 1. Es decir:
\[\sum_{j}{x_{i,j}}=1 \]
Definamos estas variables \(x_{i,j}\)
item_in_bin = [[Binary(f'item_{i}_in_bin_{j}') for j in range(num_items)]
for i in range(num_items)]
item_in_bin
[[BinaryQuadraticModel({'item_0_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_0_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_1_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_1_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_2_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_2_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_3_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_3_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_4_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_4_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_5_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_5_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_6_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_6_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_7_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_7_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_8_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_8_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_9_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_9_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_10_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_10_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_11_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_11_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_12_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_12_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_13_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_13_in_bin_14': 1.0}, {}, 0.0, 'BINARY')],
[BinaryQuadraticModel({'item_14_in_bin_0': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_1': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_2': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_3': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_4': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_5': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_6': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_7': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_8': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_9': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_10': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_11': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_12': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_13': 1.0}, {}, 0.0, 'BINARY'),
BinaryQuadraticModel({'item_14_in_bin_14': 1.0}, {}, 0.0, 'BINARY')]]
Ahora añadimos la restricción anterior para cada uno de los i_es
for i in range(num_items):
one_bin_per_item = cqm.add_constraint(sum(item_in_bin[i]) == 1, label=f'item_placing_{i}')
Otra restricción a tener en cuenta es que la capacidad de cada contenedor o bin es limitada y entonces para cada j se tiene que se debe cumplir:
\[\sum_{i}{x_{i,j}*{w_i}}<=C \]
es decir:
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}')
len(cqm.variables)
240
25. Resolución del problema.#
from dwave.system import LeapHybridCQMSampler
sampler = LeapHybridCQMSampler()
sampleset = sampler.sample_cqm(cqm,
time_limit=180,
label="SDK Examples - Bin Packing")
# Nos quedamos con las soluciones factibles
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)))
127 feasible solutions of 131.
best
Sample(sample={'bin_used_0': 0.0, 'bin_used_1': 0.0, 'bin_used_10': 0.0, 'bin_used_11': 1.0, 'bin_used_12': 0.0, 'bin_used_13': 0.0, 'bin_used_14': 0.0, 'bin_used_2': 0.0, 'bin_used_3': 0.0, 'bin_used_4': 0.0, 'bin_used_5': 1.0, 'bin_used_6': 0.0, 'bin_used_7': 0.0, 'bin_used_8': 0.0, 'bin_used_9': 0.0, 'item_0_in_bin_0': 0.0, 'item_0_in_bin_1': 0.0, 'item_0_in_bin_10': 0.0, 'item_0_in_bin_11': 1.0, 'item_0_in_bin_12': 0.0, 'item_0_in_bin_13': 0.0, 'item_0_in_bin_14': 0.0, 'item_0_in_bin_2': 0.0, 'item_0_in_bin_3': 0.0, 'item_0_in_bin_4': 0.0, 'item_0_in_bin_5': 0.0, 'item_0_in_bin_6': 0.0, 'item_0_in_bin_7': 0.0, 'item_0_in_bin_8': 0.0, 'item_0_in_bin_9': 0.0, 'item_10_in_bin_0': 0.0, 'item_10_in_bin_1': 0.0, 'item_10_in_bin_10': 0.0, 'item_10_in_bin_11': 0.0, 'item_10_in_bin_12': 0.0, 'item_10_in_bin_13': 0.0, 'item_10_in_bin_14': 0.0, 'item_10_in_bin_2': 0.0, 'item_10_in_bin_3': 0.0, 'item_10_in_bin_4': 0.0, 'item_10_in_bin_5': 1.0, 'item_10_in_bin_6': 0.0, 'item_10_in_bin_7': 0.0, 'item_10_in_bin_8': 0.0, 'item_10_in_bin_9': 0.0, 'item_11_in_bin_0': 0.0, 'item_11_in_bin_1': 0.0, 'item_11_in_bin_10': 0.0, 'item_11_in_bin_11': 0.0, 'item_11_in_bin_12': 0.0, 'item_11_in_bin_13': 0.0, 'item_11_in_bin_14': 0.0, 'item_11_in_bin_2': 0.0, 'item_11_in_bin_3': 0.0, 'item_11_in_bin_4': 0.0, 'item_11_in_bin_5': 1.0, 'item_11_in_bin_6': 0.0, 'item_11_in_bin_7': 0.0, 'item_11_in_bin_8': 0.0, 'item_11_in_bin_9': 0.0, 'item_12_in_bin_0': 0.0, 'item_12_in_bin_1': 0.0, 'item_12_in_bin_10': 0.0, 'item_12_in_bin_11': 0.0, 'item_12_in_bin_12': 0.0, 'item_12_in_bin_13': 0.0, 'item_12_in_bin_14': 0.0, 'item_12_in_bin_2': 0.0, 'item_12_in_bin_3': 0.0, 'item_12_in_bin_4': 0.0, 'item_12_in_bin_5': 1.0, 'item_12_in_bin_6': 0.0, 'item_12_in_bin_7': 0.0, 'item_12_in_bin_8': 0.0, 'item_12_in_bin_9': 0.0, 'item_13_in_bin_0': 0.0, 'item_13_in_bin_1': 0.0, 'item_13_in_bin_10': 0.0, 'item_13_in_bin_11': 1.0, 'item_13_in_bin_12': 0.0, 'item_13_in_bin_13': 0.0, 'item_13_in_bin_14': 0.0, 'item_13_in_bin_2': 0.0, 'item_13_in_bin_3': 0.0, 'item_13_in_bin_4': 0.0, 'item_13_in_bin_5': 0.0, 'item_13_in_bin_6': 0.0, 'item_13_in_bin_7': 0.0, 'item_13_in_bin_8': 0.0, 'item_13_in_bin_9': 0.0, 'item_14_in_bin_0': 0.0, 'item_14_in_bin_1': 0.0, 'item_14_in_bin_10': 0.0, 'item_14_in_bin_11': 1.0, 'item_14_in_bin_12': 0.0, 'item_14_in_bin_13': 0.0, 'item_14_in_bin_14': 0.0, 'item_14_in_bin_2': 0.0, 'item_14_in_bin_3': 0.0, 'item_14_in_bin_4': 0.0, 'item_14_in_bin_5': 0.0, 'item_14_in_bin_6': 0.0, 'item_14_in_bin_7': 0.0, 'item_14_in_bin_8': 0.0, 'item_14_in_bin_9': 0.0, 'item_1_in_bin_0': 0.0, 'item_1_in_bin_1': 0.0, 'item_1_in_bin_10': 0.0, 'item_1_in_bin_11': 0.0, 'item_1_in_bin_12': 0.0, 'item_1_in_bin_13': 0.0, 'item_1_in_bin_14': 0.0, 'item_1_in_bin_2': 0.0, 'item_1_in_bin_3': 0.0, 'item_1_in_bin_4': 0.0, 'item_1_in_bin_5': 1.0, 'item_1_in_bin_6': 0.0, 'item_1_in_bin_7': 0.0, 'item_1_in_bin_8': 0.0, 'item_1_in_bin_9': 0.0, 'item_2_in_bin_0': 0.0, 'item_2_in_bin_1': 0.0, 'item_2_in_bin_10': 0.0, 'item_2_in_bin_11': 1.0, 'item_2_in_bin_12': 0.0, 'item_2_in_bin_13': 0.0, 'item_2_in_bin_14': 0.0, 'item_2_in_bin_2': 0.0, 'item_2_in_bin_3': 0.0, 'item_2_in_bin_4': 0.0, 'item_2_in_bin_5': 0.0, 'item_2_in_bin_6': 0.0, 'item_2_in_bin_7': 0.0, 'item_2_in_bin_8': 0.0, 'item_2_in_bin_9': 0.0, 'item_3_in_bin_0': 0.0, 'item_3_in_bin_1': 0.0, 'item_3_in_bin_10': 0.0, 'item_3_in_bin_11': 1.0, 'item_3_in_bin_12': 0.0, 'item_3_in_bin_13': 0.0, 'item_3_in_bin_14': 0.0, 'item_3_in_bin_2': 0.0, 'item_3_in_bin_3': 0.0, 'item_3_in_bin_4': 0.0, 'item_3_in_bin_5': 0.0, 'item_3_in_bin_6': 0.0, 'item_3_in_bin_7': 0.0, 'item_3_in_bin_8': 0.0, 'item_3_in_bin_9': 0.0, 'item_4_in_bin_0': 0.0, 'item_4_in_bin_1': 0.0, 'item_4_in_bin_10': 0.0, 'item_4_in_bin_11': 0.0, 'item_4_in_bin_12': 0.0, 'item_4_in_bin_13': 0.0, 'item_4_in_bin_14': 0.0, 'item_4_in_bin_2': 0.0, 'item_4_in_bin_3': 0.0, 'item_4_in_bin_4': 0.0, 'item_4_in_bin_5': 1.0, 'item_4_in_bin_6': 0.0, 'item_4_in_bin_7': 0.0, 'item_4_in_bin_8': 0.0, 'item_4_in_bin_9': 0.0, 'item_5_in_bin_0': 0.0, 'item_5_in_bin_1': 0.0, 'item_5_in_bin_10': 0.0, 'item_5_in_bin_11': 0.0, 'item_5_in_bin_12': 0.0, 'item_5_in_bin_13': 0.0, 'item_5_in_bin_14': 0.0, 'item_5_in_bin_2': 0.0, 'item_5_in_bin_3': 0.0, 'item_5_in_bin_4': 0.0, 'item_5_in_bin_5': 1.0, 'item_5_in_bin_6': 0.0, 'item_5_in_bin_7': 0.0, 'item_5_in_bin_8': 0.0, 'item_5_in_bin_9': 0.0, 'item_6_in_bin_0': 0.0, 'item_6_in_bin_1': 0.0, 'item_6_in_bin_10': 0.0, 'item_6_in_bin_11': 0.0, 'item_6_in_bin_12': 0.0, 'item_6_in_bin_13': 0.0, 'item_6_in_bin_14': 0.0, 'item_6_in_bin_2': 0.0, 'item_6_in_bin_3': 0.0, 'item_6_in_bin_4': 0.0, 'item_6_in_bin_5': 1.0, 'item_6_in_bin_6': 0.0, 'item_6_in_bin_7': 0.0, 'item_6_in_bin_8': 0.0, 'item_6_in_bin_9': 0.0, 'item_7_in_bin_0': 0.0, 'item_7_in_bin_1': 0.0, 'item_7_in_bin_10': 0.0, 'item_7_in_bin_11': 1.0, 'item_7_in_bin_12': 0.0, 'item_7_in_bin_13': 0.0, 'item_7_in_bin_14': 0.0, 'item_7_in_bin_2': 0.0, 'item_7_in_bin_3': 0.0, 'item_7_in_bin_4': 0.0, 'item_7_in_bin_5': 0.0, 'item_7_in_bin_6': 0.0, 'item_7_in_bin_7': 0.0, 'item_7_in_bin_8': 0.0, 'item_7_in_bin_9': 0.0, 'item_8_in_bin_0': 0.0, 'item_8_in_bin_1': 0.0, 'item_8_in_bin_10': 0.0, 'item_8_in_bin_11': 0.0, 'item_8_in_bin_12': 0.0, 'item_8_in_bin_13': 0.0, 'item_8_in_bin_14': 0.0, 'item_8_in_bin_2': 0.0, 'item_8_in_bin_3': 0.0, 'item_8_in_bin_4': 0.0, 'item_8_in_bin_5': 1.0, 'item_8_in_bin_6': 0.0, 'item_8_in_bin_7': 0.0, 'item_8_in_bin_8': 0.0, 'item_8_in_bin_9': 0.0, 'item_9_in_bin_0': 0.0, 'item_9_in_bin_1': 0.0, 'item_9_in_bin_10': 0.0, 'item_9_in_bin_11': 1.0, 'item_9_in_bin_12': 0.0, 'item_9_in_bin_13': 0.0, 'item_9_in_bin_14': 0.0, 'item_9_in_bin_2': 0.0, 'item_9_in_bin_3': 0.0, 'item_9_in_bin_4': 0.0, 'item_9_in_bin_5': 0.0, 'item_9_in_bin_6': 0.0, 'item_9_in_bin_7': 0.0, 'item_9_in_bin_8': 0.0, 'item_9_in_bin_9': 0.0}, energy=2.0, num_occurrences=1, is_satisfied=array([ True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True,
True, True, True]), is_feasible=True)
best.sample.items()
dict_items([('bin_used_0', 0.0), ('bin_used_1', 0.0), ('bin_used_10', 0.0), ('bin_used_11', 1.0), ('bin_used_12', 0.0), ('bin_used_13', 0.0), ('bin_used_14', 0.0), ('bin_used_2', 0.0), ('bin_used_3', 0.0), ('bin_used_4', 0.0), ('bin_used_5', 1.0), ('bin_used_6', 0.0), ('bin_used_7', 0.0), ('bin_used_8', 0.0), ('bin_used_9', 0.0), ('item_0_in_bin_0', 0.0), ('item_0_in_bin_1', 0.0), ('item_0_in_bin_10', 0.0), ('item_0_in_bin_11', 1.0), ('item_0_in_bin_12', 0.0), ('item_0_in_bin_13', 0.0), ('item_0_in_bin_14', 0.0), ('item_0_in_bin_2', 0.0), ('item_0_in_bin_3', 0.0), ('item_0_in_bin_4', 0.0), ('item_0_in_bin_5', 0.0), ('item_0_in_bin_6', 0.0), ('item_0_in_bin_7', 0.0), ('item_0_in_bin_8', 0.0), ('item_0_in_bin_9', 0.0), ('item_10_in_bin_0', 0.0), ('item_10_in_bin_1', 0.0), ('item_10_in_bin_10', 0.0), ('item_10_in_bin_11', 0.0), ('item_10_in_bin_12', 0.0), ('item_10_in_bin_13', 0.0), ('item_10_in_bin_14', 0.0), ('item_10_in_bin_2', 0.0), ('item_10_in_bin_3', 0.0), ('item_10_in_bin_4', 0.0), ('item_10_in_bin_5', 1.0), ('item_10_in_bin_6', 0.0), ('item_10_in_bin_7', 0.0), ('item_10_in_bin_8', 0.0), ('item_10_in_bin_9', 0.0), ('item_11_in_bin_0', 0.0), ('item_11_in_bin_1', 0.0), ('item_11_in_bin_10', 0.0), ('item_11_in_bin_11', 0.0), ('item_11_in_bin_12', 0.0), ('item_11_in_bin_13', 0.0), ('item_11_in_bin_14', 0.0), ('item_11_in_bin_2', 0.0), ('item_11_in_bin_3', 0.0), ('item_11_in_bin_4', 0.0), ('item_11_in_bin_5', 1.0), ('item_11_in_bin_6', 0.0), ('item_11_in_bin_7', 0.0), ('item_11_in_bin_8', 0.0), ('item_11_in_bin_9', 0.0), ('item_12_in_bin_0', 0.0), ('item_12_in_bin_1', 0.0), ('item_12_in_bin_10', 0.0), ('item_12_in_bin_11', 0.0), ('item_12_in_bin_12', 0.0), ('item_12_in_bin_13', 0.0), ('item_12_in_bin_14', 0.0), ('item_12_in_bin_2', 0.0), ('item_12_in_bin_3', 0.0), ('item_12_in_bin_4', 0.0), ('item_12_in_bin_5', 1.0), ('item_12_in_bin_6', 0.0), ('item_12_in_bin_7', 0.0), ('item_12_in_bin_8', 0.0), ('item_12_in_bin_9', 0.0), ('item_13_in_bin_0', 0.0), ('item_13_in_bin_1', 0.0), ('item_13_in_bin_10', 0.0), ('item_13_in_bin_11', 1.0), ('item_13_in_bin_12', 0.0), ('item_13_in_bin_13', 0.0), ('item_13_in_bin_14', 0.0), ('item_13_in_bin_2', 0.0), ('item_13_in_bin_3', 0.0), ('item_13_in_bin_4', 0.0), ('item_13_in_bin_5', 0.0), ('item_13_in_bin_6', 0.0), ('item_13_in_bin_7', 0.0), ('item_13_in_bin_8', 0.0), ('item_13_in_bin_9', 0.0), ('item_14_in_bin_0', 0.0), ('item_14_in_bin_1', 0.0), ('item_14_in_bin_10', 0.0), ('item_14_in_bin_11', 1.0), ('item_14_in_bin_12', 0.0), ('item_14_in_bin_13', 0.0), ('item_14_in_bin_14', 0.0), ('item_14_in_bin_2', 0.0), ('item_14_in_bin_3', 0.0), ('item_14_in_bin_4', 0.0), ('item_14_in_bin_5', 0.0), ('item_14_in_bin_6', 0.0), ('item_14_in_bin_7', 0.0), ('item_14_in_bin_8', 0.0), ('item_14_in_bin_9', 0.0), ('item_1_in_bin_0', 0.0), ('item_1_in_bin_1', 0.0), ('item_1_in_bin_10', 0.0), ('item_1_in_bin_11', 0.0), ('item_1_in_bin_12', 0.0), ('item_1_in_bin_13', 0.0), ('item_1_in_bin_14', 0.0), ('item_1_in_bin_2', 0.0), ('item_1_in_bin_3', 0.0), ('item_1_in_bin_4', 0.0), ('item_1_in_bin_5', 1.0), ('item_1_in_bin_6', 0.0), ('item_1_in_bin_7', 0.0), ('item_1_in_bin_8', 0.0), ('item_1_in_bin_9', 0.0), ('item_2_in_bin_0', 0.0), ('item_2_in_bin_1', 0.0), ('item_2_in_bin_10', 0.0), ('item_2_in_bin_11', 1.0), ('item_2_in_bin_12', 0.0), ('item_2_in_bin_13', 0.0), ('item_2_in_bin_14', 0.0), ('item_2_in_bin_2', 0.0), ('item_2_in_bin_3', 0.0), ('item_2_in_bin_4', 0.0), ('item_2_in_bin_5', 0.0), ('item_2_in_bin_6', 0.0), ('item_2_in_bin_7', 0.0), ('item_2_in_bin_8', 0.0), ('item_2_in_bin_9', 0.0), ('item_3_in_bin_0', 0.0), ('item_3_in_bin_1', 0.0), ('item_3_in_bin_10', 0.0), ('item_3_in_bin_11', 1.0), ('item_3_in_bin_12', 0.0), ('item_3_in_bin_13', 0.0), ('item_3_in_bin_14', 0.0), ('item_3_in_bin_2', 0.0), ('item_3_in_bin_3', 0.0), ('item_3_in_bin_4', 0.0), ('item_3_in_bin_5', 0.0), ('item_3_in_bin_6', 0.0), ('item_3_in_bin_7', 0.0), ('item_3_in_bin_8', 0.0), ('item_3_in_bin_9', 0.0), ('item_4_in_bin_0', 0.0), ('item_4_in_bin_1', 0.0), ('item_4_in_bin_10', 0.0), ('item_4_in_bin_11', 0.0), ('item_4_in_bin_12', 0.0), ('item_4_in_bin_13', 0.0), ('item_4_in_bin_14', 0.0), ('item_4_in_bin_2', 0.0), ('item_4_in_bin_3', 0.0), ('item_4_in_bin_4', 0.0), ('item_4_in_bin_5', 1.0), ('item_4_in_bin_6', 0.0), ('item_4_in_bin_7', 0.0), ('item_4_in_bin_8', 0.0), ('item_4_in_bin_9', 0.0), ('item_5_in_bin_0', 0.0), ('item_5_in_bin_1', 0.0), ('item_5_in_bin_10', 0.0), ('item_5_in_bin_11', 0.0), ('item_5_in_bin_12', 0.0), ('item_5_in_bin_13', 0.0), ('item_5_in_bin_14', 0.0), ('item_5_in_bin_2', 0.0), ('item_5_in_bin_3', 0.0), ('item_5_in_bin_4', 0.0), ('item_5_in_bin_5', 1.0), ('item_5_in_bin_6', 0.0), ('item_5_in_bin_7', 0.0), ('item_5_in_bin_8', 0.0), ('item_5_in_bin_9', 0.0), ('item_6_in_bin_0', 0.0), ('item_6_in_bin_1', 0.0), ('item_6_in_bin_10', 0.0), ('item_6_in_bin_11', 0.0), ('item_6_in_bin_12', 0.0), ('item_6_in_bin_13', 0.0), ('item_6_in_bin_14', 0.0), ('item_6_in_bin_2', 0.0), ('item_6_in_bin_3', 0.0), ('item_6_in_bin_4', 0.0), ('item_6_in_bin_5', 1.0), ('item_6_in_bin_6', 0.0), ('item_6_in_bin_7', 0.0), ('item_6_in_bin_8', 0.0), ('item_6_in_bin_9', 0.0), ('item_7_in_bin_0', 0.0), ('item_7_in_bin_1', 0.0), ('item_7_in_bin_10', 0.0), ('item_7_in_bin_11', 1.0), ('item_7_in_bin_12', 0.0), ('item_7_in_bin_13', 0.0), ('item_7_in_bin_14', 0.0), ('item_7_in_bin_2', 0.0), ('item_7_in_bin_3', 0.0), ('item_7_in_bin_4', 0.0), ('item_7_in_bin_5', 0.0), ('item_7_in_bin_6', 0.0), ('item_7_in_bin_7', 0.0), ('item_7_in_bin_8', 0.0), ('item_7_in_bin_9', 0.0), ('item_8_in_bin_0', 0.0), ('item_8_in_bin_1', 0.0), ('item_8_in_bin_10', 0.0), ('item_8_in_bin_11', 0.0), ('item_8_in_bin_12', 0.0), ('item_8_in_bin_13', 0.0), ('item_8_in_bin_14', 0.0), ('item_8_in_bin_2', 0.0), ('item_8_in_bin_3', 0.0), ('item_8_in_bin_4', 0.0), ('item_8_in_bin_5', 1.0), ('item_8_in_bin_6', 0.0), ('item_8_in_bin_7', 0.0), ('item_8_in_bin_8', 0.0), ('item_8_in_bin_9', 0.0), ('item_9_in_bin_0', 0.0), ('item_9_in_bin_1', 0.0), ('item_9_in_bin_10', 0.0), ('item_9_in_bin_11', 1.0), ('item_9_in_bin_12', 0.0), ('item_9_in_bin_13', 0.0), ('item_9_in_bin_14', 0.0), ('item_9_in_bin_2', 0.0), ('item_9_in_bin_3', 0.0), ('item_9_in_bin_4', 0.0), ('item_9_in_bin_5', 0.0), ('item_9_in_bin_6', 0.0), ('item_9_in_bin_7', 0.0), ('item_9_in_bin_8', 0.0), ('item_9_in_bin_9', 0.0)])
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.
def get_indices(name):
return [int(digs) for digs in name.split('_') if digs.isdigit()]
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 {} tiene pesos {} que suman un total de {}.".format(b, w, sum(w)))
Bin 11 tiene pesos [4, 6, 4, 5, 3, 4, 4] que suman un total de 30.
Bin 5 tiene pesos [4, 6, 6, 3, 4, 6, 6, 6] que suman un total de 41.
26. Optimizando Código#
En este apartado vamos a ver cómo podríamos mejorar el código anterior para obtener una mejora importante en el rendimiento de esas instrucciones.
Por simplicidad, pero sin pérdida de generalidad, vamos a suponer que cada contenedor o bin,tiene una capacidad de 1. Un problema de estas características con n items, se convierte en un CQM de n*(n+1) variables binarias. Comenzamos definiendo el número de items y los pesos
import numpy as np
num_items = 100 # results in 10100 binary variables
weights = np.random.default_rng(42).random(num_items)
Entonces la primera implementación de problema, sería la siguiente:
import typing
import dimod
def bin_packing(weights: typing.Sequence[float]) -> dimod.ConstrainedQuadraticModel:
"""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)]
cqm = dimod.ConstrainedQuadraticModel()
# minimize the number of bins used
cqm.set_objective(sum(y))
# each item can go in only one bin
for i in range(n):
cqm.add_constraint(sum(x[i]) == 1, label=f'item_placing_{i}')
# 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
%timeit bin_packing(weights)
793 ms ± 30.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Lo anterior es la implementación con la función sum(), que suele ser más lenta que si se utiliza quicksum()
import typing
import dimod
def bin_packing(weights: typing.Sequence[float]) -> dimod.ConstrainedQuadraticModel:
"""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)]
cqm = dimod.ConstrainedQuadraticModel()
# 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):
cqm.add_constraint(dimod.quicksum(x[i]) == 1, label=f'item_placing_{i}')
# 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
%timeit bin_packing(weights)
552 ms ± 6.76 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Puede conseguir una mejora aún mayor si omite por completo la construcción simbólica y trabaja directamente con etiquetas de variables y un único objeto BQM.
El siguiente pequeño ejemplo demuestra la diferencia de rendimiento
import dimod
def make_bqm_symbolic(num_variables: int) -> dimod.BinaryQuadraticModel:
return dimod.quicksum(2*dimod.Binary(v) for v in range(num_variables))
def make_bqm_labels(num_variables: int) -> dimod.BinaryQuadraticModel:
bqm = dimod.BinaryQuadraticModel('BINARY')
bqm.add_linear_from((v, 2) for v in range(num_variables))
return bqm
%timeit make_bqm_symbolic(1000)
31.9 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit make_bqm_labels(1000)
390 µs ± 2.03 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Aplicamos esta misma construcción de modelo al ejemplo de binpacking:
import typing
import dimod
def bin_packing(weights: typing.Sequence[float]) -> dimod.ConstrainedQuadraticModel:
"""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)]
cqm = dimod.ConstrainedQuadraticModel()
# minimize the number of bins used
objective = dimod.QuadraticModel()
objective.add_linear_from(((v, 1) for v in y_labels), default_vartype='BINARY')
#objective.add_linear(((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 = dimod.QuadraticModel()
lhs.add_linear_from(((v, 1) for v in x_labels[i]), default_vartype='BINARY')
#lhs.add_linear(((v, 1) for v in x_labels[i]), default_vartype='BINARY')
cqm.add_constraint_from_model(lhs, rhs=1, sense='==', label=f'item_placing_{i}')
# each bin has a capacity that must be respected
for j in range(n):
lhs = dimod.QuadraticModel()
lhs.add_linear_from(((x_labels[i][j], weights[i]) for i in range(n)), default_vartype='BINARY')
#lhs.add_linear(((x_labels[i][j], weights[i]) for i in range(n)), default_vartype='BINARY')
lhs.add_linear(y_labels[j], -1, default_vartype='BINARY')
cqm.add_constraint_from_model(lhs, rhs=0, sense='<=', label=f'capacity_bin_{j}')
return cqm
%timeit bin_packing(weights)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
~\AppData\Local\Temp\ipykernel_15812\14838865.py in <module>
----> 1 get_ipython().run_line_magic('timeit', 'bin_packing(weights)')
d:\mistrabajos\dwaveocean\ocean\lib\site-packages\IPython\core\interactiveshell.py in run_line_magic(self, magic_name, line, _stack_depth)
2362 kwargs['local_ns'] = self.get_local_scope(stack_depth)
2363 with self.builtin_trap:
-> 2364 result = fn(*args, **kwargs)
2365 return result
2366
d:\mistrabajos\dwaveocean\ocean\lib\site-packages\decorator.py in fun(*args, **kw)
230 if not kwsyntax:
231 args, kw = fix(args, kw, sig)
--> 232 return caller(func, *(extras + args), **kw)
233 fun.__name__ = func.__name__
234 fun.__doc__ = func.__doc__
d:\mistrabajos\dwaveocean\ocean\lib\site-packages\IPython\core\magic.py in <lambda>(f, *a, **k)
185 # but it's overkill for just that one bit of state.
186 def magic_deco(arg):
--> 187 call = lambda f, *a, **k: f(*a, **k)
188
189 if callable(arg):
d:\mistrabajos\dwaveocean\ocean\lib\site-packages\IPython\core\magics\execution.py in timeit(self, line, cell, local_ns)
1178 for index in range(0, 10):
1179 number = 10 ** index
-> 1180 time_number = timer.timeit(number)
1181 if time_number >= 0.2:
1182 break
d:\mistrabajos\dwaveocean\ocean\lib\site-packages\IPython\core\magics\execution.py in timeit(self, number)
167 gc.disable()
168 try:
--> 169 timing = self.inner(it, self.timer)
170 finally:
171 if gcold:
<magic-timeit> in inner(_it, _timer)
~\AppData\Local\Temp\ipykernel_15812\1737132310.py in bin_packing(weights)
19 # minimize the number of bins used
20 objective = dimod.QuadraticModel()
---> 21 objective.add_linear_from(((v, 1) for v in y_labels), default_vartype='BINARY')
22 #objective.add_linear(((v, 1) for v in y_labels), default_vartype='BINARY')
23 cqm.set_objective(objective)
TypeError: add_linear_from() got an unexpected keyword argument 'default_vartype'
Como