25-01-03 Gomory cuts (1958)

수학자 Gomory는 다음과 같은 사실을 바탕으로 valid inequality를 쉽게 찾는 방법을 고안하였다.

if \(a \le b\) and \(a\) is an integer then \(a \le \lfloor b \rfloor\).

즉, a가 정수라면 b를 rouding해도 a는 b보다 작거나 같은 관계는 유지가 된다.

Gomory fractional cut

앞에 IP문제에서 convex hull로 정의되는 feasible set 집합 \(S\)가 다음과 같다고 해보자.

\[S \subseteq \left\{ x \in \mathbb{Z}^{n}_{+} : \sum^{n}_{j=1} a_{j} x_{j} = a_{0} \right\} \quad \text{where} \quad a_{0} \notin \mathbb{Z}\]

이때 Gomory fractional cut은 다음과 같이 정의된다.

\[\sum^{n}_{j=1} (a_{j} - \lfloor a_{j} \rfloor) x_{j} \ge a_{0} - \lfloor a_{0} \rfloor\]

이와 같은 아이디어를 확장한 아이디어가 매우 많다. 예를 들어 Chvatal cuts, split cuts, lift-and-project cuts 등등이 있다.

Gomory fractional cut 유도 과정은 Wikipedia에 자세히 나와있으므로 참조하기 바란다.