注釈

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

二次計画法#

はじめに#

このチュートリアルでは、Qiskit の最適化モジュールを利用して最適化問題をビルドする方法について簡単に紹介します。最適化問題のモデルを構築するために、Qiskit optimizationには 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ファイルから QuadraticProgram をロードする#

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

[1]:

from qiskit_optimization import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp

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

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

from_docplex_mp 関数を呼び出すことで、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

QuadraticProgram には包括的な文字列表現を生成するための prettyprint メソッドがあります。

[3]:

# 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

QuadraticProgram の直接的な構築#

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

[4]:

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

Problem name: my problem

Minimize
  0

Subject to
  No constraints

  No variables

QuadraticProgram は、次の3種類の変数をサポートします。

  • バイナリー変数

  • 整数変数

  • 連続変数

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

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

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

二次計画法を指定する別の方法は、配列を使用することです。一次項の場合、配列は数学的定式化のベクトル \(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.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

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

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

名前、線形式、検出、および右側の値 (rh) を設定することで、線形制約を追加できます。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.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

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

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

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

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

一部の変数を定数または他の変数に置き換えることができます。より正確には、 QuadraticProgram には、次の2つのケースを処理するためのメソッド substitute_variables(constants=..., variables=...) があります。

  • \(x \leftarrow c\) : constants が辞書 {x: c} の場合。

  • \(x \leftarrow c y\) : variables が辞書 {x: (y, c)} の場合。

変数を置き換えます#

[13]:

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

結果として生じる問題が下限または上限のために実行不可能である場合、メソッドはステータス 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'

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

[16]:

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


[17]:

import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit SoftwareVersion
qiskit-terra0.21.0.dev0+dbd3961
qiskit-aer0.10.4
qiskit-ibmq-provider0.19.1
qiskit-optimization0.4.0
System information
Python version3.10.4
Python compilerGCC 11.2.0
Python buildmain, Apr 2 2022 09:04:19
OSLinux
CPUs4
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.

[ ]: