OR-Tools는 조합 최적화를 위한 오픈소스 소프트웨어로, 가능한 대규모 솔루션 중에서 문제에 대한 최적의 해결책을 찾습니다. 다음은 OR 도구로 해결할 수 있는 문제의 예입니다.
- 차량 경로: 제약 조건 (예: '이 트럭은 6,000 킬로그램 이상을 담을 수 없습니다' 또는 '모든 배송은 2시간 이내에 배송되어야 합니다').
- 예약: 복잡한 머신 집합에 대해 최적의 일정을 찾습니다. 일부 작업은 다른 머신보다 먼저 고정되어야 하며, 고정된 머신 또는 다른 리소스를 통해 수행해야 합니다.
- 휴지통 패킹: 다양한 크기의 객체를 최대한 많은 용량의 적재용 빈통에 패킹합니다.
대부분의 경우 이와 같은 문제에는 수많은 해결책이 있습니다. 컴퓨터 하나로 모두 검색하기에는 너무 많은 솔루션이 있습니다. 이를 극복하기 위해 OR-도구는 최첨단 (또는 최적의) 솔루션을 찾기 위해 최첨단 알고리즘을 사용하여 검색 범위를 좁힙니다.
OR 도구에는 다음을 위한 문제 해결 도구가 포함되어 있습니다.
- 제약 조건 프로그래밍
- 제약조건으로 표현되는 문제에 대한 실행 가능한 해결 방법을 찾는 일련의 기법입니다(예: 2개의 이벤트에 회의실을 동시에 사용할 수 없거나 농작물까지의 거리는 호스의 길이보다 짧거나 한 번에 5개 이하의 TV 프로그램을 녹화할 수 있음).
- 선형 및 혼합 정수 프로그래밍
- Glop 선형 옵티마이저는 제약 조건으로 선형 부등식 세트(예: 작업에 사용자를 할당하거나 비용을 최소화하면서 리소스 집합을 최적으로 할당)를 고려하여 선형 목표 함수의 최적 값을 찾습니다. Glop 및 혼합 정수 프로그래밍 소프트웨어 SCIP는 Google Apps Script 최적화 서비스를 통해서도 제공됩니다.
- 차량 라우팅
- 제한 조건을 충족하는 최적의 차량 경로를 식별하는 특수 라이브러리입니다.
- 그래프 알고리즘
- 그래프, 최저 비용 흐름, 최대 흐름, 선형 합계 할당에서 최단 경로를 찾는 코드입니다.
다음 섹션에서 OR 도구를 빠르게 사용할 수 있습니다.