OR 도구 정보

OR-Tools는 조합 최적화를 위한 오픈소스 소프트웨어로, 가능한 대규모 솔루션 중에서 문제에 대한 최적의 해결책을 찾습니다. 다음은 OR 도구로 해결할 수 있는 문제의 예입니다.

• 차량 경로: 제약 조건 (예: '이 트럭은 6,000 킬로그램 이상을 담을 수 없습니다' 또는 '모든 배송은 2시간 이내에 배송되어야 합니다').
• 예약: 복잡한 머신 집합에 대해 최적의 일정을 찾습니다. 일부 작업은 다른 머신보다 먼저 고정되어야 하며, 고정된 머신 또는 다른 리소스를 통해 수행해야 합니다.
• 휴지통 패킹: 다양한 크기의 객체를 최대한 많은 용량의 적재용 빈통에 패킹합니다.

대부분의 경우 이와 같은 문제에는 수많은 해결책이 있습니다. 컴퓨터 하나로 모두 검색하기에는 너무 많은 솔루션이 있습니다. 이를 극복하기 위해 OR-도구는 최첨단 (또는 최적의) 솔루션을 찾기 위해 최첨단 알고리즘을 사용하여 검색 범위를 좁힙니다.

OR 도구에는 다음을 위한 문제 해결 도구가 포함되어 있습니다.

제약 조건 프로그래밍

제약조건으로 표현되는 문제에 대한 실행 가능한 해결 방법을 찾는 일련의 기법입니다(예: 2개의 이벤트에 회의실을 동시에 사용할 수 없거나 농작물까지의 거리는 호스의 길이보다 짧거나 한 번에 5개 이하의 TV 프로그램을 녹화할 수 있음).

선형 및 혼합 정수 프로그래밍

Glop 선형 옵티마이저는 제약 조건으로 선형 부등식 세트(예: 작업에 사용자를 할당하거나 비용을 최소화하면서 리소스 집합을 최적으로 할당)를 고려하여 선형 목표 함수의 최적 값을 찾습니다. Glop 및 혼합 정수 프로그래밍 소프트웨어 SCIP는 Google Apps Script 최적화 서비스를 통해서도 제공됩니다.

차량 라우팅

제한 조건을 충족하는 최적의 차량 경로를 식별하는 특수 라이브러리입니다.

그래프 알고리즘

그래프, 최저 비용 흐름, 최대 흐름, 선형 합계 할당에서 최단 경로를 찾는 코드입니다.

다음 섹션에서 OR 도구를 빠르게 사용할 수 있습니다.