최단 경로나 최소 비용 신장 트리(cheapest spanning tree), 최장 증가 부분 수열(longest increasing subsequence)와 같은 알고리즘들에 대한 많은 문제들은 최적화(optimization) 작업들입니다. 이와 같은 경우, (1) 특정 제약(예를 들어, 경로는 반드시 그래프의 간선을 사용해야 하고, s에서부터 t로 이동해야 하며 트리의 모든 노드를 지나야 한다)을 만족하고, (2) 잘 정의된 기준에 부합하면서 이들 제약들을 만족하는 모든 솔루션 가운데 가장 최적의 솔루션을 찾습니다.
선형 계획법(Linear Programming)은 제약들과 최적화 기준이 선형 함수(linear function)가 되는 최적화 작업의 넓은 부류를 의미합니다. 그리고, 많은 수의 문제들이 선형 계획법으로 표현될 수 있다는 것이 밝혀졌습니다.
선형 계획법이라는 주제는 엄청 방대한데, 아래의 주제들에 대해서 살펴보도록 하겠습니다. 평소 포스팅하던 알고리즘과는 다른 개념적인 내용들에 대해 주로 다루게 될 것 같습니다.. !
(아마 하나의 포스팅으로 끝내지는 못할 것 같네요..)
An Introduction to Linear Programming
선형 계획법 문제에서는 변수들의 집합이 주어지고, (1) 이 변수를 포함하는 선형 방적식 및(또는) 선형 부등식들을 만족하고 (2) 주어진 선형 목적 함수(linear objective function)을 최대화 또는 최소화하기 위해 변수에 실제 값들을 할당됩니다.
그럼 몇 가지 예제들을 통해 자세히 알아보도록 하겠습니다.
Example: Profit Maximization
어느 상점에서 두 개의 상품 A와 B를 가지고 있다고 가정해봅시다. 여기서 이익을 최대화하기 위해 각 상품을 얼마나 생산해야 할까요? 개당 1달러인 A 상품을 하루에 \(x_1\) 박스를 만들고, 개당 6달러인 B 상품을 하루에 \(x_2\) 박스를 만든다고 해봅시다. 여기서 \(x_1\)과 \(x_2\)는 우리가 결정하고자 하는 미지의 값 입니다. 다만, 이것이 전부가 아닙니다. 여기에는 \(x_1\)와 \(x_2\)에 대한 몇 가지 제약이 존재합니다 (명백한 제약 조건인 \(x_1, x_2 \geq 0\) 제외).
첫째, 상품 A에 대한 일일 수요는 최대 200 박스로 제한되고 상품 B에 대한 일일 수요는 최대 300 박스로 제한됩니다.
둘째, 현재 생상 능력에 따라 하루에 A,B 모두 포함하여 400 박스의 상품만 생산할 수 있습니다.
여기서 최적의 \(x_1\)과 \(x_2\)는 무엇일까요?
선형 계획법에 의해서, 위 문제를 식으로 표현하면 다음과 같습니다.
\(x_1\)과 \(x_2\)의 선형 방적식은 2차원 평면에서 직선으로 정의됩니다. 그리고 선형 부등식은 직선의 half-space를 명시합니다. 따라서, 선형 계획법의 모든 가능한 해답의 집합, 즉 모든 제약을 만족하는 점 (\(x_1\), \(x_2\))는 5개의 half-space의 교집합이 됩니다. 이는 아래 그림에서 나타난 것과 같이 볼록 다각형(convex polygon)입니다.
(a) The feasible region for a linear program. (b) Contour lines of the objective function: \(x_1\) + 6\(x_2\) = c for different values of the profit c.
이때 목적 함수, 즉 이익이 최대가 되는 곳에서 이 다각형의 포인트를 발견하길 원합니다. 이익이 c 달러인 점들은 직선 \(x_1 + 6x_2 = c\) 상에 놓이게 됩니다. 이 직선은 기울기가 \(-\frac{1}{6}\)이고, 선택된 c의 값에 대해 위의 그림에서 보는 것과 같습니다. 위 그림의 오른쪽 이미지에서 c가 증가함으로써 이 직선은 위쪽으로 평행 이동합니다. 목적은 c를 최대화하는 것이기 때문에, 적합한 구역에 도달할 때까지 가능한 위쪽으로 멀리 직선을 이동시켜야 합니다. 만약 이 직선의 기울기가 다르다면, 이때 다각형과 마지막으로 접촉하는 부분은 단일 정점(포인트)이 아닌 모서리(edge)와 일치할 수 있습니다. 이 경우에는 최적의 솔루션이 유일하지는 않지만 확실하게 최적의 포인트가 될 수는 있습니다.
가능한 구역(feasible region)에서의 정점에서 얻을 수 있는 최적(optimum)은 선형 계획의 일반적인 룰 입니다. 예외는 오직 최적이 없는 경우 입니다. 이러한 경우는 아래의 두 가지 방법에서 나타날 수 있습니다.
선형 계획법이 실행 불가능하다. 즉, 제약들이 너무 엄격하여 모두 만족시키기 불가능한 경우. 예를 들면, 다음의 제약과 같다. \[x \leq 1, x \geq 2\]
가능한 구역의 경계가 없을 정도로 제약이 너무 느슨하다. 따라서 임의의 높은 목적 값을 얻을 수 있다. 예를 들면 다음과 같다. \[\begin{matrix} \text{max }x_1 + x_2 \\ x_1, x_2 \geq 0 \end{matrix}\]
Solving Linear Programs
선형 계획법(LPs)는 1947년 George Dantzig에 의해 고안된 심플렉스법(simplex method)을 사용하여 해결될 수 있습니다. 이 방법은 뒤에서 자세하게 살펴볼텐데, 일단 간단히 설명하면 이 알고리즘은 한 정점(여기서는 아마도 (0,0))에서 출발하고, 더 좋은 목적값(objective value)의 인접한 정점(feasible region의 간선(모서리)에 연결된)을 반복적으로 찾습니다. 다각형의 정점에서 언덕을 오르는 것과 같은 방법처럼 길을 따라 꾸준하게 이익을 증가시킵니다. 아래 그림은 이 방법을 통해 최대 이익을 찾아나가는 경로를 보여줍니다.
찾아나가다가 더 좋은 이웃을 갖지 않는 정점에 도달하자마자 그 값을 최적이라고 선택하고 멈춥니다. 여기서 의문은 왜 이와 같은 지역적인 검사(local test)가 전역(global)의 최적성이라는 것을 내포할까요?
단순한 기하학으로, 이 정점을 통과하는 profit line을 생각해봅시다. 꼭지점의 모든 이웃들이 선 아래쪽에 위치하고 때문에 feasible region에서 나머지 이웃들은 선 아래에 위치해야 합니다.
More Products
소비자들의 요구에 의해 판매자가 매우 한정적인 C라는 상품을 생산하기로 결정했다고 합시다. C 상품은 한 박스에 13달러라고 가정합니다. 이때, \(x_1, x_2, x_3\)를 하루에 생각되는 각 A, B, C 상품의 박스 수라고 합니다. 여기서 \(x_3\)은 C의 박스 수가 됩니다. 그리고 비록 \(x_3\)이 추가되었지만, \(x_1, x_2\)에 대한 제약은 이전과 동일하게 유지합니다. 따라서, 세 변수들의 합은 최대 400이 됩니다. 추가로 상품 C는 상품 B와 동일한 포장 기계를 사용하지만, 상품 C를 포장하는데 B에 걸리는 시간보다 3배 더 걸린다고 가정합니다. 그러면 여기서 또 다른 제약인 \(x_2 + x_3 \leq 600\)이 추가됩니다. 여기서 최적의 솔루션은 무엇일까요?
선형 계획법에 의해 위 문제는 다음과 같이 표현됩니다.
솔루션의 공간은 이제 3차원입니다. 각 선형 방정식은 3D 평면에 정의하고 한쪽 평면에 각각 부등식에 의한 half-space를 정의합니다. 여기서 가능한 공간은 7개 half-space의 교집합, 즉, 아래 그림과 같이 다면체가 됩니다.
The feasible polyhedron for a three-variable linear program.
이제 이익인 c는 평면 \(x_1 + 6x_2 + 13x_3 = c\)에 대응됩니다. c가 증가함으로써, 이 이익 평면(profit-plane)은 feasible region에 위치하지 않을 때까지 양의 사분면 내로 점점 더 평행으로 이동합니다. 최종 접촉점이 최적이 정점이 되며, 여기서는 (0, 300, 100)이 되어 총 이익은 3100 달러가 됩니다.
심플렉스법이 위 문제에서 어떻게 동작될까요? 이전과 같이, 꾸준하게 이익을 증가시키면서 다면체의 간선들 사이의 정점에서 정점으로 이동합니다. 가능한 경로는 위의 그림에서 보여주고 있으며, 아래에서 보여주는 정점과 이익들의 순서를 따라 이동합니다.
이동하다가, 마지막으로 더 좋은 이웃을 갖지 않는 정점에 도달하자마자 이동을 멈추고 도달한 정점을 최적의 정점이라고 결정합니다.
만약 상품이 하나 더 추가되면 어떨까요? 그러면 문제는 4차원이 되고 시각화하기 어렵습니다. 비록 위의 문제에서는 설명하기 위해 단순 기하학적인 측면에서 살펴볼 수 있도록 저차원의 예제로 살펴봤지만, 이러한 기하하적인 직관에 의존하지 않더라도 심플렉스법은 4차원 이상의 문제를 해결할 수 있습니다.
쌍대(Duality)라 불리는 magic trick 위의 A,B,C 상품에 대한 문제에서 총 이익이 3100 달러인 (0, 300, 100)이 최적이라고 결정한 이유가 바로 여기에 있습니다. 다시 선형 계획법을 살펴봅시다. 위에서 표현한 식에서 두 번째 항등식과 세 번째 항등식을 더한 결과를, 네 번째 항등식에 4를 곱하여 더해봅시다. 그 결과 아래의 항등식이 계산됩니다. \[x_1 + 6x_2 + 13x_3 \leq 3100\]
즉, 이 항등식은 3100보다 큰 이익을 가지는 솔루션이 없다는 것을 말합니다. 따라서 우리는 실제로 최적값을 찾았습니다. 여기서 유일한 의문은 4가지 부등식에 대한 이 불가사의한 승수(multiple) (0, 1, 1, 4)(4개의 부등식에 더할 때 곱하는 숫자들)를 어디에서 얻을 수 있을까요?
이번 포스팅이나 다음 포스팅에서 다른 선형 계획법(LP)을 풀어보면서 이 불가사의한 승수를 찾는 것이 항상 가능하다는 것을 살펴볼 예정입니다. 그리고 사실 원래의 LP(이를 dual이라고 함)와 매우 밀접하게 연관되어 있기 때문에 원래의 LP를 해결하면 dual로 해결됩니다. 자세한 내용은 뒤에서 살펴보도록 하겠습니다.
Example: Production Planning
어느 한 회사가 계절 상품인 손으로 짠 카페트를 생산한다고 합시다. 회사의 분석가는 다음 연도의 모든 달에 요구되는 견적 \(d_1, d_2, \cdots, d_n\)을 얻었다고 가정합니다. 다만, 걱정되는 것은 이 견적이 440에서 920까지 불규칙적이라는 것입니다.
회사의 상황을 살펴봅시다. 이 회사는 현재 30명의 직원이 있으며, 각 직원은 한달에 20개의 카페트를 생산하며 2000달러의 월급을 받습니다. 그리고 카페트의 초기 재고는 없습니다.
이러한 상황에서 어떻게 수요에 대한 변동성을 처리할까요? 일단 여기에는 3가지의 방법이 있습니다.
초과 근무(overtime), 단 초과 근무는 일반 수당보다 80% 더 많기 때문에 비용이 많이 듭니다.
고용과 해고. 하지만 이 비용은 직원 한 명당 각각 320달러, 400달러입니다.
추가 생산을 통한 저장. 다만 저장 비용은 카페트 하나마다 한달에 8달러의 비용이 듭니다. 현재 보관된 카페트는 없으며, 해가 마무리될 때는 보관된 카페트는 없어야 합니다.
위와 같은 문제는 공식화할 수 있으며, 선형 계획법으로 해결할 수 있습니다.
먼저 중요한 첫 번째 단계는 변수들을 선언하는 것입니다.
1년에 총 12달이 존재하기 때문에, 총 72개의 변수가 존재합니다(\(w_0\)과 \(s_0\)을 포함하면 74개).
이 선형 계획법을 심플렉스로 푸는 것은 1초도 채 걸리지 않으며 회사를 위한 최적의 비즈니스 전략을 제공할 수 있습니다.
최적의 답은 아마 분수로 나타날 것 입니다. 예를 들어, 3월에 10.6명을 고용하는 것이 필요합니다. 이 수는 통상적으로 10 또는 11로 반올림되고 전체 비용은 이에 상응하여 증가하게 됩니다. 현재 예제에서 변수의 대부분은 상당히 큰 값들입니다. 따라서 반올림이 많은 영향을 주지는 않는 것 같습니다. 그러나 합리적인 정수로 답을 내기 위해서 반올림에 대한 결정이 매우 신중해야 하는 다른 LP 문제들이 있습니다.
일반적으로 선형계획법에는 분수로 나타나는 해답과 정수 해답을 얻는 편의성 사이의 tension이 존재합니다. LP에서 최적의 정수 해답을 찾는 것은 중요하지만 매우 어려운 문제이며 이러한 문제를 정수 선형 계획법(integer linear programming)이라고 합니다.
Example: Optimum Bandwidth Allocation
이번에는 네트워크 서비스 제공자가 직면할 수 있는 문제를 축소한(reduced) 버전의 문제를 살펴보겠습니다.
위 그림에서 나타나는 대역폭을 가진 선들로 이루어진 네트워크를 관리한다고 가정해봅시다. 그리고 사용자 A와 B, B와 C, A와 C 사이에 3개의 연결이 더 필요하다고 해봅시다. 각 연결은 적어도 2개의 대역폭이 요구되지만, 더 할당될 수도 있습니다. A-B 연결은 대역폭당 3달러를 지불하고, B-C와 A-C는 각각 2달러와 4달러를 지불합니다.
각 연결은 긴 경로(route)와 짧은 경로 또는 이 두 조합에 의한 경로, 두 가지 방법으로 길을 찾을 수 있습니다. 예를 들어, 짧은 길을 경유한 두 대역폭과 긴 길을 경유한 하나의 대역폭의 조합이 있을 수 있습니다. 이때, 이 네트워크의 수익을 최대로 하기 위해 이들을 어떻게 연결해야 할까요?
이 문제는 선형 계획법 문제입니다. 이 문제에서는 각 연결과 각 경로에 대한 변수들을 갖습니다. 예를 들면, \(x_{AB}\)는 A와 B 사이에 연결을 위해 할당된 짧은 경로의 대역폭이됩니다. 그리고 \(x'_{AB}\)는 이와 동일한 연결을 위한 긴 경로의 대역폭이 됩니다. 이때, 간선의 대역폭은 초과되어서는 안 되며 각 연결은 적어도 두 단위의 대역폭을 가지는 것으로 요구됩니다.
식으로 표현하면 위와 같습니다. 아주 작은 예제였지만, 이와 같은 네트워크 문제를 혼자 힘으로 풀기는 어렵습니다. 그러나 최적의 솔루션은 심플렉스법을 통해 즉시 얻을 수 있습니다.
이 솔루션은 정수가 아닙니다. 하지만 정수를 꼭 구할 필요는 없으므로 여기서 반올림은 수행하지 않습니다. 네트워크를 살펴보면, a-c를 제외한 모든 간선이 최대 용량으로 사용되는 것을 알 수 있습니다.
Reductions (치환)
교재에서는 Reduction을 축약이라고 해석합니다. 축약도 어느정도 맞는 표현이지만 웹 상의 다른 글들을 보면 축약보다는 다른 문제로 치환한다는 의미로 많이 사용하고 있어, 저도 치환이라는 용어로 해석하여 사용합니다.
때때로 computational task이 충분히 일반적(general)이어서 해당 서브루틴을 사용하여 언뜻 보기에 전혀 관련이 없어 보일 수 있는 다양한 다른 task를 해결할 수도 있습니다. 예를 들어, 아래 DP에 대한 포스팅에서 살펴봤었는데 DAG에서 가장 긴 경로를 찾는 알고리즘이 놀랍게도 최장 증가 부분 수열(LIS)을 찾는데 사용되는 것을 살펴봤습니다.
여기서 이러한 현상은 LIS 문제가 DAG에서 가장 긴 경로를 찾는 문제로 치환된다고 말할 수 있습니다. 그리고, DAG의 가장 긴 경로는 DAG의 가장 짧은 경로 문제로 치환됩니다. 아래는 DAG의 가장 짧은 경로를 찾는 알고리즘이 어떻게 가장 긴 경로를 찾는 문제를 해결하는데 사용될 수 있는지 보여줍니다.
다시 돌아와서, 치환(reduction)을 더 형식적인 관점에서 살펴보겠습니다. 만약 task Q에 대한 어떤 서브루틴이 P를 해결하는 데에도 사용될 수 있는 경우 P가 Q로 치환(P reduces to Q)된다고 말합니다. 종종 P는 Q의 서브루틴에 대한 단일 호출로 해결할 수 있습니다. 이는 P의 모든 인스턴스 x가 인스턴스 y로 변환되어 P(x)가 Q(y)에서 추론될 수 있음을 의미합니다.
(P=LONGEST PATH에서 Q=SHORTEST PATH로의 치환이 되는 것이죠)
만약 사전처리 혹은 사후처리가 효율적으로 계산될 수 있다면, 이는 Q를 위한 효율적인 알고리즘에서 벗어나 P를 위한 효율적인 알고리즘을 만들게 됩니다.
이렇듯 Reduction(치환)은 알고리즘의 힘을 강화시킵니다. 문제 Q(예를 들어, 최단 경로)에 대한 알고리즘을 알자마자, 다른 문제들을 풀기 위해 사용할 수 있습니다. 사실 교재에서 설명하는 대부분의 computational task들은 매우 다양한 응용 프로그램에서 발생하기 때문에 핵심적인 CS 문제로 간주됩니다. 특히 선형 계획법이 이에 해당합니다.
Variants of Linear Programming
예제에서 증명되었듯이, 보편적인 선형계획법은 많은 자유도(degree of freedom)을 가지고 있습니다.
최대화 또는 최소화 문제가 될 수 있다.
제약들은 항등식과(또는) 부등식이 될 수 있다.
변수들은 보통 음이 아닌 값으로 제한되지만, 부호에 제한이 없을 수도 있다.
이제 이 LP들의 옵션들이 단순환 변환을 통해 또 다른 것으로 모두 축소될 수 있다는 것을 살펴보겠습니다.
1. 최소화 문제를 최대화 문제로 바꾸기 위해, 목적 함수의 계수들에 -1을 곱한다.
2a. \(\sum_{i = 1}{n}a_i x_i \leq b\)와 같은 부등식 제약은 항등식으로 바꾸기 위하여, 새로운 변수 s를 도입하여 사용한다.
\[\sum_{i=1}{n}a_i x_i + s = b, s \geq 0\]
여기서 s는 부등식을 위한 여유 변수(slack variable)라고 부른다. 정당한지 증명하기 위해 벡터(\(x_1, \cdots, x_n\))가 원래의 부등식 제약을 만족하는 필요충분 조건으로 새로운 항등식 제약을 만족하기 위한 어떤 \(s \geq 0\)이 있음을 관찰합니다.
2b. 항등식의 제약을 부등식으로 변경하는 것은 쉽습니다. 즉, \(ax = b\)는 \(ax \leq b\)와 \(ax \geq b\) 제약들로 재작성합니다.
3. 마지막으로 부호에 제한이 없는 변수 x를 다루기 위해, 다음과 같이 합니다.
두 개의 음이 아닌 변수들 \(x^+, x^- \geq 0\)을 도입한다.
목적 함수 또는 제약에서 x가 나타날 때마다 \(x^+ - x^-\)로 대체한다.
이 방법에서 x는 새로운 변수들을 적절히 조정함으로써 실제값을 얻을 수 있습니다. 더 정확하게는 x를 포함한 원래의 LP에서 어떤 가능한 해답은 \(x^+, x^-\)를 포함하는 새로운 LP의 가능한 해답에 매핑될 수 있습니다.
이러한 변환을 적용함으로서 어떤 LP(음이 아니고 부호에 제한이 없는 변수들을 모두 갖는 부등식과 항등식을 둘 다 사용하는 최대화 또는 최소화)를 표준 형태(standard form)라고 부르는 매우 강제적인 제약을 갖는 LP로 풀 수 있습니다. 이 표준 형태는 변수가 모두 음이 아니어야 하고, 제약들이 모두 항등식이며 목적 함수를 최소화합니다.
예를 들어, 우리가 처음 살펴봤던 선형계획법은 다음과 같이 다시 작성됩니다.
원래의 식 또한 어떤 부등식에 대한 목적 함수를 최대화하는 유용한 형태입니다. 어떠한 LP든지 위와 같은 방법과 마찬가지로 새로 작성될 수 있습니다.
Matrix-vector notation \(x_1 + 6x_2\)와 같은 선형 함수들은 두 개의 벡터들의 내적으로서 쓰여질 수 있습니다. 그리고 이는 \(c \cdot x\) 또는 \(c^T \cdot x\)로 표현됩니다. \[c = \begin{pmatrix} 1 \\ 6 \end{pmatrix} \text{ and } \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}\] 비슷하게, 선형 제약들을 행렬-벡터 형태로 표현될 수 있습니다.
행렬 \(\mathbf{A}\)의 각 행은 하나의 제약에 대응합니다. \(\mathbf{x}\)와의 내적은 \(\mathbf{b}\)의 해당 행에 있는 값입니다. 다시 말하면, 만약 \(\mathbf{A}\)의 행들이 \(a_1, \cdots, a_m\) 벡터라면, 이때 \(\mathbf{Ax} \leq \mathbf{b}\)는 다음과 동치입니다. \[a_i \cdot x \leq b_i, \text{ for all } i = 1, \cdots, m\] 이 표기법을 이용하면, 일반적인 LP는 간단하게 아래처럼 표현할 수 있습니다.
댓글