13. Linear Programming

1. Brewer's problem

 

Brewer's problem은, 맥주공장에서 한정된 자원을 가지고 어떻게 맥주와 에일을 생산해야 최대의 이익을 올릴 수 있는지 결정하는 문제이다. 자원은 이미 한정되어 있고, 맥주와 에일을 1개 생산하는 데는 특정 수치의 자원의 조합을 투입해야 한다.

 

예를 들어, 자원 X가 480, Y가 160, Z가 1190개가 있다고 해보자.

맥주 A를 만드는데는 X, Y, Z가 각각 5, 4, 35개가 필요하다.

에일 B를 만드는데는 X, Y, Z가 각각 15, 4, 20개가 필요하다.

맥주 A는 개당 13달러의 이윤을, 에일 B는 23달러의 이윤을 남기고, 이윤을 최대화 하고 싶다.

 

이를 A는 맥주 생산량, B는 에일 생산량 변수로 하여 방정식으로 표현하면 다음과 같다.

최대화 하고싶은 값은 Object function으로 표현한다.

Objective function은 다음과 같다.

13A + 23B

Constraint는 다음과 같다.

5A + 15B <= 480

4A + 4B <= 160

35A + 20B <= 1190

A, B >= 0

 

고등수학을 배웠으면 알 수 있듯이 이것은 2차원평면에서 그래프의 영역으로 표현된다.

A를 x축, B를 y축으로 하여 대충 그림으로 그리면 아래 영역이다...

 

 

Objective function이 최대가 되는 지점은 13A + 23B = K 일 때, K가 최대가 되는 지점이므로 Y절편이 최대가 되는 지점이다. Objective function이 변수의 선형합의 형태일 때, 최대가 되는 지점은 이러한 convex polygon의 extreme point이다.

우리는 따라서, 영역내의 모든 값이 아닌 extreme point만을 조사하면된다.

 

참고로 extreme point란, convex polygon에서 임의의 2점 a, b를 선택했을 때, 두 점 사이의 점인 1/2(a+b)로서 구할 수 없는 않은 점을 말한다. 최적해의 존재성은 한개의 extreme point의 존재성을 보장한다.

여기서 extreme point는 유한한 갯수이지만, 주어진 변수 n개에 따라 exponential하게 증가한다.

생각해보자. 변수가 2개인 2차원의 평면에서 하나의 constraint는 직선으로 표현되고, 이것을 추가하는 것은 기존의 한 extreme point를 2개의 extreme point로 늘리는 역할을 할 수 있다. 

변수가 3개인 3차원에서는 하나의 constraint는 평면으로 표현될 수 있고, 이것을 추가하는 것은 모서리부분을 잘랐을 때 extreme point를 3개의 extreme point로 늘리는 역할을 할 수 있다. 4차원, 5차원으로 갈 수록 하나의 constraint의 추가는 더 많은 extreme point를 생산할 것이다.

Objective function의 변수가 많아질수록 차원이 높아지고 extreme point의 갯수도 변수n에 대해 exponential하게 증가한다.

 

먼저, 특정 문제를 풀기 위해 우리는 이것을 Standard form으로 변환해주어야 한다.

Standard form은 다음과 같다(행렬식으로 표현하는게 깔끔하긴하다).

출처 : cousera, Princeton University Algorithm part2 lecture

 

변환하면 아래와 같은 형태가 된다.

 

Z          // maximize

 

13A + 23B - Z = 0 

5A + 15B + Sx = 480

4A + 4B + Sy = 160

35A + 20B  + Sz = 1190

A, B, Sx, Sy, Sz >= 0 

 

부등식을 등식으로 만들기 위해, slack variable을 추가한다.

6차 방정식이고, 등식은 4개이므로, 4개 차원이 고정되었을 때 constraint내부에서 2개 차원이 자유롭게 움직일 수 있다... 

 

2. Simplex Algorithm

 

Simplex Algorithm은 위에서 Standard form으로 변환된 식에서, slack variable인 Sx, Sy, Sz를 basis로 설정함으로서 시작한다. 여기서 basis란 n개 변수 중에 선택된 m개의 변수집합을 의미한다. 여기서는 n = 6이고, m개 변수집합은 {Sx, Sy, Sz} 이다. basis를 제외한 변수는 0으로 설정한다. 

2개차원 A, B가 0의 값으로 고정되었으므로, 4개차원의 값은 결정된다. Sx = 480, Sy = 160, Sz = 1190, Z = 0

 

다음으로, Bland's rule과 같은 방법으로 pivot이 될 변수(column)를 결정한다.

Bland's rule로 구현했다고 가정하고, Z가 들어가있는 식에서 계수가 양수인 부분을 선택하므로 여기서는 13A + 23B - Z 에서 A, B 둘다 선택할 수 있는데, B를 선택했다고 가정한다.

 

다음으로, Minimum ratio rule에 의해 pivot이 될 constraint(row)를 결정한다.

현재 15B, 4B, 20B 중에 선택해야 하는데, 목적함수는 23B가 증가하는 것을 가장 크게 제한하는 값은 15B이다. 왜냐하면 B만 생산한다고 가정했을 때, 15B = 480 으로 B를 점진적으로 증가시켰을 때 가장 먼저 걸리는 constraint이기 때문이다.

구하는 방식은 min{480/15, 160/4, 1190/20} 으로 480/15가 가장 작으므로 15B가 pivot으로 최종 선택된다.

 

B = (1/15)(480 - 5A - Sc) 이므로, 이 값을 다른 constraint에 넣어서 B변수를 치환한다.

식은 다음과 같이 변환된다.

 

(16/3)A - (23/15)Sx - Z = -736

(1/3)A + B + (1/15)Sx = 32

(8/3)A  - (4/15)Sx + Sy = 32

(85/3)A - (4/3)Sx + Sz = 550

 

위 식에서 basis를 B, Sy, Sz로 설정할 수 있다. 나머지 변수 A, Sx는 0이므로  B = 32, Sy = 32, Sz = 550, Z = 736이다.

그리고 위와 같은 방법으로 pivot이 선택되지 않을 때까지 반복한다.

현재 A변수의 계수가 양수이고, Minimum ratio rule에 따르면 (8/3)A가 pivot으로 선택된다.

A = (3/8)(32 + (4/15)Sx - Sy)이므로 각 constraint를 치환하면, 최종적으로 Z를 포함한 식은 다음과 같다.

 

- Sx - Sy - Z = -800

 

더 이상 양수계수가 없으므로, 알고리즘을 종료한다. A, B, Sz가 basis이고 Sx, Sy는 0이다. 

Objective function의 최댓값은 800이다. 이 값은 Optimal value이다.

 

3. Implemenataion

 

구현은 기본적으로 방정식들을 유지하기 위해 2D-Array를 생성하여 활용한다.

물론 0이 많다는 가정하에 앞에서 배운 linked-list를 활용할 수도 있다.

 

constraint의 갯수가 m이고, 목적함수의 변수가 n개라고 했을 때 row의 갯수는 m + 1 이고, column의 갯수는 m + n 이다.

실제의 알고리즘 실행시에 실행은 기껏해야 2(m+n)의 pivots에 대해 알고리즘을 실행 후에 끝난다.

 

하지만 아직까지 어떠한 pivot rule도 polynomial한 실행을 보장하지 않는다. 대부분의 pivot rule이 worst-case에서 exponential하게 동작한다. 

Simplex Algorithm의 경우 같은 새로운 basis를 선택하였지만, 여전히 같은 extreme point를 선택하게되는 문제가 생길 수 있다. 이외에도 입력값에 따라 알고리즘 실행시에 실행시간을 늦춰질 수 있는 여러가지 고려사항이 있고, 이를 개선하는 여러 개선된 알고리즘이 있다.

 

4. Reductions

 

Linear Algorithm이 최고의 성능을 보장하지 않음에도 유용한 이유는, 엄청나게 많은 문제들이 reduction을 통해 Linear programming model로 변환될 수 있기 때문이다. 이것은 굉장히 General한 Model이다.

max flow, shortest path, bipartite matching 등등 이전에 공부했던 수많은 알고리즘이 Linear programming model로 변환 될 수 있다.

 

변환의 과정은 다음과 같다.

1) Identify variables

2) Define constraints (inequalities and equations)

3) Define objective function

4) Convert to statndard form

 

1, 2, 3번의 과정은 우리가 해야 하지만, 4번의 과정은 변환하는 수많은 구현들이 있다.

참고로 이것을 직접 구현하지 않고 이미 구현된 것을 사용하도록 하자...

문제가 복잡해질수록, 특정 알고리즘으로 해결하기 어려운 것들이 많고, 이것을 Linear programming model로 변환할 수 있다면 물론 시간을 오래걸릴 수도 있지만, 해결가능할 수 있다.

 

지금까지 수많은 알고리즘 개선이 있어왔고, 그에 따라서 수많은 Linear programming model로 변환되어 풀어온 문제들이 더욱더 빠른 시간내에 풀 수 있게 되어졌다.