8. Introducción.#
En capítulos anteriores, ya hemos comentado cómo construir restricciones en los programa de QUBO, esta metodología la ampliaremos en el presente capítulo en el cual construiremos un programa con código Ocean para un problema que tiene una función objetivo y una restricción, lo cual implicará profundizar en cómo se utiliza el parámetro de Lagrange.
Recordemos que un problema tipo QUBO modela un problema real de optimización con variables binarias que sólo admiten los valores 0 ó 1 y lo que pretende siempre es minimizar una determinada función. Esta por regla general compuesto de una función objetivo así como de una serie de restricciones. El formato general de este tipo problemas es el siguiente:
Para formular nuestro QUBO, primero tenemos que definir claramente cuáles son nuestros objetivos y restricciones. A continuación, podemos averiguar cómo definir nuestras variables binarias. Una vez que hayamos escrito nuestros objetivos y restricciones como expresiones matemáticas binario, es posible que tengamos que hacer algunos ajustes para que se puedan combinar con un parámetro de Lagrange para construir el QUBO.
8.1. Ajustes en un problema tipo QUBO.#
Hay algunos parámetros que deberíamos intentar afinar para mejorar los resultados cuando construimos nuestro QUBO y lo ejecutamos en la QPU.
El primero es el número de lecturas. Recuerda que la QPU es probabilística, por lo que deberíamos establecer este número en 10, 100 o incluso 1000 dependiendo de la complejidad de nuestro problema.
El siguiente parámetro es el denominado parámetro de Lagrange. Este parámetro nos ayuda a determinar con qué fuerza ponderar cada restricción con respecto al objetivo y entre sí.
Si ve que se devuelven soluciones en las que no se satisface una restricción, considere aumentar valor del el parámetro de Lagrange que corresponde a esa restrcción.
Por último, podemos optar por ajustar manualmente el valor de la fuerza de la cadena (chain strength) para nuestro problema si no obtenemos buenos resultados con la herramienta de ajuste automático de Ocean
8.2. Elegir el parámetro de Lagrange.#
Veamos cómo podemos elegir un buen valor para un parámetro de Lagrange. Queremos elegir un valor que sea lo suficientemente grande como para que se satisfaga nuestra restricción, pero lo suficientemente pequeño para que no sobrecargar las otras restricciones y objetivos del problema.
Para ello, debemos tener en cuenta la importancia de que nuestra restricción se satisfaga en el problema original.
Si una restricción es dura, significa que debe satisfacerse absolutamente. Esto es como si un vendedor estuviera en una sola ciudad a la vez en el problema del viajante de comercio. Una persona no puede estar en dos lugares al mismo tiempo. Para una restricción dura tendremos que elegir un valor mayor para el parámetro de Lagrange.
Si una restricción es blanda, significa que podemos tener cierta flexibilidad en cuanto a si la restricción se satisface absolutamente o casi. Esto es como colocar antenas con poca o ninguna interferencia - un poco de interferencia está bien, pero lo ideal sería que no hubiera ninguna. Para una restricción suave, podemos elegir un valor menor para el parámetro de Lagrange
Entonces, ¿cómo podemos elegir un buen valor inicial para este parámetro sintonizable?.
Una buena regla general es pensar en el valor que tendrá la parte objetiva del problema en una solución óptima. Comience con ese valor, pruébelo y luego aumentar o disminuir el valor en función de las soluciones que se devuelven.
Esencialmente, queremos que los valores que se producen a partir de la parte de la restricción de QUBO estén en el mismo orden que los valores producidos por la parte del objetivo.
Si mi objetivo va a producir valores como 10 o 20, pero mi restricción tiene una penalización de 1 cuando no se cumple, elegiría un parámetro de Lagrange de 10 o 20 para que esas penalizaciones sean del mismo número que el objetivo original.
Al final, debería elegir el valor más pequeño que haya encontrado y que devuelva sistemáticamente soluciones con la restricción satisfecha## Herramientas de Ocean para formular restricciones.
Como se verá en otros capítulos, Ocean tiene una serie de métodos con los que se pueden añadir restricciones a los problemas de optimización. En este capítulo vamos a mostrar algunos concretos e interesantes para estos propòsitos.
Para la presentación de estos métodos, vamos a suponer que tenemos un modelo cuadrático de cinco variable, que queda representado por la siguiente matriz:
import numpy as np
matriz = np.array([
[-3,2,2,2,2],
[0,-3,2,2,2],
[0,0,-3,2,2],
[0,0,0,-3,2],
[0,0,0,0,-3]
])
matriz
array([[-3, 2, 2, 2, 2],
[ 0, -3, 2, 2, 2],
[ 0, 0, -3, 2, 2],
[ 0, 0, 0, -3, 2],
[ 0, 0, 0, 0, -3]])
Por lo tanto la fórmula matemática a minimizar sería la siguiente:
Formulamos entonces el problema de la siguiente forma:
from dimod import BQM
bqm = BQM("BINARY")
for i in range(5):
bqm.add_linear(f"X_{i}",matriz[i,i])
for i in range(5):
for j in range(i+1,5):
bqm.add_quadratic(f"X_{i}",f"X_{j}",matriz[i,j])
bqm
BinaryQuadraticModel({'X_0': -3.0, 'X_1': -3.0, 'X_2': -3.0, 'X_3': -3.0, 'X_4': -3.0}, {('X_1', 'X_0'): 2.0, ('X_2', 'X_0'): 2.0, ('X_2', 'X_1'): 2.0, ('X_3', 'X_0'): 2.0, ('X_3', 'X_1'): 2.0, ('X_3', 'X_2'): 2.0, ('X_4', 'X_0'): 2.0, ('X_4', 'X_1'): 2.0, ('X_4', 'X_2'): 2.0, ('X_4', 'X_3'): 2.0}, 0.0, 'BINARY')
Una de las restricciones que suelen ser utilizadas con mucha frecuencia en estos problemas es la restricción de elegir un número determinado de variables. Por ejemplo en este problema, supongamos que una restricción es que se tomen exactamente dos variables. Es decir la restricción sería la siguiente:
Esta restricción la podriamos introducir en la forma cuadrática mediante una suma y mutiplicando el parámetro de Lagrange \(\gamma\) por la siguiente expresión (convenientemente desarrollada): \((\sum_{i=0}^{4}X_i-2)^2\)
Pero sin embargo el paquete dimod, nos ofrece la posibilidad de construir esta restricción mediante el método dimod.generators.combinations()( ver este enlace ). Para añadir esta restricción utilizamos la forma bqm.update(…), en nuestro caso lo hariamos de la siguiente manera:
from dimod.generators import combinations
bqm.update(combinations(['X_0','X_1','X_2','X_3','X_4'],2))
La función de combinaciones en dimod le permite añadir una restricción de “elegir exactamente k de de n” a un objeto BQM. Aquí puede ver la sintaxis para utilizar esta función en un programa Ocean. Nuestra restricción es elegir exactamente 2 de 5 variables, o la suma de las variables binarias debe ser igual a 2.
Otra de las opciones que existe para añadir restricciones en un problema de tipo QUBO es mediante el método add_linear_equality_constraint() de un objeto del tipo BQM. Este método contiene los siguientes parámetros:
Terms:Términos en la forma [(var_1,coefic_1),…(var_n,coefic_n)]
Constant: Constante K (cambiada de signo en la restricción de las sumas)
Lagrange_multiplier:Coeficiente de lagrange
Por ejemplo supongamos que queremos meter la siguiente restricción:
Lo haríamos de la siguiente manera
bqm.add_linear_equality_constraint(
[('X_0',2),('X_1',4),('X_2',9),('X_3',4),('X_4',7)],
constant = -8,
lagrange_multiplier = 1
)
Por lo tanto y como sabemos, en muchos de los primeros módulos anteriores desarrollamos QUBOs que tenían restricciones de igualdad . Multiplicar los polinomios al cuadrado para obtener una matriz es mucho trabajo.
En cambio, podemos utilizar Ocean para añadir estas restricciones de igualdad directamente a un modelo cuadrático binario utilizando la función “add_linear_equality_constraint”. Esta función toma 3 parámetros. El primer parámetro es una lista de tuplas que representan las variables involucradas en la restricción y el coeficiente de cada variable. El segundo parámetro es la constante. Observa que la hemos movido al otro lado de la ecuación para que nuestra restricción sea igual a 0. El último parámetro es un parámetro de Lagrange de Lagrange.
NOTA. Observar en el desarrollor anterior que el término a la derecha de la restricción de igualdad que en este caso tiene un valor positivo, lo cambiamos de signo cuando lo incoporamos dentro del método “add_linear_equality_constraint”.
De forma similar a add_linear_equality_constraint existe una función llamada add_linear_inequality_constraint que se utiliza para añadir restricciones de desigualdad.
A continuación vamos a añadir dos restricciones más. Una será que tomamos como mucho 3 variables y la otra tendrá la forma genérica siguiente:
El uso de esta función es casi exactamente el mismo que en el caso anterior, excepto que debemos proporcionar una etiqueta como entrada cuando se utiliza esta función. La etiqueta nos permite ver las variables adicionales que hay que introducir, llamadas variables de holgura.
Por lo tanto el formato de add_linear_inequality_constraint() será el siguiente:
Terms:Términos en la forma [(var_1,coefic_1),…(var_n,coefic_n)]
Constant: Constante K (cambiada de signo en la restricción de las sumas)
Lagrange_multiplier:Coeficiente de lagrange
Label: Una etiqueta para las restricciones
Un ejemplo de lo anterior sería lo siguiente (\(2X_0+4X_1+9X_2+4X_3+7X_4 \le 8\)):
bqm = BQM('BINARY')
bqm.add_linear_inequality_constraint(
[('X_0',2),('X_1',4),('X_2',9),('X_3',4),('X_4',7)],
constant = -8,
lagrange_multiplier = 1,
label= 'count'
)
[('slack_count_0', 1),
('slack_count_1', 2),
('slack_count_2', 4),
('slack_count_3', 1)]
Cuando añadimos una desigualdad a un BQM, las variables de holgura son variables binarias adicionales l que el software utiliza para convertir la desigualdad en una igualdad.
En la siguiente imagen podremos ver un ejemplo sencillo sobre la forma de actuar de estas variables de holgura (slack variables)
Por lo tanto arriba se muestra un ejemplo de cómo funcionan las variables de holgura. Supongamos que necesitamos elegir como máximo 2 números que sumen 3 de nuestro conjunto A. Hay dos soluciones: 1+2 y 3 por sí mismo.
En la solución en la que elegimos 1+2, estamos utilizando exactamente dos números. En este caso, nuestra desigualdad para elegir a lo sumo 2 es en realidad una igualdad - que elegimos exactamente 2 números. Esto significa que nuestras variables de holgura deben tener todas el valor 0. No necesitamos aumentar cuántos números fueron elegidos para cumplir con el valor 2 que es nuestro límite superior.
Por otro lado, en la solución en la que elegimos sólo el número 3 necesitamos que las variables de holgura jueguen un papel. Nuestro límite superior de cuántos números podemos elegir es 2, y elegimos sólo 1. Deberíamos esperar que una de nuestras variables de holgura tenga un valor de 1 para ayudarnos a cumplir el límite superior de nuestra desigualdad.
En el conjunto de muestras mostrado, podemos ver las variables de holgura para nuestra restricción que etiquetamos en anterior imagen. Hay dos variables de holgura porque nuestro modelo.
En el peor de los casos, podríamos no elegir ningún número, por lo que para llegar al límite superior de 2 necesitamos dos variables de holgura.
Para nuestra solución de 1+2, ambas variables de holgura son 0, mientras que para la solución 3 vemos que una de ellas tiene el valor de uno.
La forma más eficiente de definir y utilizar las variables de holgura es definirlas como exponentes para que podamos añadir un número logarítmico de variables de holgura en lugar de que el número de variables de holgura crezca a un ritmo lineal con el límite superior (ver apartado restricciones de desigualdad)