Nota

Esta página foi gerada a partir do tutoriais/otimizacao/1_programa_quadratico.ipynb.

Execute interativamente no IBM Quantum lab.

Programas Quadráticos

Introdução

Neste tutorial, introduzimos brevemente como construir problemas de otimização usando o módulo de otimização do Qiskit. O Qiskit introduz a classe QuadraticProgram para fazer um modelo de um problema de otimização. Mais precisamente, ela lida com programas quadráticos restritos quadraticamente, dados da seguinte forma:

\[\begin{split}\begin{align} \text{minimize}\quad& x^\top Q_0 x + c^\top x\\ \text{subject to}\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}\]

onde \(Q_i\) são matrizes \(n \times n\), \(A\) é uma matriz \(m \times n\), \(x\) e \(c\) são vetores \(n\)-dimensionais, \(b\) é um vetor \(m\)-dimensional, e onde \(x\) pode ser definido com variáveis binárias, inteiras ou contínuas. Além das restrições “\(\leq\)”, ‘QuadraticProgram’ também suporta “\(\geq\)” and “\(=\)”.

Carregando um Quadratic Program a partir de um arquivo LP

Como configuração, é necessário importar o seguinte módulo.

from qiskit.optimization import QuadraticProgram

Você começa com um modelo vazio. Como adicionar variáveis e restrições a um modelo é explicado na seção “Construindo diretamente um QuadraticProgram”.

O módulo de otimização do Qiskit suporta a conversão de um modelo Docplex. Você pode facilmente fazer um modelo de um problema de otimização com o Docplex. Você pode encontrar a documentação do Docplex em https://ibmdecisionoptimization.github.io/docplex-doc/mp/index.html

Você pode carregar um modelo Docplex para QuadraticProgram invocando from_docplex.

Carregando um QuadraticProgram a partir de um 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

# load from a Docplex model
mod = QuadraticProgram()
mod.from_docplex(mdl)
print(mod.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
 c0: x - y = 3
 q0: [ x^2 - y^2 ] <= 1

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

Binaries
 x

Generals
 y
End

Construindo diretamente um QuadraticProgram

Explicamos então como modelar um problema de otimização diretamente utilizando a QuadraticProgram. Vamos começar a partir de um modelo vazio.

# make an empty problem
mod = QuadraticProgram('my problem')
print(mod.export_as_lp_string())

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

Minimize
 obj:
Subject To

Bounds
End

A QuadraticProgram suporta três tipos de variáveis: - Variável binária - Variável inteira - Variável contínua

Quando você adiciona variáveis, você pode especificar nomes, tipos, limites inferiores e limites superiores.

Ao visualizar o seu problema como formato LP, Binaries denota variáveis binárias e Generals denota variáveis inteiras. Se as variáveis não estiverem incluídas em Binaries nem Generals, tais variáveis são contínuas com limite inferior = 0 e limite superior = infinito por padrão. Observe que você não pode usar ‘e’ ou ‘E’ como o primeiro caractere de nomes devido à especificação do formato LP.

# 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.export_as_lp_string())

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

Minimize
 obj:
Subject To

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

Binaries
 x

Generals
 y
End

Você pode configurar a função objetiva invocando QuadraticProgram.minimize ou QuadraticProgram.maximize. Você pode adicionar um termo constante assim como uma função objetiva linear e quadrática especificando termos lineares e quadráticos usando uma lista, matriz ou dicionário.

Observe que no formato LP a parte quadrática tem que ser escalonada por um fator \(1/2\). Assim, quando imprimindo no formato LP, a parte quadrática é primeiramente multiplicada por 2 e então dividida por 2 novamente.

Para os programas quadráticos, existem 3 peças que devem ser especificadas: uma constante (offset), um termo linear (\(c^{T}x\)), e um termo quadrático (\(x^{T}Qx\)).

A célula abaixo mostra como declarar uma função objetiva usando um dicionário. Para o termo linear, as chaves do dicionário correspondem a nomes de variáveis, sendo que os valores correspondentes são os coeficientes. Para o termo quadrático, as chaves do dicionário correspondem às duas variáveis que estão sendo multiplicadas, sendo que os valores são novamente os coeficientes.

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

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

Minimize
 obj: x + [ 4 x*y - 2 z^2 ]/2 + 3
Subject To

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

Binaries
 x

Generals
 y
End

Outra maneira de especificar o programa quadrático é usando matrizes. Para o termo linear, a matriz corresponde ao vetor \(c\) na formulação matemática. Para o termo quadrático, a matriz corresponde à matriz \(Q\). Observe que a ordenação das variáveis (\(x\) na formulação matemática) é a ordem na qual as variáveis foram originalmente declaradas no 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.export_as_lp_string())

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

Minimize
 obj: x + [ 4 x*y - 2 z^2 ]/2 + 3
Subject To

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

Binaries
 x

Generals
 y
End

Você pode acessar a constante, o termo linear, e o termo quadrático olhando para Quadratic.objective.{constant, linear, quadratic}, respectivamente. Quanto aos termos lineares e quadráticos, pode-se obter uma matriz densa (to_array), uma matriz esparsa (coefficients), e um dicionário (to_dict). Para os dicionários, é possível especificar se deve usar os índices ou nomes das variáveis como chaves. Observe que os termos quadráticos são armazenados de forma compactada, por exemplo, {('x', 'y'): 1, ('y', 'x'): 2} é armazenado como {('x', 'y'): 3}. Você pode obter o termo quadrático como uma matriz simétrica chamando to_array(symmetric=True) ou to_dict(symmetric=True). Se você chamar to_dict(name=True), você pode obter um dicionário cujas chaves são pares de nomes de variáveis.

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

Adicionando/removendo restrições lineares e quadráticas

Você pode adicionar restrições lineares configurando um nome, uma expressão linear, um sentido e um valor à direita (rhs). Você pode usar os sentidos ‘EQ’, ‘LE’, e ‘GE’ como o Docplex suporta.

# 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.export_as_lp_string())

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

Minimize
 obj: x + [ 4 x*y - 2 z^2 ]/2 + 3
Subject To
 lin_eq: x + 2 y = 3
 lin_leq: x + 2 y <= 3
 lin_geq: x + 2 y >= 3

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

Binaries
 x

Generals
 y
End

Você pode adicionar restrições quadráticas, bem como funções objetivas e restrições lineares.

# 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.export_as_lp_string())

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

Minimize
 obj: x + [ 4 x*y - 2 z^2 ]/2 + 3
Subject To
 lin_eq: x + 2 y = 3
 lin_leq: x + 2 y <= 3
 lin_geq: x + 2 y >= 3
 quad_eq: [ x^2 - y*z ] + x + y = 1
 quad_leq: [ x^2 - y*z ] + x + y <= 1
 quad_geq: [ x^2 - y*z ] + x + y >= 1

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

Binaries
 x

Generals
 y
End

Você pode acessar termos lineares e quadráticos de restrições lineares e quadráticas da mesma forma que com a função objetiva.

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

Você também pode remover restrições lineares/quadráticas usando remove_linear_constraint e remove_quadratic_constraint.

# Remove constraints
mod.remove_linear_constraint('lin_eq')
mod.remove_quadratic_constraint('quad_leq')
print(mod.export_as_lp_string())

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

Minimize
 obj: x + [ 4 x*y - 2 z^2 ]/2 + 3
Subject To
 lin_leq: x + 2 y <= 3
 lin_geq: x + 2 y >= 3
 quad_eq: [ x^2 - y*z ] + x + y = 1
 quad_geq: [ x^2 - y*z ] + x + y >= 1

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

Binaries
 x

Generals
 y
End

Você pode substituir algumas variáveis por constantes ou outras variáveis. Mais precisamente, a QuadraticProgram possui um método substitute_variables(constants=..., variables=...) para lidar com os dois casos a seguir. - \(x \leftarrow c\): quando constants tem um dicionário {x: c}. - \(x \leftarrow c y\): quando variables tem um dicionário {x: (y, c)}.

Substituindo Variáveis

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

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

Minimize
 obj: [ - 2 z^2 ]/2 + 3
Subject To
 lin_leq: - 2 z <= 3
 lin_geq: - 2 z >= 3
 quad_eq: [ z^2 ] - z = 1
 quad_geq: [ z^2 ] - z >= 1

Bounds
 -1 <= z <= 1
End

Se o problema resultante for inviável devido a limites inferiores ou limites superiores, os métodos retornam o status Status.INFEASIBLE. Nós tentamos substituir a variável x, por -1, mas -1 está fora do intervalo de x (0 <= x <= 1). Assim, ele retorna Status.INFEASIBLE.

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

Infeasible substitution for variable: x
QuadraticProgramStatus.INFEASIBLE

Não é possível substituir variáveis várias vezes. O método retorna um erro nesse 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'

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.21.0
Terra	0.15.2
Aer	0.6.1
Ignis	0.4.0
Aqua	0.7.5
IBM Q Provider	0.9.0
System information
Python	3.8.5 (default, Jul 21 2020, 10:48:26) [Clang 11.0.3 (clang-1103.0.32.62)]
OS	Darwin
CPUs	2
Memory (Gb)	8.0
Sat Sep 26 02:21:47 2020 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

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.