Nota

Esta página fue generada a partir de docs/tutorials/01_quadratic_program.ipynb.

Programas Cuadráticos

Introducción

En este tutorial presentamos brevemente cómo construir problemas de optimización usando el módulo de optimización de Qiskit. Qiskit Optimization introduce la clase QuadraticProgram para hacer un modelo de un problema de optimización. Más precisamente, se ocupa de programas cuadráticamente restringidos que se dan de la siguiente manera:

\[\begin{split}\begin{align} \text{minimizar}\quad& x^\top Q_0 x + c^\top x\\ \text{sujeto a}\quad& A x \leq b\\ & x^\top Q_i x + a_i^\top x \leq r_i, \quad 1,\dots,i,\dots,q\\ & l_i \leq x_i \leq u_i, \quad 1,\dots,i,\dots,n, \end{align}\end{split}\]

donde los \(Q_i\) son matrices \(n \times n\), \(A\) es una matriz \(m \times n\), \(x\) y \(c\) son vectores \(n\)-dimensionales, \(b\) es un vector \(m\)-dimensional, y donde las \(x\) se pueden definir como variables binarias, enteras o continuas. Además de las restricciones «\(\leq\)», QuadraticProgram también admite «\(\geq\)» e «\(=\)».

Cargar un QuadraticProgram desde un archivo LP

Como configuración, necesitas importar el siguiente módulo.

from qiskit_optimization import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp

Comienzas con un modelo vacío. La forma de agregar variables y restricciones a un modelo se explica en la sección Construir directamente un QuadraticProgram.

El módulo de optimización de Qiskit soporta la conversión del modelo Docplex. Puedes crear fácilmente un modelo de un problema de optimización con Docplex. Puedes encontrar la documentación de Docplex en https://ibmdecisionoptimization.github.io/docplex-doc/mp/index.html

Puedes cargar un modelo Docplex en QuadraticProgram utilizando la función from_docplex_mp.

Carga de un QuadraticProgram desde un modelo docplex

# Make a Docplex model
from docplex.mp.model import Model

mdl = Model("docplex model")
x = mdl.binary_var("x")
y = mdl.integer_var(lb=-1, ub=5, name="y")
mdl.minimize(x + 2 * y)
mdl.add_constraint(x - y == 3)
mdl.add_constraint((x + y) * (x - y) <= 1)
print(mdl.export_as_lp_string())

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: docplex model

Minimize
 obj: x + 2 y
Subject To
 c1: x - y = 3
 qc1: [ x^2 - y^2 ] <= 1

Bounds
 0 <= x <= 1
 -1 <= y <= 5

Binaries
 x

Generals
 y
End

QuadraticProgram tiene un método prettyprint para generar una representación completa de cadenas.

# load from a Docplex model
mod = from_docplex_mp(mdl)
print(type(mod))
print()
print(mod.prettyprint())

<class 'qiskit_optimization.problems.quadratic_program.QuadraticProgram'>

Problem name: docplex model

Minimize
  x + 2*y

Subject to
  Linear constraints (1)
    x - y == 3  'c0'

  Quadratic constraints (1)
    x^2 - y^2 <= 1  'q0'

  Integer variables (1)
    -1 <= y <= 5

  Binary variables (1)
    x

Construir directamente un QuadraticProgram

A continuación, explicamos cómo hacer el modelo de un problema de optimización directamente utilizando QuadraticProgram. Empecemos con un modelo vacío.

# make an empty problem
mod = QuadraticProgram("my problem")
print(mod.prettyprint())

Problem name: my problem

Minimize
  0

Subject to
  No constraints

  No variables

El QuadraticProgram admite tres tipos de variables:

• Variable binaria

• Variable entera

• Variable continua

Cuando agregas variables, puedes especificar nombres, tipos, límites inferiores y límites superiores.

# Add variables
mod.binary_var(name="x")
mod.integer_var(name="y", lowerbound=-1, upperbound=5)
mod.continuous_var(name="z", lowerbound=-1, upperbound=5)
print(mod.prettyprint())

Problem name: my problem

Minimize
  0

Subject to
  No constraints

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

Puedes establecer la función objetivo invocando QuadraticProgram.minimize o QuadraticProgram.maximize. Puedes añadir un término constante, así como una función objetivo lineal y cuadrática, especificando términos lineales y cuadráticos con una lista, una matriz o un diccionario.

Ten en cuenta que en el formato LP la parte cuadrática tiene que ser escalada por un factor de \(1/2\). Por lo tanto, cuando se imprime como formato LP, la parte cuadrática se multiplica primero por 2 y luego se divide entre 2 de nuevo.

Para los programas cuadráticos, hay 3 piezas que se deben de especificar: una constante (compensación u offset), un término lineal (\(c^{T}x\)), y un término cuadrático (\(x^{T}Qx\)).

La siguiente celda muestra cómo declarar una función objetivo utilizando un diccionario. Para el término lineal, las claves en el diccionario corresponden a nombres de variables, y los valores correspondientes son los coeficientes. Para el término cuadrático, las claves en el diccionario corresponden a las dos variables que se están multiplicando, y los valores son de nuevo los coeficientes.

# Add objective function using dictionaries
mod.minimize(constant=3, linear={"x": 1}, quadratic={("x", "y"): 2, ("z", "z"): -1})
print(mod.prettyprint())

Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  No constraints

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

Otra forma de especificar el programa cuadrático es usando arreglos. Para el término lineal, el arreglo corresponde al vector \(c\) en la formulación matemática. Para el término cuadrático, el arreglo corresponde a la matriz \(Q\). Ten en cuenta que el orden de las variables (\(x\) en la formulación matemática) es el orden en el que las variables fueron declaradas originalmente en el objeto QuadraticProgram.

# Add objective function using lists/arrays
mod.minimize(constant=3, linear=[1, 0, 0], quadratic=[[0, 1, 0], [1, 0, 0], [0, 0, -1]])
print(mod.prettyprint())

Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  No constraints

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

Puedes acceder a la constante, el término lineal y el término cuadrático mediante Quadratic.objective.{constant, linear, quadratic}, respectivamente. En cuanto a los términos lineales y cuadráticos, puedes obtener una matriz densa (to_array), una matriz dispersa (coefficients), y un diccionario (to_dict). Para los diccionarios, puedes especificar si usar los índices de variables o los nombres como claves. Ten en cuenta que los términos cuadráticos se almacenan de una manera comprimida, por ejemplo, {('x', 'y'): 1, ('y', 'x'): 2} se almacena como {('x', 'y'): 3}. Puedes obtener el término cuadrático como una matriz simétrica llamando a to_array(symmetric=True) o to_dict(symmetric=True). Si llamas a to_dict(name=True), puedes obtener un diccionario cuyas claves son pares de nombres de variables.

print("constant:\t\t\t", mod.objective.constant)
print("linear dict:\t\t\t", mod.objective.linear.to_dict())
print("linear array:\t\t\t", mod.objective.linear.to_array())
print("linear array as sparse matrix:\n", mod.objective.linear.coefficients, "\n")
print("quadratic dict w/ index:\t", mod.objective.quadratic.to_dict())
print("quadratic dict w/ name:\t\t", mod.objective.quadratic.to_dict(use_name=True))
print(
    "symmetric quadratic dict w/ name:\t",
    mod.objective.quadratic.to_dict(use_name=True, symmetric=True),
)
print("quadratic matrix:\n", mod.objective.quadratic.to_array(), "\n")
print("symmetric quadratic matrix:\n", mod.objective.quadratic.to_array(symmetric=True), "\n")
print("quadratic matrix as sparse matrix:\n", mod.objective.quadratic.coefficients)

constant:                        3
linear dict:                     {0: 1}
linear array:                    [1 0 0]
linear array as sparse matrix:
   (0, 0)       1

quadratic dict w/ index:         {(0, 1): 2, (2, 2): -1}
quadratic dict w/ name:          {('x', 'y'): 2, ('z', 'z'): -1}
symmetric quadratic dict w/ name:        {('y', 'x'): 1, ('x', 'y'): 1, ('z', 'z'): -1}
quadratic matrix:
 [[ 0  2  0]
 [ 0  0  0]
 [ 0  0 -1]]

symmetric quadratic matrix:
 [[ 0  1  0]
 [ 1  0  0]
 [ 0  0 -1]]

quadratic matrix as sparse matrix:
   (0, 1)       2
  (2, 2)        -1

Agregar/eliminar restricciones lineales y cuadráticas

Puedes agregar restricciones lineales estableciendo un nombre, expresión lineal, sentido y el valor del lado derecho (right-hand-side, rhs). Puedes utilizar los sentidos “EQ”, “LE”, y “GE” como lo soporta Docplex.

# Add linear constraints
mod.linear_constraint(linear={"x": 1, "y": 2}, sense="==", rhs=3, name="lin_eq")
mod.linear_constraint(linear={"x": 1, "y": 2}, sense="<=", rhs=3, name="lin_leq")
mod.linear_constraint(linear={"x": 1, "y": 2}, sense=">=", rhs=3, name="lin_geq")
print(mod.prettyprint())

Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  Linear constraints (3)
    x + 2*y == 3  'lin_eq'
    x + 2*y <= 3  'lin_leq'
    x + 2*y >= 3  'lin_geq'

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

Puedes añadir restricciones cuadráticas, así como funciones objetivo y restricciones lineales.

# Add quadratic constraints
mod.quadratic_constraint(
    linear={"x": 1, "y": 1},
    quadratic={("x", "x"): 1, ("y", "z"): -1},
    sense="==",
    rhs=1,
    name="quad_eq",
)
mod.quadratic_constraint(
    linear={"x": 1, "y": 1},
    quadratic={("x", "x"): 1, ("y", "z"): -1},
    sense="<=",
    rhs=1,
    name="quad_leq",
)
mod.quadratic_constraint(
    linear={"x": 1, "y": 1},
    quadratic={("x", "x"): 1, ("y", "z"): -1},
    sense=">=",
    rhs=1,
    name="quad_geq",
)
print(mod.prettyprint())

Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  Linear constraints (3)
    x + 2*y == 3  'lin_eq'
    x + 2*y <= 3  'lin_leq'
    x + 2*y >= 3  'lin_geq'

  Quadratic constraints (3)
    x^2 - y*z + x + y == 1  'quad_eq'
    x^2 - y*z + x + y <= 1  'quad_leq'
    x^2 - y*z + x + y >= 1  'quad_geq'

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

Puedes acceder a términos lineales y cuadráticos de restricciones cuadráticas y lineales como del mismo modo que la función objetivo.

lin_geq = mod.get_linear_constraint("lin_geq")
print("lin_geq:", lin_geq.linear.to_dict(use_name=True), lin_geq.sense, lin_geq.rhs)
quad_geq = mod.get_quadratic_constraint("quad_geq")
print(
    "quad_geq:",
    quad_geq.linear.to_dict(use_name=True),
    quad_geq.quadratic.to_dict(use_name=True),
    quad_geq.sense,
    lin_geq.rhs,
)

lin_geq: {'x': 1.0, 'y': 2.0} ConstraintSense.GE 3
quad_geq: {'x': 1.0, 'y': 1.0} {('x', 'x'): 1.0, ('y', 'z'): -1.0} ConstraintSense.GE 3

También puedes eliminar restricciones lineales/cuadráticas con remove_linear_constraint y remove_quadratic_constraint.

# Remove constraints
mod.remove_linear_constraint("lin_eq")
mod.remove_quadratic_constraint("quad_leq")
print(mod.prettyprint())

Problem name: my problem

Minimize
  2*x*y - z^2 + x + 3

Subject to
  Linear constraints (2)
    x + 2*y <= 3  'lin_leq'
    x + 2*y >= 3  'lin_geq'

  Quadratic constraints (2)
    x^2 - y*z + x + y == 1  'quad_eq'
    x^2 - y*z + x + y >= 1  'quad_geq'

  Integer variables (1)
    -1 <= y <= 5

  Continuous variables (1)
    -1 <= z <= 5

  Binary variables (1)
    x

Puedes sustituir algunas de las variables con constantes u otras variables. Más precisamente, QuadraticProgram tiene un método substitute_variables(constants=..., variables=...) para tratar los dos casos siguientes.

• \(x \leftarrow c\): cuando constants tenga un diccionario {x: c}.

• \(x \leftarrow c y\): cuando variables tenga un diccionario {x: (y, c)}.

Sustituir Variables

sub = mod.substitute_variables(constants={"x": 0}, variables={"y": ("z", -1)})
print(sub.prettyprint())

Problem name: my problem

Minimize
  -z^2 + 3

Subject to
  Linear constraints (2)
    -2*z <= 3  'lin_leq'
    -2*z >= 3  'lin_geq'

  Quadratic constraints (2)
    z^2 - z == 1  'quad_eq'
    z^2 - z >= 1  'quad_geq'

  Continuous variables (1)
    -1 <= z <= 1

Si el problema resultante es inviable debido a los límites inferiores o superiores, los métodos devuelven el estado Status.INFEASIBLE. Intentamos reemplazar la variable x por -1, pero -1 está fuera del rango de x (0 <= x <= 1). Por lo tanto, se devuelve Status.INFEASIBLE.

sub = mod.substitute_variables(constants={"x": -1})
print(sub.status)

Infeasible substitution for variable: x

QuadraticProgramStatus.INFEASIBLE

No puedes sustituir variables varias veces. El método devuelve un error en tal caso.

from qiskit_optimization import QiskitOptimizationError

try:
    sub = mod.substitute_variables(constants={"x": -1}, variables={"y": ("x", 1)})
except QiskitOptimizationError as e:
    print("Error: {}".format(e))

Error: 'Cannot substitute by variable that gets substituted itself: y <- x 1'

Nota: Cuando muestras tu problema en formato LP usando export_as_lp_string, Binaries denota variables binarias y Generals denota variables enteras. Si las variables no están incluidas en Binaries o Generals, dichas variables son continuas con el límite inferior predeterminado = 0 y el límite superior = infinito. Ten en cuenta que no puedes utilizar “e” o “E” como el primer carácter de los nombres debido a la especificación del formato LP.

mod = QuadraticProgram()
mod.binary_var(name="e")
mod.binary_var(name="f")
mod.continuous_var(name="g")
mod.minimize(linear=[1, 2, 3])
print(mod.export_as_lp_string())

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX

Minimize
 obj: _e + 2 f + 3 g
Subject To

Bounds
 0 <= _e <= 1
 0 <= f <= 1

Binaries
 _e f
End

import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
qiskit-terra	0.21.0.dev0+dbd3961
qiskit-aer	0.10.4
qiskit-ibmq-provider	0.19.1
qiskit-optimization	0.4.0
System information
Python version	3.10.4
Python compiler	GCC 11.2.0
Python build	main, Apr 2 2022 09:04:19
OS	Linux
CPUs	4
Memory (Gb)	14.577545166015625
Wed May 18 16:03:27 2022 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.