Korean
언어
English
Japanese
German
Korean
Portuguese, Brazilian
French
Table of Contents
  • Docs >
  • 이차계획법 문제
Shortcuts

참고

이 페이지는 `tutorials/optimization/1_quadratic_program.ipynb`_ 에서 생성되었다.

IBM 퀀텀 랩 에서 대화식으로 실행하시오.

이차계획법 문제

소개

본 사용 지침서에서는 키스킷의 최적화 모듈을 사용하여 최적화 문제를 빌드하는 방법을 간략하게 소개할 것이다. 키스킷은 최적화 문제의 모델을 생성하기 위하여 QuadraticProgram 클래스를 소개한다. 엄밀히 말하자면, QuadraticProgram 은 목적함수와 제약조건이 모두 이차 식으로 주어진 문제들 (quadratically constrained quadratic programs) 을 다룬다. 예를 들어, 다음과 같이 주어진 문제에서:

\[\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\) 는 바이너리, 정수, 혹은 연속한 변수들로 정의된다. QuadraticProgram 클래스는 “\(\leq\)” 뿐만 아니라 “\(\geq\)” 과 “\(=\)” 제약조건까지도 지원한다.

LP (Linear Program) 파일에서 Quadratic Program 을 불러오기

초기 설정을 위하여, 아래와 같이 모듈을 불러와야 한다.

[1]:

from qiskit.optimization import QuadraticProgram

비어 있는 모델에서 시작한다. 모델에 변수와 제한조건을 추가하는 방법에 대해서는 “ QuadraticProgram 을 사용하여 직접 모델을 세워보기” 섹션에서 설명할 것이다.

키스킷의 최적화 모듈은 Docplex 모델과의 변환을 지원한다. Docplex를 활용하면 쉽게 최적화 문제의 모델을 생성할 수 있다. Docplex 문서는 여기 https://ibmdecisionoptimization.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 은 다음의 세 가지 변수 유형을 지원한다: - 바이너리 변수 - 정수 변수 - 연속형 변수

변수를 추가할 때, 변수의 이름, 유형, 하계(lower bound), 상계(upper bound) 를 지정할 수 있다.

당신의 최적화 문제가 LP 형식으로 표시될 때, Binaries 는 바이너리 변수들을 나타내고, Generals 는 정수형 변수들을 나타낸다. 만약 Binaries 와 Generals 둘 중에 어디에도 속하지 않는 변수들이 있다면, 이와 같은 변수들은 하계 = 0이고 상계 = 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 를 호출하여 목적함수를 설정할 수 있다. 리스트, 행렬, 혹은 딕셔너리 자료형을 사용해 선형 항과 이차 항을 지정함으로서 상수 항을 추가할 수 있을 뿐만 아니라 선형 목적함수와 이차 목적함수를 추가할 수 있다.

LP 형식에 따라 이차 항은 스케일 팩터 \(1/2\) 로 스케일링 되어야 한다는 점을 유의하시오. 따라서 LP 형식에 따라 출력할 때, 이차 항에 먼저 2를 곱한 후 2로 나누게 된다.

이차 계획법 문제에서는 다음의 3가지 요소가 명시되어야 한다: 상수 항 (offset), 선형 항(\(c^{T}x\)), 이차 항(\(x^{T}Qx\)).

아래의 셀 (cell) 은 딕셔너리 자료형을 사용하여 목적함수를 선언하는 방법을 보여준다. 선형 항의 경우, 자료형의 키 (key) 는 변수 이름에 대응되며 자료형의 값 (value) 은 계수에 대응된다. 이차 항의 경우, 키는 곱한 두 변수를 나타내며, 마찬가지로 값은 계수에 대응된다.

[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} 를 출력함으로써 상수 항, 선형 항, 이차 항에 각각 액세스 (access) 할 수 있다. 선형 항과 이차 항을 출력하고자 할 때는 밀집 행렬(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

선형 제약조건과 이차 제약조건을 추가/제거하기

이름, 선형 표현식, 민감도 (sense), 우변 (right-hand-side valuel; rhs) 을 설정함으로써 선형 제약조건을 추가할 수 있다. 민감도의 경우 Docples는 ‘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

목적함수에 액세스(access) 했던 방법을 그대로 사용하여 선형 제약조건의 선형 항과 이차 제약조건의 이차 항에 각각 액세스할 수 있다.

[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

상계 혹은 하계의 제약조건을 만족할 수 없는 불가능 (infeasible) 상태에서, 해당 메서드는 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.

[ ]:

© Copyright 2021, Qiskit Development Team. 최종 업데이트: 2021/06/04

Built with Sphinx using a theme provided by Read the Docs.