• 정수 최적화

일부 변수가 정수여야 하는 선형 최적화 문제를 혼합 정수 프로그램 (MIP)이라고 합니다.

이러한 변수는 여러 가지 방식으로 발생할 수 있습니다.

  • 자동차 또는 텔레비전 세트와 같은 품목의 수를 나타내는 정수 변수. 문제는 수익을 극대화하기 위해 제조할 각 품목의 수를 결정하는 것입니다.
    일반적으로 이러한 문제는 표준 선형 최적화 문제로 설정할 수 있으며, 변수가 정수여야 한다는 요구사항이 추가됩니다. 다음 섹션은 이러한 유형의 문제 예를 보여줍니다.

  • 0~1 값으로 결정을 나타내는 부울 변수.
    예를 들어 태스크에 작업자를 할당하는 것과 관련된 문제를 생각해 보겠습니다(할당 참조). 이러한 유형의 문제를 설정하려면 작업자 i가 태스크 j에 할당되면 1, 그렇지 않으면 0인 부울 변수 xi,j를 정의하면 됩니다.

정수 최적화에 대한 좋은 입문서는 Mosek 모델링 설명서를 참고하세요.

도구

Google에서는 MIP 문제를 해결하는 몇 가지 방법을 제공합니다.

  • MPSolver: 표준 브랜치 및 바운드 기법을 사용하는 여러 서드 파티 MIP 솔버용 래퍼입니다.
  • CP-SAT 솔버: SAT (만족도) 방법을 사용하는 제약 조건 프로그래밍 솔버입니다.
  • 원래 CP 솔버: 제약 조건 프로그래밍 솔버입니다.

어떤 문제 해결사를 사용해야 하나요?

MIP 솔버를 사용할지 CP-SAT 솔버를 사용할지 결정하는 데 있어 확실한 규칙은 없습니다. 대략적인 가이드는 다음과 같습니다.

  • MIP 솔버는 표준 LP로 설정할 수 있지만 위의 첫 번째 예와 같이 임의의 정수 변수가 있는 문제에 더 적합합니다.
  • CP-SAT 솔버는 위의 두 번째 예와 같이 대부분의 변수가 부울인 문제에 더 적합합니다.

정수 변수와 불리언 변수가 모두 있는 일반적인 MIP의 경우 두 솔버 간에 속도에 명확한 차이가 없는 경우가 많으므로 개인적인 선호도에 따라 선택하면 됩니다.

MIP 및 CP-SAT 솔버를 모두 사용하는 예는 할당 문제 해결 및 다른 할당 섹션을 참고하세요.

정수 프로그래밍 문제를 해결하는 또 다른 방법은 네트워크 흐름 솔버를 사용하는 것입니다.
예시는 최소 비용 흐름 문제로 할당을 참고하세요.
네트워크 흐름으로 설정할 수 있는 문제의 경우 최소 비용 흐름 솔버는 MIP 또는 CP-SAT 솔버보다 빠를 수 있습니다. 그러나 모든 MIP를 이러한 방식으로 설정할 수 있는 것은 아닙니다.