선형 완화 문제란?

조합 최적화 에서의 혼합 정수 최적화 문제의 정수 제약을 없애고 할 수 있는 문제를 (혼합 정수 최적화 문제의) 선형 완화 문제라고 하며, 선형 최적화 문제가 됩니다.

원래 완화 문제 1이란?

원래 문제의 제약 조건의 일부 또는 전부를 삭제할 수 있는 새로운 문제를 원래 문제의 완화 문제라고 합니다.

특징

제약 조건이 없어져 실행 가능 영역이 넓어집니다. 따라서 다음과 같은 특징이 있습니다.

최대화 문제의 경우, 완화 문제의 최적해는 원래의 문제의 상계가 됩니다 (최소화라면 하계).

완화 문제의 최적해가 원래의 문제로 실행 가능한 경우, 원래의 문제의 최적해가 됩니다.

기본적으로 원래의 문제보다 풀기 쉬워집니다.

선형 완화란?

완화의 일종으로 정수 제약을 제거하는 것입니다.

(참고로) 라그랑주 완화 란 무엇입니까?

원래의 비선형 최적화 문제의 제약 조건을 제거하고 제약 조건을 위반하는 양을 페널티로 하여 목적 함수에 더해 생기는 새로운 문제를 원래 문제의 라그랑주 완화 문제라고 합니다.

적절한 페널티 가중치(라그랑주 승수)를 결정하면, 라그랑주 완화 문제의 최적해는 원래의 문제의 최적해가 됩니다.

라그랑주 완화 문제는 무제한이 되어, 이용 가능한 알고리즘이 늘어나 풀기 쉬워집니다.

다만, 혼합 정수 최적화 문제의 라그랑주 완화 문제를 생각해도 그다지 의미는 없기 때문에, 여기에서는 소개만으로 합니다.

왜 완화하는가?

예를 들어 선형 완화는 분지 한정법에서 사용됩니다.
그 밖에도, 근사해를 얻거나, 감도 분석하거나, 쌍대 정리의 증명 등으로 사용됩니다.
덧붙여 곡선의 함수를 꺾은선으로 나타내는 것은, 구분선형 근사라고 불려 완화는 아닙니다.

예제 (Napsack 문제)로 확인

쉽고 쉽게 설명할 수 있도록 3가지 변수의 혼합 정수 최적화 문제 2인 냅삭 문제를 생각해 봅시다.

혼합 정수 최적화 문제의 공식화

최대화
$7x+8y+9z$


제약
$6x+7y+8z\le 14$

$x,y,z\in\{0,1\}$

혼합 정수 최적화 문제의 솔루션 공간 및 최적 솔루션 (빨간색 점)

혼합 정수 최적화 문제의 Python에 의한 구해

파이썬

from pulp import *
m = LpProblem(sense=LpMaximize) # 数理モデル
x,y,z = [LpVariable(c,cat=LpBinary) for c in 'xyz'] # 変数
m += lpDot([7,8,9], [x,y,z]) # 目的関数
m += lpDot([6,7,8], [x,y,z]) <= 14 # 制約条件
m.solve() # 求解
print([value(v) for v in [x,y,z]]) # 出力
>>>
[1.0, 0.0, 1.0]

선형 완화 문제의 공식화

최대화
$7x+8y+9z$


제약
$6x+7y+8z\le 14$

$x,y,z\ge 0, ~~\le 1$

선형 완화 문제의 해 공간과 최적 해 (빨간 점)의 그림

선형 완화 문제의 Python에 의한 구해

파이썬

from pulp import *
m = LpProblem(sense=LpMaximize) # 数理モデル
x,y,z = [LpVariable(c,lowBound=0,upBound=1) for c in 'xyz'] # 変数
m += lpDot([7,8,9], [x,y,z]) # 目的関数
m += lpDot([6,7,8], [x,y,z]) <= 14 # 制約条件
m.solve() # 求解
print([value(v) for v in [x,y,z]]) # 出力
>>>
[1.0, 1.0, 0.125]

이상



정식화된 물건을 모델이라고 부르면 완화 문제가 아니라 완화 모델이라고 하고 싶은 곳입니다. ↩

혼동이 적고 방법으로, 냅삭 문제는 정수 최적화 문제가 됩니다. 여기에서는, 보다 범용적인 혼합 정수 최적화 문제에 대해서 성립하는 설명이므로, 굳이 이렇게 하고 있습니다. ↩