다음 섹션에서는 Java용 OR-도구를 시작합니다.
최적화 문제란 무엇인가요?
최적화의 목표는 가능한 많은 해법 세트 중에서 문제에 대한 최적의 해결책을 찾는 것입니다. (가능한 해결 방법을 찾는 데 만족할 때도 있지만 OR-도구로도 이를 수행할 수 있습니다.)
다음은 일반적인 최적화 문제입니다. 운송 회사에서 트럭을 이용해 고객에게 패키지를 배송한다고 가정해 보겠습니다. 회사는 매일 트럭에 택배를 할당한 다음 각 트럭이 택배를 배송할 경로를 선택해야 합니다. 가능한 각 패키지 및 경로 할당에는 트럭의 총 이동 거리와 기타 요소를 기준으로 비용이 책정됩니다. 문제는 비용이 가장 적은 패키지 및 경로의 할당을 선택하는 것입니다.
모든 최적화 문제와 마찬가지로 이 문제에는 다음과 같은 요소가 있습니다.
목표: 최적화할 수량입니다. 위 예에서 목표는 비용을 최소화하는 것입니다. 최적화 문제를 설정하려면 가능한 모든 해의 목표값을 계산하는 함수를 정의해야 합니다. 이를 목표 함수라고 합니다. 앞의 예시에서 목적 함수는 패키지 및 경로 할당의 총비용을 계산합니다.
최적 해법은 목적 함수의 값이 가장 좋은 해법입니다. '최적'은 최댓값 또는 최솟값일 수 있습니다.
제약 조건—문제의 구체적인 요구사항에 따라 가능한 솔루션 세트에 대한 제한 예를 들어 운송 회사가 특정 중량을 초과하는 패키지를 트럭에 할당할 수 없는 경우 솔루션에 제약이 발생합니다.
실행 가능한 해법은 최적일 필요 없이 문제에 주어진 모든 제약 조건을 충족하는 솔루션입니다.
최적화 문제를 해결하는 첫 번째 단계는 목표와 제약 조건을 식별하는 것입니다.
Java에서 최적화 문제 해결
다음으로 최적화 문제의 예를 제공하고 자바에서 이 문제를 설정하고 해결하는 방법을 보여줍니다.
선형 최적화의 예
가장 오래되고 가장 널리 사용되는 최적화 영역 중 하나는 선형 최적화(또는 선형 프로그래밍)로, 목적 함수와 제약 조건을 선형 표현식으로 작성할 수 있습니다. 다음은 이러한 문제 유형의 간단한 예입니다.
다음 제약 조건에 따라 3x + y를 최대화합니다.
- 0 ≤
x≤ 1 - 0 ≤
y≤ 2 x + y≤ 2
이 예시의 목적 함수는 3x + y입니다.
목적 함수와 제약 조건은 모두 선형 표현식으로 주어지므로 이 문제는 선형 문제입니다.
문제 해결의 주요 단계
각 언어에서 문제 설정 및 해결의 기본 단계는 동일합니다.
- 필요한 라이브러리를 가져옵니다.
- 문제 해결사를 선언하고
- 변수를 만듭니다.
- 제약 조건을 정의합니다.
- 목적 함수를 정의합니다.
- 솔버를 호출하고
- 결과를 표시합니다.
Java 프로그램<
이 섹션에서는 문제를 설정하고 해결하는 Java 프로그램에 대해 살펴봅니다.
다음 단계를 따르세요.
- 필수 라이브러리를 가져옵니다.
import com.google.ortools.Loader; import com.google.ortools.init.OrToolsVersion; 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"); if (solver == null) { System.out.println("Could not create solver GLOP"); return; }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를 정의합니다.double infinity = Double.POSITIVE_INFINITY; // Create a linear constraint, x + y <= 2. MPConstraint ct = solver.makeConstraint(-infinity, 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메서드는 이를 최대화 문제로 선언합니다. - 솔버를 호출하고 결과를 표시합니다.
System.out.println("Solving with " + solver.solverVersion()); final MPSolver.ResultStatus resultStatus = solver.solve(); System.out.println("Status: " + resultStatus); if (resultStatus != MPSolver.ResultStatus.OPTIMAL) { System.out.println("The problem does not have an optimal solution!"); if (resultStatus == MPSolver.ResultStatus.FEASIBLE) { System.out.println("A potentially suboptimal solution was found"); } else { System.out.println("The solver could not solve the problem."); return; } } 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.init.OrToolsVersion;
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();
System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());
// Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
if (solver == null) {
System.out.println("Could not create solver GLOP");
return;
}
// 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());
double infinity = Double.POSITIVE_INFINITY;
// Create a linear constraint, x + y <= 2.
MPConstraint ct = solver.makeConstraint(-infinity, 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();
System.out.println("Solving with " + solver.solverVersion());
final MPSolver.ResultStatus resultStatus = solver.solve();
System.out.println("Status: " + resultStatus);
if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
System.out.println("The problem does not have an optimal solution!");
if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
System.out.println("A potentially suboptimal solution was found");
} else {
System.out.println("The solver could not solve the problem.");
return;
}
}
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());
System.out.println("Advanced usage:");
System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
System.out.println("Problem solved in " + solver.iterations() + " iterations");
}
private BasicExample() {}
}
Java 프로그램 실행
위의 프로그램을 다음과 같이 실행할 수 있습니다.
- 위의 코드를 복사하여 새 파일에 붙여넣고
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-도구로 해결할 수 있는 문제 유형의 간략한 개요와 각 문제 유형을 해결하는 방법을 설명하는 이 가이드의 섹션으로 연결되는 링크입니다.
선형 최적화
이전 섹션에서 알아본 것처럼 선형 최적화 문제는 목적 함수와 제약 조건이 변수의 선형 표현식인 문제입니다.
이러한 유형의 문제를 해결하기 위한 OR-도구의 기본 솔버는 선형 최적화 솔버입니다. 선형 최적화 솔버는 실제로 서드 파티 라이브러리를 포함하여 선형 및 혼합 정수 최적화를 위한 여러 다양한 라이브러리의 래퍼입니다.
혼합 정수 최적화
혼합 정수 최적화 문제는 일부 또는 전체 변수가 정수여야 하는 문제입니다. 작업자 그룹을 태스크 세트에 할당해야 하는 할당 문제를 예로 들 수 있습니다. 각 작업자와 작업에 대해 지정된 작업자가 지정된 작업에 할당되면 값이 1, 그렇지 않으면 0인 변수를 정의합니다. 이 경우 변수는 0 또는 1 값만 취할 수 있습니다.
제약조건 최적화
제약조건 최적화 또는 제약조건 프로그래밍 (CP)은 임의의 제약조건 측면에서 문제를 모델링할 수 있는 매우 큰 조합 집합에서 실현 가능한 솔루션을 식별합니다. CP는 최적화 (최적 솔루션 찾기)보다는 실행 가능성 (실현 가능한 솔루션 찾기)을 기반으로 하며 목적 함수보다는 제약 조건과 변수에 중점을 둡니다. 하지만 CP는 가능한 모든 솔루션의 목적 함수의 값을 간단히 비교하는 방식으로 최적화 문제를 해결하는 데 사용할 수 있습니다.
임무
할당 문제에는 에이전트 그룹 (예: 작업자 또는 머신)을 태스크 집합에 할당하는 작업이 포함됩니다. 각 에이전트를 특정 작업에 할당하면 고정 비용이 발생합니다. 문제는 총 비용이 가장 적은 할당을 찾는 것입니다. 할당 문제는 실제로 네트워크 흐름 문제의 특수한 사례입니다.
포장
빈 패킹은 크기가 다른 객체 집합을 용량이 다른 컨테이너에 패킹하는 문제입니다. 목표는 컨테이너의 용량에 따라 가능한 한 많은 객체를 패킹하는 것입니다. 이와 관련된 특수한 사례는 Knapsack 문제로, 이 문제에는 컨테이너가 하나뿐입니다.
예약
예약 문제에는 특정 시간에 일련의 작업을 수행하기 위해 리소스를 할당하는 작업이 포함됩니다. 중요한 예로는 여러 대의 머신에서 여러 작업이 처리되는 작업실 문제가 있습니다. 각 작업은 지정된 순서대로 수행되어야 하는 일련의 태스크로 구성되며 각 태스크는 특정 머신에서 처리되어야 합니다. 문제는 모든 작업이 가능한 한 짧은 시간 간격으로 완료되도록 일정을 할당하는 것입니다.
라우팅
라우팅 문제에는 방향 그래프로 정의된 네트워크를 통과하기 위한 여러 차량의 최적 경로를 찾는 작업이 포함됩니다. 최적화 문제란 무엇인가요?에서 설명한 대로 배달 트럭에 택배를 할당하는 문제는 경로 문제의 한 가지 예입니다. 또 다른 문제는 여행 영업사원 문제입니다.
네트워크 흐름
많은 최적화 문제는 노드와 노드 사이의 방향성 호로 구성된 방향성 그래프로 표현될 수 있습니다. 예를 들어 상품이 철도 네트워크를 통해 운송되는 운송 문제는 호가 철로이고 노드가 유통 센터인 그래프로 표현될 수 있습니다.
최대 흐름 문제에서 각 원호에는 운반할 수 있는 최대 용량이 있습니다. 문제는 각 호를 가로질러 배송할 물품의 양을 할당하여 운송되는 총 수량을 최대한 많이 하는 것입니다.