25-01-02 Cutting plane algorithm

이 절에서는 integer linear program을 풀 수 있는 cutting plane 알고리즘에 대해 살펴보도록 하겠다.

Valid Inequality

Cutting plane을 정의하기 위해 먼저 valid inequality가 무엇인지 살펴보자.

집합 S에 대해 부등식 πTxπ0이 다음 조건을 만족한다면 valid하다고 말한다. 즉, 어떤 집합 S가 부등식 πTxπ0이 정의하는 halfspace에 포함되어 있다면 이 부등식은 S에 대해 valid하다고 볼 수 있다.

πTxπ0 for all xS

부등식이 Valid해야 cutting plane이 될 수 있다.

Cutting plane algorithm

이제 다음과 같은 integer programming이 있을 때 cutting plane algorithm을 살펴보도록 하자.

minxcTxsubject to xCxjZ,jJ

S:=conv{xC:xjZ,jJ}이다.

Cutting plane algorithm

다음 알고리즘에서 Convex Problem은 CP로 Integer Program은 IP로 표기한다.

  1. C0:=C으로 두고 x(0):=argminx{cTx:xC0}를 계산
  2. for k=0,1,...
    if xk가 (IP) feasible이면 xk는 optimal solution이므로 Stop함
    else
    S에 대해 valid하면서 xk를 잘라내는 부등식 (π, π0)을 찾음
    Ck+1:=Ck{x:πTxπ0}
    x(k+1):=argminx{cTx:xCk+1}
    end if
    end for

이와 같은 valid inequality를 cutting plane 또는 cut이라고 한다.

알고리즘의 1단계는 convex relaxation을 하여 CP 문제를 푸는 단계이다. 이떄 feasible set은 C이다.

알고리즘 2단계에서는 구한 해가 IP에서 feasible하다면 이를 해로 본다. 만일 feasible하지 않다면 해인 xk와 집합 S를 나누는 valid inequality를 찾아서 Ck의 범위를 줄인다. 그리고, Ck+1로 재정의된 CP 문제를 풀고 알고리즘 2단계를 반복하게 된다.

아래 그림에서 polygon은 집합 C를 나타내며 CP의 해는 검정색 점으로 표시되어 있다. 이때, valid inequality는 해를 잘라내서 집합 C의 범위를 줄이게 된다.

[Fig1] Valid Inequality

[Fig1] Valid Inequality [3]

이와 같이 집합 C의 범위를 계속해서 줄여나가면 IP 문제의 convex hull feasible set인 집합 S와 만나게 되어 IP에 feasible한 해를 구할 수 있게 된다.