Models

Aquest exemple mínim presenta un model d’optimització binària, el converteix a una forma de penalització QUBO i exporta el Hamiltonian corresponent:

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)

Objectius i restriccions

Cada Model consta de:

• Un únic Objective

• Zero o més instàncies de Constraint

Objectiu

El Objective defineix la funció que el model pretén minimitzar o maximitzar. Exemple:

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)

Sortida:

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

Les restriccions de codificació s’afegeixen automàticament per a les variables contínues acotades. Cada restricció té un multiplicador de Lagrange associat, que determina la penalització per violar-la.

Podeu actualitzar el multiplicador de la manera següent:

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

Sortida:

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

Restriccions

Es poden afegir Restriccions addicionals per limitar l’espai de solucions:

from qilisdk.core import LT

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

Sortida:

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

Constructors

En lloc de construir un model des de zero, també podeu construir-lo per a certs problemes predefinits:

• Model.ising(edges, couplings, fields, label) - Construeix un problema d’Ising per a un graf amb pesos donat.

• Model.knapsack(values, weights, max_weight, label, lagrange_multiplier) - Construeix un problema de la motxilla amb els pesos, valors i capacitat donats.

• Model.max_cut(edges, weights, label) - Construeix un problema de tall màxim per a un graf donat.

• Model.graph_coloring(graph, num_colors, label, lagrange_multiplier) - Construeix un problema de coloració de grafs per a un graf i un nombre de colors donats.

• Model.travelling_salesman(edges, distances, label, lagrange_multiplier) - Construeix un problema del viatjant de comerç per a una matriu de distàncies donada.

• Model.factoring(n, label) - Construeix un problema de factorització per a un enter donat.

Cadascun d’aquests (excepte la factorització) també té una contrapart aleatòria, útil per generar problemes per a proves i avaluacions de rendiment:

• Model.random_ising(num_variables, edge_probability, coefficient_range, label, seed) - Construeix un model d’Ising aleatori, completament connectat per defecte.

• Model.random_knapsack(num_items, value_range, weight_range, capacity_ratio, label, seed, lagrange_multiplier) - Construeix un problema de la motxilla amb valors i pesos aleatoris.

• Model.random_max_cut(num_nodes, edge_probability, weight_range, label, seed) - Construeix un problema de tall màxim sobre un graf connex aleatori.

• Model.random_graph_coloring(num_nodes, num_colors, edge_probability, label, seed, lagrange_multiplier) - Construeix un problema de coloració de grafs sobre un graf connex aleatori.

• Model.random_travelling_salesman(num_cities, edge_probability, distance_range, label, seed, lagrange_multiplier) - Construeix un problema del viatjant de comerç amb distàncies aleatòries, sobre un graf complet per defecte.

Per exemple, per crear un problema de la motxilla:

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)

Avaluar un model

Per avaluar un Model, proporcioneu valors per a totes les variables implicades:

model.evaluate({
    x: 1.4
})

Sortida:

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

L’avaluació retorna un diccionari amb valors per a l’objectiu i les restriccions. Una restricció retorna 0.0 si es satisfà, o el seu multiplicador de Lagrange si es viola.

Per exemple:

model.evaluate({
    x: 2
})

Sortida:

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

Resoldre un model de manera clàssica

Per ajudar a demostrar els límits dels resolutors clàssics, es proporcionen diversos embolcalls per a diferents resolutors:

• BruteForceSolver - Un resolutor de força bruta que avalua totes les solucions possibles.

• ScipySolver - Un resolutor que utilitza una de les rutines optimize de SciPy per trobar una solució.

• SimulatedAnnealingSolver - Un resolutor de recuita simulada, implementat completament en C++. Requereix un QUBO, per la qual cosa un model general s’ha de convertir primer amb to_qubo().

• ScipSolver - Un embolcall per a SCIP, un resolutor de programació entera mixta. Això requereix l’extra de SCIP (és a dir, pip install "qilisdk[scip]").

Es poden utilitzar de la manera següent:

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)

Cadascun d’ells retorna un ClassicalSolverResult, que exposa la solució trobada:

• result.objective - el valor de l’objectiu del model en la solució

• result.constraints - el valor de cadascuna de les restriccions del model, indexades per la seva etiqueta

• result.results - l’objectiu i totes les restriccions juntes, indexats per la seva etiqueta

• result.sample - el valor que pren cadascuna de les variables del model en la solució

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