Partición de un conjunto de números con DQM.

16. Partición de un conjunto de números con DQM.#

En otro apartado ya se ha visto cómo se resuelve este problema utilizando la clase BQM. Ahora vamos a ver otro procedimiento utilizando para ello la clase DQM.

16.1. Generalización para hacer una partición de números.#

El objetivo es dividir un conjunto de números en varios conjuntos de igual tamaño (que tengan la misma suma). Una variable de decisión que sirve a este propósito es una variable binaria $x_{i,j}$ donde el subíndice i corresponde al número seleccionado y j al conjunto asginado, y que vale 1 si el número i es asignado a la clase j. Entonces, esto sería equivalente a crear una variable $x_i$ que toma valores enteros y que vale $x_i=j$ si el elemneto i es asignado a la clase j.

NOTA: Las dos variables, la binaria ($x_{i,j}=1$) y la discreta ($x_i = j$) pueden utilizarse indistintamente. Para la mayoría de las expresiones matemáticas es más conveniente utilizar la forma binaria.

Procedemos a resolver el problema de crear tres grupos de números, de manera que la suma sea igual en cada grupo.

from dimod import DiscreteQuadraticModel

values = [7, 2, 3, 1, 8, 3, 1, 2, 9]
dqm = DiscreteQuadraticModel()
n = len(values)
m = 3 # num_partitions

# Creamos las variables discretas
x = {i: dqm.add_variable(m) for i in range(n)}

16.2. No objective, only constraints#

En este tipo de problemas no tenemos función objetivo, sólo restricciones

Para cada par de particiones, debemos asegurar que la suma de sus elementos es la misma.

\[ \begin{align}\begin{aligned} \sum_i v_i x_{ij} = \sum_i v_i x_{ik} $$ for all $j$ and $k$\\O lo que es lo mismo (forma que debemos utilizar en este tipo de modelos):\\$$ \sum_i v_i x_{ij} - \sum_i v_i x_{ik} = 0\end{aligned}\end{align} \]

Creamos esta condición para que sea entendida por Ocean SDK de la siguiente manera

from itertools import combinations
for k, l in combinations(range(m), r=2):
    dqm.add_linear_equality_constraint(
    [(x[i], k, values[i]) for i in range(n)] + [(x[i], l, -values[i]) for i in range(n)],
    constant=0,
    lagrange_multiplier=10)

En un problema de este tipo, utilizando BQM se debería añadir una restricción para asegurar de que cada número pertenece a un sólo conjunto. Esta restricción sería la siguiente.

\[\sum_jx_{ij}=1\quad \forall i\]

Pero utilizando un modelo de tipo BQM no es necesario añadir esta restricción

Resolvemos el problema utilizando el solver ExactDQMSolver

from dimod import ExactDQMSolver

res = ExactDQMSolver().sample_dqm(dqm).truncate(5)
print(res)

1 2 3 4 5 6 7 8 energy num_oc.
0 0 2 1 2 0 2 1 1    0.0       1
2 1 0 1 0 2 0 2 1    0.0       1
0 0 1 1 1 0 2 2 2    0.0       1
0 1 2 1 2 0 2 0 1    0.0       1
2 2 0 1 0 2 0 1 1    0.0       1
['INTEGER', 5 rows, 5 samples, 9 variables]

16.3. Resultado#

Pongamos el resultado de una forma más estética y comprobemos que es corercto

sample = res.first.sample

print(sample)
print(sum(values))
for k in range(m):
    set1 = [values[i] for i in x if sample[x[i]] == k]
    print(sum(set1), set1)

{0: 0, 1: 0, 2: 2, 3: 1, 4: 2, 5: 0, 6: 2, 7: 1, 8: 1}
36
12 [7, 2, 3]
12 [1, 2, 9]
12 [3, 8, 1]

Ahora volvemos a resolver el problema utilizando el solver de Leap’s hybrid solver.

from dwave.system import LeapHybridDQMSampler

res = LeapHybridDQMSampler().sample_dqm(dqm).truncate(5)
print(res)

1 2 3 4 5 6 7 8 energy num_oc.
1 1 1 0 2 2 2 0 0    0.0       1
2 2 0 2 1 1 1 2 0    0.0       1
1 1 1 2 0 0 0 2 2    0.0       1
1 1 1 0 0 0 2 2 2    0.0       1
2 2 0 0 0 2 1 1 1    0.0       1
['INTEGER', 5 rows, 5 samples, 9 variables]

sample = res.first.sample

print(sample)
print(sum(values))
for k in range(m):
    set1 = [values[i] for i in x if sample[x[i]] == k]
    print(sum(set1), set1)

{0: 1, 1: 1, 2: 1, 3: 0, 4: 2, 5: 2, 6: 2, 7: 0, 8: 0}
36
12 [1, 2, 9]
12 [7, 2, 3]
12 [8, 3, 1]

16.4. Ejercicio.#

Se deja para el lector ampliar la lista de núemros anterior y hacer un ejercicio similar. En concreto se propone lo siguiente:

Crear una lista de 100 números enteros (se puede hacer una generación aleatoria de estos números)
Hacer una partición similar a la de este apartado, pero creando 10 grupos
Resolver este problema utilizando LeapHybridDQMSampler