Modelos

Este ejemplo mínimo presenta un modelo de optimización binaria, lo convierte a la forma de penalización QUBO y exporta el Hamiltonian correspondiente:

from qilisdk.core import BinaryVariable, LEQ, Model, ObjectiveSense
from qilisdk.core.model import QUBO

x0, x1 = BinaryVariable("x0"), BinaryVariable("x1")

model = Model("toy")
model.set_objective(-2 * x0 - 3 * x1 + 4 * x0 * x1,
                    label="energy",
                    sense=ObjectiveSense.MINIMIZE)
model.add_constraint("budget", LEQ(x0 + x1, 1), lagrange_multiplier=5)

qubo = model.to_qubo()
print(qubo.qubo_objective)

ham = qubo.to_hamiltonian()
print(ham)

Objetivos y restricciones

Cada Model consta de:

• Un único Objective

• Cero o más instancias de Constraint

Objetivo

El Objective define la función que el modelo trata de minimizar o maximizar. Ejemplo:

from qilisdk.core.model import Model, ObjectiveSense
from qilisdk.core.variables import Variable, Domain, Bitwise
model = Model("example_model")
x = Variable("x", domain=Domain.REAL, bounds=(1, 2), encoding=Bitwise, precision=1e-1)
model.set_objective(2*x + 3, label="obj", sense=ObjectiveSense.MINIMIZE)
print(model)

Salida:

Model name: example_model
objective (obj):
    minimize :
    (2) * x + (3)

subject to the encoding constraint/s:
    x_upper_bound_constraint: x <= (2)
    x_lower_bound_constraint: x >= (1)

With Lagrange Multiplier/s:
    x_upper_bound_constraint : 100
    x_lower_bound_constraint : 100

Las restricciones de codificación se añaden automáticamente para variables continuas acotadas. Cada restricción tiene un multiplicador de Lagrange asociado que determina la penalización por violarla.

Puede actualizar el multiplicador de la siguiente manera:

model.set_lagrange_multiplier("x_upper_bound_constraint", 1)
print(model)

Salida:

Model name: example_model
objective (obj):
    minimize :
    (2) * x + (3)

subject to the encoding constraint/s:
    x_upper_bound_constraint: x <= (2)
    x_lower_bound_constraint: x >= (1)

With Lagrange Multiplier/s:
    x_upper_bound_constraint : 1
    x_lower_bound_constraint : 100

Restricciones

Se pueden añadir Restricciones adicionales para acotar el espacio de soluciones:

from qilisdk.core import LT

model.add_constraint("test_constraint", LT(x, 1.5), lagrange_multiplier=10)
print(model)

Salida:

Model name: example_model
objective (obj):
    minimize :
    (2) * x + (3)

subject to the constraint/s:
    test_constraint: x < (1.5)

subject to the encoding constraint/s:
    x_upper_bound_constraint: x <= (2)
    x_lower_bound_constraint: x >= (1)

With Lagrange Multiplier/s:
    x_upper_bound_constraint : 1
    x_lower_bound_constraint : 100
    test_constraint : 10

Constructores

En lugar de construir un modelo desde cero, también puede construirlo para ciertos problemas predefinidos:

• Model.ising(edges, couplings, fields, label) - Construye un problema de Ising para un grafo con pesos dado.

• Model.knapsack(values, weights, max_weight, label, lagrange_multiplier) - Construye un problema de la mochila con los pesos, valores y capacidad dados.

• Model.max_cut(edges, weights, label) - Construye un problema de corte máximo para un grafo dado.

• Model.graph_coloring(graph, num_colors, label, lagrange_multiplier) - Construye un problema de coloreado de grafos para un grafo y un número de colores dados.

• Model.travelling_salesman(edges, distances, label, lagrange_multiplier) - Construye un problema del viajante de comercio para una matriz de distancias dada.

• Model.factoring(n, label) - Construye un problema de factorización para un entero dado.

Cada uno de estos (excepto la factorización) también tiene una contraparte aleatoria, útil para generar problemas de prueba y de evaluación de rendimiento:

• Model.random_ising(num_variables, edge_probability, coefficient_range, label, seed) - Construye un modelo de Ising aleatorio, completamente conectado por defecto.

• Model.random_knapsack(num_items, value_range, weight_range, capacity_ratio, label, seed, lagrange_multiplier) - Construye un problema de la mochila con valores y pesos aleatorios.

• Model.random_max_cut(num_nodes, edge_probability, weight_range, label, seed) - Construye un problema de corte máximo sobre un grafo conexo aleatorio.

• Model.random_graph_coloring(num_nodes, num_colors, edge_probability, label, seed, lagrange_multiplier) - Construye un problema de coloreado de grafos sobre un grafo conexo aleatorio.

• Model.random_travelling_salesman(num_cities, edge_probability, distance_range, label, seed, lagrange_multiplier) - Construye un problema del viajante de comercio con distancias aleatorias, sobre un grafo completo por defecto.

Por ejemplo, para crear un problema de la mochila:

from qilisdk.core import Model

values = [10, 15, 40]
weights = [1, 2, 3]
max_weight = 6
knapsack_model = Model.knapsack(values, weights, max_weight)
print(knapsack_model)

Evaluar un modelo

Para evaluar un Model, proporcione valores para todas las variables implicadas:

model.evaluate({
    x: 1.4
})

Salida:

{'obj': 5.8, 'test_constraint': 0.0}

La evaluación devuelve un diccionario con valores para el objetivo y las restricciones. Una restricción devuelve 0.0 si se satisface, o su multiplicador de Lagrange si se viola.

Por ejemplo:

model.evaluate({
    x: 2
})

Salida:

{'obj': 7.0, 'test_constraint': 10.0}

Resolver un modelo de forma clásica

Para ayudar a demostrar los límites de los solucionadores clásicos, se proporcionan varios envoltorios para diferentes solucionadores:

• BruteForceSolver - Un solucionador de fuerza bruta que evalúa todas las soluciones posibles.

• ScipySolver - Un solucionador que utiliza una de las rutinas optimize de SciPy para encontrar una solución.

• SimulatedAnnealingSolver - Un solucionador de recocido simulado, implementado completamente en C++. Requiere un QUBO, por lo que un modelo general debe convertirse primero con to_qubo().

• ScipSolver - Un envoltorio para SCIP, un solucionador de programación entera mixta. Esto requiere el extra de SCIP (es decir, pip install "qilisdk[scip]").

Se pueden utilizar de la siguiente manera:

from qilisdk.core import Model
from qilisdk.utils.classical_solvers import BruteForceSolver
model = Model.random_ising(4)
solver = BruteForceSolver()
result = solver.solve(model)
print(result)

Cada uno de ellos devuelve un ClassicalSolverResult, que expone la solución encontrada:

• result.objective - el valor del objetivo del modelo en la solución

• result.constraints - el valor de cada una de las restricciones del modelo, indexadas por su etiqueta

• result.results - el objetivo y todas las restricciones juntos, indexados por su etiqueta

• result.sample - el valor que toma cada una de las variables del modelo en la solución

print(result.objective)
print(result.sample)