15. Problema partición un conjunto de números.#
En este apartado vamos a ver cómo resolver el problema de dividir un conjunto de números, en dos o más grupos, de manera que la suma de los números de cada grupo sea la misma.
Para comenzar, inicialmente lo hacemos en dicidir una lista de números en dos grupos. Por lo tanto, lo primero que debemos tener es el conjunto de todos los números, que los colocaremos en una lista, como se hace a continuación
values = [1, 2, 3, 4, 5, 6, 7, 8]
15.1. Creación de un objeto de tipo BQM.#
Para resolver nuestro problema, debemos tener en cuenta lo siguiente:
Se utilizará la variable denominada x que valdrá 1 si el número está en el conjunto y cero en caso contrario.
En este problema NO hay función objetivo, sólo una restricción
La suma de los valores en cada conjunto debe ser la misma.
En consecuencia se debe cumplir lo siguiente
Operando en la expresión anterior, se llega a la siguiente igualdad.
A continuación creamos un objeto de tipo BQM (BinaryQuadraticModel), y le añadimos las variables con la propiedad add_variable. Esta variables se crean utilizando un diccionario de Python, para que de esa manera se trabaje mejor con ellas.
NOTA importante. Observar que la variable i-ésima se crea con la expresión : bqm.add_variable(f’x_{i}’) . Si vemos la documentación de este método, cuando no se pasa ningún valor como segundo argumento (que se refiere al valor del bias o constante por la que se multiplica \(x_i\)), el valor que toma por defecto es cero, es decir no existe término lineal y eso es así porque como hemos dicho en este caso no existe función objetivo, sólo una restricción.
from dimod import BinaryQuadraticModel
bqm = BinaryQuadraticModel('BINARY')
n = len(values)
# Creamos el diccionario que contiene cada variable tratada
x = {i: bqm.add_variable(f'x_{i}') for i in range(n)}
Veamos los valores que toma el diccionario generado:
x
{0: 'x_0',
1: 'x_1',
2: 'x_2',
3: 'x_3',
4: 'x_4',
5: 'x_5',
6: 'x_6',
7: 'x_7'}
A continuación vamos a crear una lista, que la llamamos sumandos, que será el primer parámetro del método add_linear_equality_constraint . Si observamos su documentación, este primer parámetro denominado terms, debe ser una lista que contenga pares de valores, de tal manera que para cada par de valor, el primer término es la variable \(x_i\) y el segundo término el valor del parámetro \(a_i\), en la expresión del tipo: \(\sum_{i=1}^{n}a_{i}x_{i}\).
En nuestro ejemplo, el primer valor del par será el valor del diciconario que hemos creado y el segundo término el valor i-ésimo de la lista values creada al principio multiplicado 2. Tener en cuenta que con el parámetro terms en este caso queremos modelar la expresión:
El segundo parámetro de add_linear_equality_constraint, denominado constant modelaría el término siguiente:
Mientras que el tercer parámetro no es más que el parámetro de Lagrange visto en el desarroll teórico. Teniendo todo esto en cuenta procedemos a continuación a implementar el código que entienda Ocean.
# Creamos la lista que debe ir dentro del parámetro terms
sumandos = [(f"x_{i}",2*values[i]) for i in range(n)]
sumandos
[('x_0', 2),
('x_1', 4),
('x_2', 6),
('x_3', 8),
('x_4', 10),
('x_5', 12),
('x_6', 14),
('x_7', 16)]
# Ahora incluimos la restricción, siguiendo las indicaciones anteriores
bqm.add_linear_equality_constraint(
terms= sumandos,
constant=-sum(values),
lagrange_multiplier=10
)
# Veamos el modelo que hemos creado
bqm
BinaryQuadraticModel({'x_0': -1400.0, 'x_1': -2720.0, 'x_2': -3960.0, 'x_3': -5120.0, 'x_4': -6200.0, 'x_5': -7200.0, 'x_6': -8120.0, 'x_7': -8960.0}, {('x_1', 'x_0'): 160.0, ('x_2', 'x_0'): 240.0, ('x_2', 'x_1'): 480.0, ('x_3', 'x_0'): 320.0, ('x_3', 'x_1'): 640.0, ('x_3', 'x_2'): 960.0, ('x_4', 'x_0'): 400.0, ('x_4', 'x_1'): 800.0, ('x_4', 'x_2'): 1200.0, ('x_4', 'x_3'): 1600.0, ('x_5', 'x_0'): 480.0, ('x_5', 'x_1'): 960.0, ('x_5', 'x_2'): 1440.0, ('x_5', 'x_3'): 1920.0, ('x_5', 'x_4'): 2400.0, ('x_6', 'x_0'): 560.0, ('x_6', 'x_1'): 1120.0, ('x_6', 'x_2'): 1680.0, ('x_6', 'x_3'): 2240.0, ('x_6', 'x_4'): 2800.0, ('x_6', 'x_5'): 3360.0, ('x_7', 'x_0'): 640.0, ('x_7', 'x_1'): 1280.0, ('x_7', 'x_2'): 1920.0, ('x_7', 'x_3'): 2560.0, ('x_7', 'x_4'): 3200.0, ('x_7', 'x_5'): 3840.0, ('x_7', 'x_6'): 4480.0}, 12960.0, 'BINARY')
from dimod import ExactSolver
#response = None # your code here (hint call the ExactSolver to sovle the bqm - Make sure to truncate to e.g. 10 samples)
response = ExactSolver().sample(bqm)
solution = response.first.sample # Elegimos la primera solución
print(solution)
print("\n*************Sacamos las 10 primeras soluciones******************\n")
# Trucamos hasta la solución 10
print(response.truncate(10))
{'x_0': 0, 'x_1': 1, 'x_2': 0, 'x_3': 1, 'x_4': 1, 'x_5': 0, 'x_6': 1, 'x_7': 0}
*************Sacamos las 10 primeras soluciones******************
x_0 x_1 x_2 x_3 x_4 x_5 x_6 x_7 energy num_oc.
0 0 1 0 1 1 0 1 0 0.0 1
1 0 0 1 0 0 0 1 1 0.0 1
2 1 1 1 0 1 0 1 0 0.0 1
3 1 0 1 0 0 1 0 1 0.0 1
4 1 0 0 1 0 1 1 0 0.0 1
5 0 0 0 0 1 1 1 0 0.0 1
6 0 0 1 1 1 1 0 0 0.0 1
7 1 1 1 1 0 0 0 1 0.0 1
8 1 0 0 1 1 0 0 1 0.0 1
9 1 1 0 0 0 0 1 1 0.0 1
['BINARY', 10 rows, 10 samples, 8 variables]
set1 = {values[i] for i in x if solution[x[i]]}
set2 = {values[i] for i in x if not solution[x[i]]}
print(f'{sum(set1)} = sum{tuple(set1)}')
print(f'{sum(set2)} = sum{tuple(set2)}')
18 = sum(2, 4, 5, 7)
18 = sum(8, 1, 3, 6)
15.2. Haciendo una partición en más de dos conjuntos#
En este apartado procedemos a extender el aprtado anterior, en el sentido de que aquí la lista de números inicial, la vamos a dividir en tres conjuntos, de manera que los números seleccionados en cada grupo sea la misma. Para hacer esto deberemos tener en cuenta lo siguiente:
Necesitamos una variable binaria, que tome valores 0 ó 1 para cada número y cada conjunto de valores.
La variable binaria en este caso \(x_{i,j} =1\) si el valor del número i-ésimo está en el grupo j. Por lo tanto en este caso i puede valor del 1 al total de números ( 9 en este ejemplo), y j puede valor 1,2 ó 3.
Cada valor o número puede ser asignado a un solo grupo
# Creamos el conjunto de números
values = [7, 2, 3, 1, 8, 3, 1, 2, 9]
# Creamos el modelo QUBO
bqm = BinaryQuadraticModel('BINARY')
n = len(values) # Es el número total de números
m = 3 # Es el número de particiones
x = {(i, k): bqm.add_variable((f'x_{i}', k))
for i in range(n)
for k in range(m)
}
Creamos a continuación un diccinario de variables, de manera que el índice es un par de números indicando el elemento iésimo de los números y el elemento j-ésimo de grupo de núemros, y como valor la variable binaria que se crea
x = {(i, k): bqm.add_variable((f'x_{i}', k))
for i in range(n)
for k in range(m)
}
x
{(0, 0): ('x_0', 0),
(0, 1): ('x_0', 1),
(0, 2): ('x_0', 2),
(1, 0): ('x_1', 0),
(1, 1): ('x_1', 1),
(1, 2): ('x_1', 2),
(2, 0): ('x_2', 0),
(2, 1): ('x_2', 1),
(2, 2): ('x_2', 2),
(3, 0): ('x_3', 0),
(3, 1): ('x_3', 1),
(3, 2): ('x_3', 2),
(4, 0): ('x_4', 0),
(4, 1): ('x_4', 1),
(4, 2): ('x_4', 2),
(5, 0): ('x_5', 0),
(5, 1): ('x_5', 1),
(5, 2): ('x_5', 2),
(6, 0): ('x_6', 0),
(6, 1): ('x_6', 1),
(6, 2): ('x_6', 2),
(7, 0): ('x_7', 0),
(7, 1): ('x_7', 1),
(7, 2): ('x_7', 2),
(8, 0): ('x_8', 0),
(8, 1): ('x_8', 1),
(8, 2): ('x_8', 2)}
A continuación vemos cómo trabaja el objeto combinations del paquete itertools, porque es algo que necesitamos conocer para entender mejor el paso siguiente.
from itertools import combinations
for k, l in combinations(range(m), r=2):
print(k,l)
0 1
0 2
1 2
Recordar que aquí no hay objetivo, sólo restricciones
Para resolver este problema, debemos de tener en cuenta que la suma de los conjuntos debe ser iguales. Entonces por cada para de conjuntos, se debe cumplir lo siguiente:
Es decir:
Plamemos todo esto en código python entendible por Ocean
from itertools import combinations
for k, l in combinations(range(m), r=2):
#expression es una lista que contiene (mediante list comprgension el primer conjunto de suma anterior)
expression = [(x[i,k] , values[i])for i in range(n)]
#expression += añadimos las symas de los segundos sumandos de la expresión anterior
expression +=[(x[i,l] , -values[i])for i in range(n)]
bqm.add_linear_equality_constraint(
expression,
constant=0,
lagrange_multiplier=10)
Añadimos ahora una restricción para segurarnos de que un numero sólo puede ser asignado a un conjunto de números. Es decir, se debe de cumplir lo siguiente:
for i in range(n):
bqm.add_linear_equality_constraint(
terms = [(x[i,j],1) for j in range(m) ],
constant=-1.0,
lagrange_multiplier=10)
Resolvemos el problema anterior utilizando el solver SimulatedAnnealingSample. Puede ser que se tenga que ejecutar varias veces…
from neal import SimulatedAnnealingSampler
res = SimulatedAnnealingSampler().sample(bqm, num_reads=100, num_sweeps=1000).truncate(5)
print(res)
('x_0', 0) ('x_0', 1) ('x_0', 2) ('x_1', 0) ... ('x_8', 2) energy num_oc.
0 0 0 1 0 ... 0 0.0 1
1 1 0 0 0 ... 1 0.0 1
2 0 1 0 0 ... 0 10.0 1
3 0 0 1 0 ... 0 10.0 1
4 1 0 0 1 ... 1 10.0 1
['BINARY', 5 rows, 5 samples, 27 variables]
El resultado que se obtiene es el siguiente
sample = res.first.sample
print(sum(values))
for k in range(m):
set1 = [values[i] for (i, l) in x if sample[x[i, l]] if k == l]
print(sum(set1), set1)
36
12 [3, 9]
12 [3, 8, 1]
12 [7, 2, 1, 2]