25-01-01 Convexification

Integer program을 동일한 convex problem으로 변환하는 것을 convexification이라고 한다. Convexification을 하게 되면 feasible set이 polyhedron 형태가 되어 cutting plane 알고리즘에서 valid한 cutting plane을 쉽게 찾을 수 있다.

Convexification

Integer program을 convexification하려면 objective function이 linear해야 한다. 이때, Integer program의 constraint는 convex set인 C와 integer set인 xj로 구성된다.

minxcTxsubject to xCxjZ,jJ

이때, feasible set은 convex hull S:=conv{xC:xjZ,jJ}로 재정의할 수 있다. 이 convex hull S로 정의된 feasible set을 이용해 원래 문제와 동일한 convex problem을 다음과 같이 정의할 수 있다. 그리고, 이러한 과정을 convexification이라고 한다.

minxcTxsubject to xS

아래 그림을 보면 파란색 영역이 C이고 빨간색 점들이 xj이며, 이 두 집합으로 구성된 convex hull S는 빨간색 영역이다.

[Fig1] Cutting Plane

[Fig1] Cutting Plane

출처: https://commons.wikimedia.org/wiki/File:Cutting_plane_algorithm2.png

이 두 식이 동일한 이유는 objective function이 linear하기 때문이다.

Special case: integer linear programs

위의 convexification 과정을 다음과 같은 integer linear program에 적용해보자.

minxcTxsubject to AxbxjZ,jJ

Integer linear program에서 convex hull S는 다음과 같이 정의된다.

Theorem : 만일 A,b가 유리수라면 다음 집합은 polygon이다. S:=conv{x:Axb,xjZ,jJ}

그렇다면 integer linear program은 linear program일까? 물론 그렇다. 하지만, 이때 polyhedron S의 형태는 부등식이 기하급수적으로 많은 매우 많은 복잡한 다각형이 될 수 있다. 따라서, 일반적으로 linear program을 풀기 위한 방법과는 다른 방법으로 문제를 풀어야 한다.