[OR-Tools 스터디] Integer Optimization (Overview)

변수의 일부가 정수여야하는 Linear Optimization problem은 Mixed Integer Programs(MIPs)라고도 불린다.

 

그러한 변수들은 일련의 방법들로 발생할 수 있다.

• Integer variables : 자동차 혹은 TV와 같은 사물의 수를 표현할 때 사용. 이 문제는 이익을 최대화하기 위해 각 사물들을 얼마나 많이 제조해야하는가를 결정하기 위한 문제이다. 전형적으로 이러한 문제들은 변수가 반드시 정수여야한다는 요구조건이 붙음으로써 표준 linear optimization problem으로 설정할 수 있다. 
• Boolean variables : 0과 1 값으로 결정을 표시한다. 

Tools

Mixed integer program 문제들을 풀기 위해 구글에서는 몇가지 방법을 제공한다.

• MPSolver : 표준 branch-and-branch 기술을 사용한 여러 타사 MIP solver를 위한 wrapper
• CP-SAT solver : SAT(satisfiability) method를 사용한 constraint programming solver
• Original CP solver : constraint programming solver

 

Which solver should I use?

MIP solver 혹은 CP-SAT를 사용하건 어떠한 것을 사용할지 결정하는 것에 대해 정해진 규칙은 없다. 대략적인 가이드는 다음과 같다.

• MIP solver는 표준 LP로 셋업을 할 수 있지만 위의 첫번째 예제와 같이 임의의 정수 변수가 있는 문제에 더 적합하다. 
• CP-SAT solver는 위의 두번째 예제와 같이 변수의 대부분이 bool값의 경우에 적합하다.

정수와 bool 변수를 가진 전형적인 MIPs(mixed integer programs)에 대해 두가지 solver 간에는 종종 속도의 차이가 명확하지 않아서 개인의 선호도에 따라 선택하면 된다.

 

MIP와 CP-SAT solver 모두 사용한 예제는 추후 Assignment 파트에서 다룰 예정이다.

 

정수 프로그래밍 문제를 해결하는 또다른 방법은 network flow solver를 사용하는 것이다.

network flow로 셋업할 수 있는 문제의 경우, min cost flow solver가 MIP 또는 CP-SAT solver보다 더 빠를 수 있다. 그러나 모든 MIPs가 이 방법으로 셋업될 수는 없다. 

 

 

Reference : 

https://developers.google.com/optimization/mip