French
Langues
English
Japanese
German
Korean
Portuguese, Brazilian
French
Table of Contents
Shortcuts

Note

Cette page a été générée à partir de tutorials/optimization/1_quadratic_program.ipynb.

Exécuter en mode interactif dans le ` IBM Quantum lab <https://quantum-computing.ibm.com/jupyter/tutorial/optimization/1_quadratic_program.ipynb>` _.

Programmes quadratiques

Introduction

Dans ce tutoriel, nous vous présentons brièvement comment construire des problèmes d’optimisation à l’aide du module d’optimisation de Qiskit. Qiskit introduit la classe QuadraticProgram pour construire un modèle d’un problème d’optimisation. Plus précisément, il traite des programmes quadratiques à contraintes quadratiques données comme suit :

\[\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}\]

where the \(Q_i\) are \(n \times n\) matrices, \(A\) is a \(m \times n\) matrix , \(x\), and \(c\) are \(n\)-dimensional vectors, \(b\) is an \(m\)-dimensional vector, and where \(x\) can defined as binary, integer, or continuous variables. In addition to “\(\leq\)” constraints ‘QuadraticProgram’ also supports “\(\geq\)” and “\(=\)”.

Chargement d’un Quadratic Program depuis un fichier LP

Pour préparer votre station de travail vous devez importer le module suivant.

[1]:

from qiskit.optimization import QuadraticProgram

Vous commencez par un modèle vide. L’ajout de variables et de contraintes à un modèle est expliqué dans la section « Construction directe d’un QuadraticProgram.

Le module d’optimisation de Qiskit prend en charge la conversion à partir du modèle Docplex. Vous pouvez facilement créer un modèle pour un problème d’optimisation avec Docplex. Vous trouverez la documentation de Docplex à l’adresse https://ibmdecisionoptimization.github.io/docplex-doc/mp/index.html

Vous pouvez charger un modèle Docplex vers le QuadraticProgram en appelant from_docplex.

Chargement d’un ` ` QuadraticProgram ` ` à partir d’un modèle docplex

[2]:

# 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


[3]:

# 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

Construction directe d’un QuadraticProgram

Nous expliquons ensuite comment modéliser un problème d’optimisation directement en utilisant le QuadraticProgram. Commençons à partir d’un modèle vide.

[4]:

# 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

Le programme ` ` QuadraticProgram ` ` prend en charge trois types de variables : -Variable binaire -Variable de type entier -Variable continue

Lorsque vous ajoutez des variables, vous pouvez spécifier des noms, des types, des bornes inférieures et supérieures.

Lorsque vous affichez votre problème sous forme de format LP, Binaries indique des variables binaires et Generals indique les variables entières. Si les variables ne figurent pas dans Binaries ou Generals, ces variables sont continues avec 0 comme limite inférieure par défaut, et l’infinité comme limite supérieure. Notez que vous ne pouvez pas utiliser “e” ou “E” comme premier caractère des noms en raison de la spécification du format LP <https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/FileFormats/topics/LP_VariableNames.html>` __.

[5]:

# 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

Vous pouvez définir la fonction objectif en appelant QuadraticProgram.minimize ou QuadraticProgram.maximize. Vous pouvez ajouter un terme constant ainsi qu’une fonction objectif linéaire ou quadratique en spécifiant des termes linéaires et quadratiques avec une liste, une matrice ou un dictionnaire.

Notez que dans le format LP, la partie quadratique doit être réduite par un facteur :math:` 1/2`. Ainsi, lors de l’affichage du résultat en format LP, la partie quadratique est d’abord multipliée par 2, puis divisée par 2.

Pour les programmes quadratiques, trois paramètres doivent être spécifiées: une constante (décalage), un terme linéaire (:math:` c ^{T}x ), et un terme quadratique (:math: x ^{T}Qx `).

La cellule ci-dessous montre comment déclarer une fonction objectif à l’aide d’un dictionnaire. Pour le terme linéaire, les clés du dictionnaire correspondent aux noms de variables, et les valeurs correspondantes sont les coefficients. Pour le terme quadratique, les clés du dictionnaire correspondent aux deux variables étant multipliées, et les valeurs sont à nouveau les coefficients.

[6]:

# 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

Une autre façon de spécifier le programme quadratique consiste à utiliser des tableaux. Pour le terme linéaire, le tableau correspond au vecteur \(c\) dans la formulation mathématique. Pour le terme quadratique, le tableau correspond à la matrice \(Q\). Notez que l’ordre des variables (\(x\) dans la formulation mathématique) est l’ordre dans lequel les variables ont été déclarées à l’origine dans l’objet QuadraticProgram.

[7]:

# 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

Vous pouvez accéder au terme constant, au terme linéaire et au terme quadratique en regardant respectivement Quadratic.objective.{constant, linear, quadratic}. Pour ce qui est des termes linéaires et quadratiques, vous pouvez obtenir une matrice dense (to_array), une matrice éparse (coefficients) et un dictionnaire (to_dict). Pour les dictionnaires, vous pouvez spécifier si vous devez utiliser des indices variables ou des noms comme clés. Notez que les termes quadratiques sont stockés de manière compressée, par exemple {('x', 'y'): 1, ('y', 'x'): 2} est stocké sous la forme {('x', 'y'): 3}. Vous pouvez obtenir le terme quadratique en tant que matrice symétrique en appelant to_array(symmetric=True) ou to_dict(symmetric=True). Si vous appelez to_dict(name=True), vous pouvez obtenir un dictionnaire dont les clés sont des paires de noms de variables.

[8]:

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

Ajout/suppression des contraintes linéaires et quadratiques

Vous pouvez ajouter des contraintes linéaires en définissant le nom, l’expression linéaire, le sens et la valeur côté droit (rhs). Vous pouvez utiliser les sens “EQ”, “LE” et “GE” comme supports Docplex.

[9]:

# 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

Vous pouvez ajouter des contraintes quadratiques ainsi que des fonctions objectives et des contraintes linéaires.

[10]:

# 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

Vous pouvez accéder à des termes linéaires et quadratiques de contraintes linéaires et quadratiques de la même manière que la fonction cible.

[11]:

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

Vous pouvez également supprimer les contraintes linéaires/quadratiques par remove_linear_constraint et remove_quadratic_constraint.

[12]:

# 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

You can substitute some of variables with constants or other variables. More precisely, QuadraticProgram has a method substitute_variables(constants=..., variables=...) to deal with the following two cases. - \(x \leftarrow c\): when constants have a dictionary {x: c}. - \(x \leftarrow c y\): when variables have a dictionary {x: (y, c)}.

Substitution des variables

[13]:

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

S’il n’est pas possible de résoudre le problème résultant en raison de bornes inférieures ou de bornes supérieures, la méthode renvoie le statut Status.INFEASIBLE. Nous essayons de remplacer la variable x par -1, mais -1 n’est pas comprise dans la plage de x (0 < = x < = 1). Donc, il retourne ``Status.INFEASIBLE ``.

[14]:

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

Infeasible substitution for variable: x
QuadraticProgramStatus.INFEASIBLE

Vous ne pouvez pas substituer plusieurs fois les variables. La méthode renvoie une erreur dans ce cas.

[15]:

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'

[16]:

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit SoftwareVersion
Qiskit0.21.0
Terra0.15.2
Aer0.6.1
Ignis0.4.0
Aqua0.7.5
IBM Q Provider0.9.0
System information
Python3.8.5 (default, Jul 21 2020, 10:48:26) [Clang 11.0.3 (clang-1103.0.32.62)]
OSDarwin
CPUs2
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.

[ ]: