다음 섹션에서는 Java용 OR-도구를 시작합니다.
최적화 문제란 무엇인가요?
최적화의 목표는 가능한 대규모 솔루션 세트 중에서 문제에 대한 최적의 솔루션을 찾는 것입니다. 적합한 솔루션을 찾는 데 만족할 때도 있지만, OR-Tools를 사용해도 이러한 작업을 수행할 수 있습니다.
다음은 일반적인 최적화 문제입니다. 한 운송 회사가 트럭을 이용하여 고객에게 택배를 배송한다고 가정해 보겠습니다. 회사는 매일 트럭에 택배를 할당하고 각 트럭의 택배 배송 경로를 선택해야 합니다. 가능한 각 택배와 경로 할당에는 트럭의 총 이동 거리와 기타 요인을 바탕으로 한 비용이 발생합니다. 문제는 비용이 가장 적은 패키지 및 경로의 할당을 선택하는 것입니다.
모든 최적화 문제와 마찬가지로 이 문제에는 다음과 같은 요소가 있습니다.
목표: 최적화하려는 수량입니다. 위 예에서 목표는 비용을 최소화하는 것입니다. 최적화 문제를 설정하려면 가능한 모든 해의 목표 값을 계산하는 함수를 정의해야 합니다. 이를 목적 함수라고 합니다. 앞의 예에서 목표 함수는 패키지 및 경로 할당의 총비용을 계산합니다.
최적 해는 목표 함수의 값이 가장 좋은 해입니다. '최적'은 최댓값 또는 최솟값일 수 있습니다.
제약 조건: 문제의 특정 요구사항에 따라 가능한 솔루션 집합에 대한 제한사항 예를 들어 운송 회사가 특정 중량을 초과하는 패키지를 트럭에 할당할 수 없는 경우 솔루션에 제약이 적용됩니다.
실행 가능한 솔루션은 문제에 대해 주어진 모든 제약 조건을 충족하며, 반드시 최적의 솔루션이 아니어야 합니다.
최적화 문제를 해결하는 첫 번째 단계는 목표와 제약 조건을 식별하는 것입니다.
자바에서 최적화 문제 해결
다음으로 최적화 문제의 예를 제시하고 자바에서 최적화 문제를 설정하고 해결하는 방법을 보여줍니다.
선형 최적화의 예
가장 오래되고 널리 사용되는 최적화 영역 중 하나는 선형 최적화(또는 선형 프로그래밍)이며, 여기서 목적 함수와 제약 조건을 선형 표현식으로 작성할 수 있습니다. 여기 이러한 유형의 문제의 간단한 예가 있습니다.
다음 제약 조건에 따라 3x + y를 최대화합니다.
- 0 ≤
x≤ 1 - 0 ≤
y≤ 2 x + y≤ 2
이 예시의 목표 함수는 3x + y입니다.
목표 함수와 제약 조건은 모두 선형 표현식으로 주어지므로 이는 선형 문제입니다.
문제 해결의 주요 단계
언어마다 문제를 설정하고 해결하는 기본 단계는 동일합니다.
- 필요한 라이브러리를 가져오고
- 문제 해결사를 선언하고
- 변수를 만듭니다.
- 제약 조건을 정의합니다.
- 목표 함수를 정의합니다.
- 솔버를 호출하고
- 결과를 표시합니다.
Java 프로그램<
이 섹션에서는 문제를 설정하고 해결하는 Java 프로그램을 살펴봅니다.
다음 단계를 따르세요.
- 필수 라이브러리를 가져옵니다.
import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable;
- 솔버를 선언합니다.
// Create the linear solver with the GLOP backend. MPSolver solver = MPSolver.createSolver("GLOP");MPSolver는 선형 프로그래밍 또는 혼합 정수 프로그래밍 문제를 해결하기 위한 래퍼입니다. - 변수를 만듭니다.
// Create the variables x and y. MPVariable x = solver.makeNumVar(0.0, 1.0, "x"); MPVariable y = solver.makeNumVar(0.0, 2.0, "y"); System.out.println("Number of variables = " + solver.numVariables()); - 제약 조건을 정의합니다.
처음 두 제약 조건
0≤x≤1및0≤y≤2는 이미 변수 정의에 의해 설정되어 있습니다. 다음 코드는x + y≤2제약 조건을 정의합니다.// Create a linear constraint, 0 <= x + y <= 2. MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct"); ct.setCoefficient(x, 1); ct.setCoefficient(y, 1); System.out.println("Number of constraints = " + solver.numConstraints());setCoefficient메서드는 제약 조건 표현식에서x및y의 계수를 설정합니다. - 목표 함수를 정의합니다.
// Create the objective function, 3 * x + y. MPObjective objective = solver.objective(); objective.setCoefficient(x, 3); objective.setCoefficient(y, 1); objective.setMaximization();
setMaximization메서드는 이를 최대화 문제로 선언합니다. - 솔버를 호출하고 결과를 표시합니다.
solver.solve(); System.out.println("Solution:"); System.out.println("Objective value = " + objective.value()); System.out.println("x = " + x.solutionValue()); System.out.println("y = " + y.solutionValue());
프로그램 완료
전체 프로그램은 다음과 같습니다.
package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
// Create the variables x and y.
MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
System.out.println("Number of variables = " + solver.numVariables());
// Create a linear constraint, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);
System.out.println("Number of constraints = " + solver.numConstraints());
// Create the objective function, 3 * x + y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 1);
objective.setMaximization();
solver.solve();
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());
}
private BasicExample() {}
}
자바 프로그램 실행
다음과 같이 위의 프로그램을 실행할 수 있습니다.
- 위의 코드를 복사하여 새 파일에 붙여넣고
my_program.java로 저장합니다. - OR-Tools를 설치한 디렉터리의 최상위 수준에서 명령어 창을 열고
make run SOURCE=relative/path/to/my_program.java
를 입력합니다. 여기서relative/path/to/는 프로그램을 저장한 디렉터리의 경로입니다.
프로그램은 목표 함수를 최대화하는 x 및 y 값을 반환합니다.
Solution:
x = 1.0
y = 1.0
프로그램을 실행하지 않고 컴파일하려면 다음을 입력합니다.
make build SOURCE=relative/path/to/my_program.java
더 많은 자바 예시
다양한 유형의 최적화 문제를 해결하는 방법을 보여주는 Java 예를 더 보려면 예를 참고하세요.
해결하려는 문제 유형 식별
최적화 문제는 매우 다양합니다. 문제 유형마다 최적의 솔루션을 찾기 위한 다양한 접근 방식과 알고리즘이 있습니다.
최적화 문제를 해결하기 위한 프로그램 작성을 시작하려면 먼저 어떤 유형의 문제를 처리하고 있는지 파악한 다음, 최적의 솔루션을 찾는 알고리즘인 해결자를 선택해야 합니다.
다음은 OR-Tools로 해결되는 문제 유형에 대한 간략한 개요와 각 문제 유형을 해결하는 방법을 설명하는 이 가이드의 섹션으로 연결되는 링크입니다.
선형 최적화
이전 섹션에서 알아본 것처럼 선형 최적화 문제는 목표 함수와 제약 조건이 변수의 선형 표현식인 문제입니다.
이러한 문제 유형을 위한 OR-Tools의 기본 솔버는 선형 최적화 솔버로, 실제로 서드 파티 라이브러리를 비롯한 선형 및 혼합 정수 최적화를 위한 여러 다른 라이브러리의 래퍼입니다.
혼합 정수 최적화
혼합 정수 최적화 문제는 일부 또는 모든 변수가 정수여야 하는 문제입니다. 예를 들어 할당 문제는 작업자 그룹을 태스크 집합에 할당해야 합니다. 각 작업자와 작업의 경우 지정된 작업자가 지정된 작업에 할당된 경우 값이 1, 그렇지 않으면 0인 변수를 정의합니다. 이 경우 변수는 0 또는 1 값만 사용할 수 있습니다.
제약조건 최적화
제약조건 최적화 또는 제약조건 프로그래밍 (CP)은 임의의 제약 조건 측면에서 문제를 모델링할 수 있는 매우 큰 조합에서 가능한 솔루션을 식별합니다. CP는 최적화 (최적 솔루션 찾기)보다는 실행 가능성 (가능한 솔루션 찾기)을 기반으로 하며 목표 함수보다는 제약 조건과 변수에 중점을 둡니다. 하지만 CP는 가능한 모든 솔루션에 대해 목표 함수의 값을 비교하여 최적화 문제를 해결하는 데 사용할 수 있습니다.
임무
할당 문제에는 에이전트 그룹 (예: 작업자 또는 머신)을 태스크 집합에 할당하는 작업이 포함됩니다. 각 에이전트를 특정 태스크에 할당하면 고정 비용이 발생합니다. 문제는 총비용이 가장 적은 할당을 찾는 것입니다. 할당 문제는 실제로 네트워크 흐름 문제의 특수한 경우입니다.
포장
빈 패킹은 크기가 다른 객체 세트를 용량이 다른 컨테이너에 패킹하는 문제입니다. 목표는 컨테이너의 용량에 따라 가능한 한 많은 객체를 패킹하는 것입니다. 이 오류의 특수한 경우는 Knapsack 문제로, 컨테이너가 하나뿐입니다.
스케줄링
예약 문제에는 특정 시간에 일련의 작업을 수행할 리소스를 할당하는 작업이 포함됩니다. 중요한 예로 여러 개의 작업이 여러 머신에서 처리되는 작업실 문제가 있습니다. 각 작업은 지정된 순서로 수행해야 하는 일련의 태스크로 구성되며 각 태스크는 특정 머신에서 처리되어야 합니다. 문제는 모든 작업이 가능한 한 짧은 시간 간격으로 최대한 빨리 완료되도록 일정을 할당하는 것입니다.
라우팅
라우팅 문제는 방향성 그래프에 의해 정의된 네트워크를 통과하기 위한 차량의 최적 경로를 찾는 것입니다. 최적화 문제란 무엇인가요?에서 설명한 대로 배송 트럭에 택배를 할당하는 문제는 라우팅 문제의 한 가지 예입니다. 또 다른 하나는 출장 영업사원 문제입니다.
네트워크 흐름
많은 최적화 문제는 노드와 노드 사이의 방향 호로 구성된 방향성 그래프로 표현될 수 있습니다. 예를 들어 상품이 철도 네트워크를 통해 배송되는 운송 문제는 호가 철로이고 노드는 유통 센터인 그래프로 표현될 수 있습니다.
최대 흐름 문제에서 각 원호에는 옮길 수 있는 최대 용량이 있습니다. 문제는 각 호를 가로질러 배송할 상품의 양을 할당하여 운송되는 총 수량을 최대한 넓히는 것입니다.