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

注釈

このページは tutorials/optimization/1_quadratic_program.ipynb から生成されました。

IBM Quantum lab でインタラクティブに実行します。

二次計画法

はじめに

このチュートリアルでは、Qiskit の最適化モジュールを利用して最適化問題をビルドする方法について簡単に紹介します。最適化問題のモデルを構築するために、Qiskit には QuadraticProgram クラスが導入されています。より正確には、次のような二次制約二次計画問題を扱います。

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

ここで、 \(Q_i\) は \(n \times n\) 行列、 \(A\) は \(m \times n\) 行列、 \(x\) 、 \(c\) は \(n\) 次元ベクトル、 \(b\) は \(m\) 次元ベクトル、 \(x\) はバイナリ、整数、または連続変数として定義できます。“\(\leq\)”制約に加えて、 ‘QuadraticProgram’ は “\(\geq\)” と “\(=\)” もサポートします。

LPファイルから Quadratic Program をロードする

セットアップとして、以下のモジュールをインポートする必要があります。

[1]:

from qiskit.optimization import QuadraticProgram

空のモデルから始めます。モデルに変数と制約を追加する方法については、「 QuadraticProgram の直接的な構築」セクションで説明します。

Qiskitの最適化モジュールはDocplexモデルからの変換をサポートしています。Docplexで簡単に最適化問題のモデルを作成できます。 Docplex のドキュメントは https://ibmdecisonoptimization.github.io/docplex-doc/mp/index.html にあります。

from_docplex を呼び出すことで、Docplex モデルを QuadraticProgram に読み込むことができます。

docplex モデルから QuadraticProgram をロードする

[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

QuadraticProgram の直接的な構築

次に、QuadraticProgram を使用して最適化問題のモデルを直接作成する方法を説明します。空のモデルから始めましょう。

[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

QuadraticProgram は3種類の変数をサポートしています: - バイナリー変数 - 整数変数 - 連続変数

変数を追加する際には、名前、タイプ、下限、上限を指定できます。

問題をLP形式で表示する場合、Binaries はバイナリー変数を、Generals は整数変数を表します。 変数が Binaries または Generals に含まれていない場合、 このような変数は、デフォルトの lower bound = 0、upper bound = infinity を持つ連続変数です。 LPフォーマットの規定 により、名前の最初の文字として ‘e’ または ‘E’ を使用することはできませんのでご注意ください。

[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

QuadraticProgram.minimize または QuadraticProgram.maximize を呼び出すことにより、目的関数を設定できます。リスト、行列、または辞書のいずれかで線形項と2次項を指定することにより、定数項と線形および2次の目的関数を追加できます。

LP形式では、二次部分を \(1/2\) 倍にスケーリングする必要があることに注意してください。したがって、LP形式で印刷する場合、二次部分は最初に2で乗算され、次に2で除算されます。

二次計画法の場合、指定する必要があるのは、定数（オフセット）、線形項（ \(c^{T}x\) ）、および二次項（ \(x^{T}Qx\) ）の3つです。

以下のセルは、辞書を使用して目的関数を宣言する方法を示しています。線形項の場合、辞書のキーは変数名に対応し、対応する値は係数です。二次項の場合、辞書のキーは乗算される2つの変数に対応し、値は再び係数になります。

[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

二次計画法を指定する別の方法は、配列を使用することです。 一次項の場合、配列は数学的定式化のベクトル \(c\) に対応します。 二次項の場合、配列は行列 \(Q\) に対応します。変数の順序（数学的定式化では \(x\) ）は、変数が 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

Quadratic.objective.{constant, linear, quadratic} をそれぞれ調べることで、定数、線形項、および二次項にアクセスできます。線形および二次項については、密行列（ to_array ）、疎行列（ coefficients ）、および辞書（ to_dict ）を取得できます。辞書の場合、変数インデックスまたは名前をキーとして使用するかどうかを指定できます。二次項は圧縮された方法で格納されることに注意してください。たとえば、 {('x', 'y'): 1, ('y', 'x'): 2} は {('x', 'y'): 3} として格納されます。 to_array(symmetric=True) または to_dict(symmetric=True) を呼び出すことにより、二次項を対称行列として取得できます。 to_dict(name=True) を呼び出すと、キーが変数名のペアである辞書を取得できます。

[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

線形および二次制約の追加/削除

名前(name)、線形式(linear)、検出(sense)、および右側の値 (rhs) を設定することで、線形制約を追加できます。Docplexのサポートとして、 ‘EQ’, ‘LE’, ‘GE’ の検出が使用できます。

[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

二次制約だけでなく、目的関数や線形制約も追加できます。

[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

目的関数と同じ方法で、線形および二次制約の線形および二次項にアクセスできます。

[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

また、 remove_linear_constraint と 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)}.

変数を置き換えます

[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

結果として生じる問題が下限または上限のために実行不可能である場合、メソッドはステータス Status.INFEASIBLE を返します。変数 x を -1 に置き換えようとしましたが、-1 は x (0 <= x <= 1)の範囲外です。したがって、 Status.INFEASIBLE を返します。

[14]:

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

Infeasible substitution for variable: x
QuadraticProgramStatus.INFEASIBLE

変数を複数回置換することはできません。メソッドはそのような場合にエラーを発生させます。

[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.

[ ]: