ILP 문제를 푸는 exact method (cutting plane, branch-and-bound, branch-and-cut)

ILP in practice

ILP는 np hard 이기 때문에 이론적으로 optimal solution 을 구할 수 있을 것이라 기대할 수 없다. 하지만 현실에서 많은 경우 ILP 솔버가 최적해를 준다. 이는 ILP 의 정확해를 찾아주는 Exact algorithm 이 많이 발전했기 때문이다. 

아주 나이브하게 생각해보면 ILP 를 풀기 위한 첫걸음으로 LP relaxation 을 생각해볼 수 있다. 쉽게말해 변수가 integer 라는 제약만 없애고 LP 문제를 푸는것이다. 당연히 얻은 결과는 정수가 아니라 실수일 수 있다. 이를 정수해로 변환하기 위해 반올림을 하면 어떨까? 이렇게 구한 해는 최적해가 아닐 수 있을 뿐더러 심지어는 feasible 한 해가 아닐 수도 있다. 

우리에게는 반올림 보다는 조금 더 나은 알고리즘이 필요한데 그것이 cutting plane, branch-and-bound, branch-and-cut 알고리즘이다.

Cutting plane method

LP relaxation후에 제약식들의 선형결합으로 만들어낼 수 있는 제약식을 추가해 어떠한 정수의 feasible point 도 배제하지 않은 채로 최적해로 도달하는 방식이다. 아래 비디오에 설명된 예제를 보자. 

https://www.youtube.com/watch?v=TwpR5p3sKdk 

 

Branch and bound

LP relaxation을 통해 실수해를 얻고 나면 해가 정수여야한다는 점에서 착안해 문제를 두개로 분기(branching) 한다. 더이상 분기할 수 없을때 알고리즘은 종결된다.

이미지 출처는 아래 영상 https://www.youtube.com/watch?v=upcsrgqdeNQ  

자세한 설명은 아래 영상을 참고하자.

https://www.youtube.com/watch?v=upcsrgqdeNQ 

Branch and cut

 branch-and-cut은 branch-and-bound와 cutting plane 방법론을 합친 방법이다. 우선은 LP로 완화된 문제에 cutting plane을 추가해가면서 더 타이트한 LP relaxation 을 최대한 찾아나간다. 더이상 추가할 cutting plane 이 없고 LP relaxation 문제에 해가 feasible 하고 구해진 최적해가 실수해로(fractional) 나왔다면 branching 을 시작한다.