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인
이때, feasible set은 convex hull
아래 그림을 보면 파란색 영역이
출처: https://commons.wikimedia.org/wiki/File:Cutting_plane_algorithm2.png
이 두 식이 동일한 이유는 objective function이 linear하기 때문이다.
Special case: integer linear programs
위의 convexification 과정을 다음과 같은 integer linear program에 적용해보자.
Integer linear program에서 convex hull
Theorem : 만일
가 유리수라면 다음 집합은 polygon이다.
그렇다면 integer linear program은 linear program일까? 물론 그렇다. 하지만, 이때 polyhedron