Using OR-Tools with C++

 

 다음 섹션에서는 C ++에서 OR- 도구를 사용하는 방법을 소개합니다.


간단한 C ++ 예제
최적화 문제 란 무엇입니까?
C ++에서 최적화 문제 해결
• 더 많은 C ++ 예제
해결하려는 문제의 유형 식별

 

 

 

간단한 C ++ 예제

 

 우리는 매우 간단한 최적화 문제를 해결하는 작은 C ++ 프로그램부터 시작합니다 : 0≤x≤1, 0≤y≤2의 제약을받는 x + y의 최대 값을 찾으십시오.

 

#include "ortools/linear_solver/linear_solver.h"
#include "ortools/linear_solver/linear_solver.pb.h"

namespace operations_research {
  void RunTest(
    MPSolver::OptimizationProblemType optimization_problem_type) {
    MPSolver solver("Glop", optimization_problem_type);
    MPVariable* const x = solver.MakeNumVar(0.0, 1, "x");
    MPVariable* const y = solver.MakeNumVar(0.0, 2, "y");
    MPObjective* const objective = solver.MutableObjective();
    objective->SetCoefficient(x, 1);
    objective->SetCoefficient(y, 1);
    objective->SetMaximization();
    solver.Solve();
    printf("\nSolution:");
    printf("\nx = %.1f", x->solution_value());
    printf("\ny = %.1f", y->solution_value());
  }

  void RunExample() {
    RunTest(MPSolver::GLOP_LINEAR_PROGRAMMING);
  }
}

int main(int argc, char** argv) {
  operations_research::RunExample();
  return 0;
}

 

 

다음과 같이 예제를 실행할 수 있습니다.


1. 위의 코드를 복사하여 새 파일에 붙여넣고 OR-Tools를 설치 한 디렉토리의 최상위 레벨에 simple_program.cc로 저장하십시오.


2. 동일한 디렉토리에서 Makefile.user라는 새 파일을 만들고 다음 빌드 규칙을 추가하십시오.

 

$(OBJ_DIR)$Ssimple_program.$O: $(EX) $(CVRPTW_DEPS) $(DIMACS_DEPS) $(FAP_DEPS)
 $(CCC) $(CFLAGS) -c $(EX) $(OBJ_OUT)$(OBJ_DIR)$S$(basename $(notdir $(EX))).$O

$(BIN_DIR)/simple_program$E: $(OR_TOOLS_LIBS) $(CVRPTW_LIBS) $(DIMACS_LIBS) $(FAP_LIBS) \
 $(OBJ_DIR)$Ssimple_program.$O
 $(CCC) $(CFLAGS) $(OBJ_DIR)$Ssimple_program.$O $(OR_TOOLS_LNK) $(CVRPTW_LNK) $(DIMACS_LNK) \
 $(FAP_LNK) $(OR_TOOLS_LD_FLAGS) $(EXE_OUT)$(BIN_DIR)$Ssimple_program$E

 

3. OR-Tools를 설치 한 디렉토리의 최상위 레벨에서 명령 창을여십시오.


4. 다음과 같이 프로그램을 실행하십시오.

 

make rcc EX=simple_program.cc

 

★ 참고 : C ++ 프로그램은 설치된 OR-Tools (Makefile이있는 디렉토리)의 최상위 레벨에서 실행해야합니다.

 

 

프로그램은 다음과 같은 결과를 반환합니다.

 

Solution:
x =  1.0
y =  2.0

 

 

실행하지 않고 프로그램을 컴파일하려면 다음을 입력하십시오.

 

make ccc EX=simple_program.cc

 

생성 한 각 C ++ 프로그램에 대해 위와 같은 새 빌드 규칙을 Makefile.user에 추가하고 simple_program의 각 인스턴스를 프로그램의 이름으로 바꿔야합니다.

 

 

선택 모드에서 컴파일

 

O3 모드에서 컴파일하기

 

make DEBUG='-O3' all

 

 

C ++ 실행 파일 실행하기

 

 C ++ 프로그램을 컴파일하면 실행 파일이 bin 디렉토리에 작성됩니다. 다음과 같이 예제 프로그램의 실행 파일을 실행할 수 있습니다.

 

$ cd bin
$ simple_program

 

프로그램을 변경하면 위와 같이 다시 컴파일해야합니다.

 

 

최적화 문제 란 무엇입니까?

 

 최적화의 목표는 가능한 많은 솔루션 세트에서 문제에 대한 최상의 솔루션을 찾는 것입니다. (때로는 실현 가능한 솔루션을 찾는데 만족할 것이며, OR-Tools도이를 수행 할 수 있습니다.)

 

 다음은 일반적인 최적화 문제입니다. 해운 회사가 트럭을 사용하여 고객에게 패키지를 전달한다고 가정합니다. 매일 회사는 트럭에 패키지를 지정해야하며 각 트럭이 패키지를 배송 할 경로를 선택해야합니다. 패키지와 경로의 가능한 할당은 트럭의 총 주행 거리를 기준으로 비용이 들며 다른 요인도 포함될 수 있습니다. 문제는 비용이 가장 적은 패키지와 경로의 할당을 선택하는 것입니다.

 

 모든 최적화 문제와 마찬가지로이 문제의 요소는 다음과 같습니다.

 

• 목표 - 최적화하려는 수량. 위의 예에서 목표는 비용을 최소화하는 것입니다. 최적화 문제를 설정하려면 가능한 솔루션에 대한 목표 값을 계산하는 함수를 정의해야합니다. 이것을 목적 함수라고합니다. 앞의 예에서 objective 함수는 패키지와 라우트 할당의 총 비용을 계산합니다.

 

 최적의 솔루션은 목적 함수의 값이 가장 좋은 솔루션입니다. ( "최고"는 최대 또는 최소 수 있습니다.)


• 문제의 특정 요구 사항을 기반으로 가능한 솔루션 집합에 대한 제약 조건 제한. 예를 들어, 운송 회사가 주어진 중량을 초과하는 패키지를 트럭에 할당 할 수없는 경우 솔루션에 대한 제약이 가해질 수 있습니다. 실현 가능한 해법은 문제에 대한 모든 주어진 제약을 만족 시키는데, 반드시 최적 일 필요는 없다.

 

최적화 문제를 해결하는 첫 번째 단계는 목표와 제약 조건을 파악하는 것입니다.

 

 

C ++에서 최적화 문제 해결

 

 다음으로 최적화 문제의 예제를 제시하고 C ++로 설정하고 해결하는 방법을 보여줍니다.

 

 

선형 최적화 예제

 

 가장 오래되고 광범위하게 사용되는 최적화 영역 중 하나는 선형 최적화 (또는 선형 프로그래밍)입니다. 여기서 목적 함수와 제약 조건을 선형 표현식으로 작성할 수 있습니다. 다음은 이러한 유형의 문제에 대한 간단한 예입니다.

 

다음 제약 조건에 따라 3x + 4y를 최대화하십시오.

 

x + 2y 14
3xy 0
xy 2

 

 이 예제의 목적 함수는 f (x, y) = 3x + 4y입니다. 객관적인 함수와 제약 조건 모두 선형 표현식에 의해 주어 지므로 선형 문제가됩니다.

 

 제약 조건은 실행 영역을 정의합니다.이 영역은 내부를 포함하여 아래에 표시된 삼각형입니다.

 

 

 

 

문제 해결의 주요 단계

 

각 언어에 대해 문제를 설정하고 해결하기위한 기본 단계는 동일합니다.


• 변수를 만듭니다.
• 제약 조건을 정의합니다.
• 목적 함수를 정의하십시오.
• 최적 해를 찾는 알고리즘을 구현하는 해법을 선언하십시오.
• 해석기를 호출하고 결과를 표시합니다.

 

 

C ++ 프로그램

 

 C ++에서 문제를 설정하는 방법을 보여줌으로써 시작하겠습니다. 이 예제에서 사용한 메소드의 링크를 참조 페이지에 추가 했으므로 참조 페이지에 대해 자세히 알아보십시오. 다음은 C ++에서 문제를 설정하고 해결하는 단계입니다.


MakeNumVar 메서드를 사용하여 변수를 만듭니다.

 

  MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
  MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");

 

• MakeRowConstraint 및 SetCoefficient 메서드를 사용하여 제약 조건을 정의합니다.

 

   // x + 2y <= 14.
  MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 14.0);
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 2);

  // 3x - y >= 0.
  MPConstraint* const c1 = solver.MakeRowConstraint(0.0, infinity);
  c1->SetCoefficient(x, 3);
  c1->SetCoefficient(y, -1);

  // x - y <= 2.
  MPConstraint* const c2 = solver.MakeRowConstraint(-infinity, 2.0);
  c2->SetCoefficient(x, 1);
  c2->SetCoefficient(y, -1);

 

예를 들어, 첫 번째 부등식 인 $$ x + 2y \ leq 14 $$에 대한 제약 조건은 다음과 같이 정의됩니다.

 

• MakeRowConstraint (-infinity, 14)는 왼쪽이 14보다 작거나 같은 부등식 제약 조건을 만듭니다.
• c0-> SetCoefficient (x, 1); x의 계수를 1로 설정합니다.
• c0-> SetCoefficient (y, 2); y의 계수를 2로 설정합니다.

 

• 목적 함수를 정의하십시오. SetCoefficient 메서드는 함수의 계수를 설정합니다. SetMaximization 메서드는이 점을 최대화 문제로 만듭니다.

 

  // Objective function: 3x + 4y.
  MPObjective* const objective = solver.MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 4);
  objective->SetMaximization();

 

• 해석기를 선언하십시오. 이 예에서는 OR-Tools 선형 해석기 래퍼를 사용하여 Google의 선형 최적화 프로그램 인 Glop을 호출합니다. 다음 코드는 해석을 선언합니다.

 

  void RunLinearExample(
  MPSolver::OptimizationProblemType optimization_problem_type) {
  MPSolver solver("LinearExample", optimization_problem_type);

 

프로그램이에 의해 해를 호출하면

 

  RunLinearExample(MPSolver::GLOP_LINEAR_PROGRAMMING);

 

솔버에게 Glop을 사용하도록 지시하는 인수 GLOP_LINEAR_PROGRAMMING이 OptimizationProblemType 메소드를 통해 해석기로 전달됩니다.

 

• 해석기를 호출하고 결과를 표시합니다.

 

  printf("\nNumber of variables = %d", solver.NumVariables());
  printf("\nNumber of constraints = %d", solver.NumConstraints());
  solver.Solve();
  // The value of each variable in the solution.
  printf("\nSolution:");
  printf("\nx = %.1f", x->solution_value());
  printf("\ny = %.1f", y->solution_value());

  // The objective value of the solution.
  printf("\nOptimal objective value = %.1f", objective->Value());
  printf("\n");

 

 

 

 

전체 프로그램

 

전체 프로그램은 아래와 같습니다.

 

#include "ortools/linear_solver/linear_solver.h"
#include "ortools/linear_solver/linear_solver.pb.h"

namespace operations_research {
void RunLinearExample(
  MPSolver::OptimizationProblemType optimization_problem_type) {
  MPSolver solver("LinearExample", optimization_problem_type);
  const double infinity = solver.infinity();
  // x and y are non-negative variables.
  MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
  MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");
  // Objective function: 3x + 4y.
  MPObjective* const objective = solver.MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 4);
  objective->SetMaximization();
  // x + 2y <= 14.
  MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 14.0);
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 2);

  // 3x - y >= 0.
  MPConstraint* const c1 = solver.MakeRowConstraint(0.0, infinity);
  c1->SetCoefficient(x, 3);
  c1->SetCoefficient(y, -1);

  // x - y <= 2.
  MPConstraint* const c2 = solver.MakeRowConstraint(-infinity, 2.0);
  c2->SetCoefficient(x, 1);
  c2->SetCoefficient(y, -1);
  printf("\nNumber of variables = %d", solver.NumVariables());
  printf("\nNumber of constraints = %d", solver.NumConstraints());
  solver.Solve();
  // The value of each variable in the solution.
  printf("\nSolution:");
  printf("\nx = %.1f", x->solution_value());
  printf("\ny = %.1f", y->solution_value());

  // The objective value of the solution.
  printf("\nOptimal objective value = %.1f", objective->Value());
  printf("\n");
}

void RunExample() {
  RunLinearExample(MPSolver::GLOP_LINEAR_PROGRAMMING);
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::RunExample();
  return 0;
}

 

 

프로그램을 실행하려면 :


1. 위의 코드를 복사하여 새 파일에 붙여넣고 lp_program.cc로 저장하십시오.


2. 간단한 C ++ 예제에서 설명한대로 Makefile.user에 새 항목을 추가하고 simple_program 대신 lp_program을 사용하십시오.


3. OR-Tools를 설치 한 디렉토리의 최상위 레벨에서 명령 창을 열고 다음을 입력하십시오.

 

make rcc EX=lp_program.cc

 

 

최적의 솔루션

 

각 프로그램은 아래와 같이 문제에 대한 최적의 솔루션을 반환합니다.

 

Number of variables = 2
Number of constraints = 3
Solution:
x = 6.0
y = 4.0
Optimal objective value = 34.0

 

다음은 솔루션을 보여주는 그래프입니다.

 

 

 점선으로 표시된 녹색 선은 목적 함수를 최적 값 34와 동일하게 설정하여 정의됩니다. 방정식이 3x + 4y = c 인 모든 선은 파선과 평행하고 34는 선의 최대 값입니다. 가능한 영역과 교차합니다.

 

 위의 그래프에서 지오메트리에 대해 생각해 보면 모든 선형 최적화 문제에서 가능한 영역의 하나 이상의 꼭지점이 최적의 솔루션이어야합니다. 결과적으로 목적 함수의 개선이 없어 질 때까지 실행 가능 영역의 정점을 탐색하여 최적의 솔루션을 찾을 수 있습니다. 이것은 선형 최적화 문제를 해결하기 위해 가장 널리 사용되는 방법 인 단순 알고리즘 뒤에있는 아이디어입니다.

 

 선형 최적화 문제를 해결하는 방법에 대한 자세한 내용은 The Glop 선형 해석기를 참조하십시오.

 

 

 

 

더 많은 C ++ 예제

 

 OR-Tools에는 다양한 유형의 최적화 문제를 해결하는 방법을 설명하는 여러 가지 C ++ 예제 프로그램이 포함되어 있습니다. 예제는 OR-Tools를 설치 한 디렉토리의 examples / cpp 서브 디렉토리에 있습니다.

 

다음과 같이 C ++ 예제를 실행할 수 있습니다.

 

make rcc EX=examples/cpp/linear_programming.cc

 

참고 : 규칙이 주요 Makefile의 일부이기 때문에 C ++ 예제에 대한 빌드 규칙을 만들 필요는 없습니다.

 

 

해결하려는 문제의 유형 식별

 

 세계에는 여러 가지 유형의 최적화 문제가 있습니다. 각 유형의 문제마다 최적의 솔루션을 찾기위한 다양한 접근법과 알고리즘이 있습니다. 최적화 문제를 해결하기위한 프로그램을 작성하기 전에 어떤 유형의 문제를 확인한 다음 최적의 솔루션을 찾는 알고리즘 인 적절한 솔버를 선택해야합니다.

아래에는 OR-Tools가 해결하는 문제 유형에 대한 간략한 개요와이 가이드의 각 문제 유형을 해결하는 방법을 설명하는 링크가 나와 있습니다.

 

선형 최적화
제약 조건 최적화
혼합 정수 최적화
빈 포장
네트워크 흐름
할당
스케줄링
라우팅

 

 

선형 최적화

 

 전 섹션에서 배웠 듯이 선형 최적화 문제는 목적 함수와 제약 조건이 변수에서 선형 표현식을 사용하는 문제입니다. 이런 유형의 문제를 해결하기위한 OR-Tools의 기본 솔버는 선형 최적화 솔버입니다. 실제로 써드 파티 라이브러리를 포함하여 선형 및 혼합 정수 최적화를위한 여러 라이브러리의 래퍼입니다.

 

선형 최적화에 대해 자세히 알아보기

 

 

제약 조건 최적화

 

 제약 조건 최적화 또는 제약 프로그래밍 (CP)은 문제가 임의의 제약 조건으로 모델링 될 수있는 매우 큰 후보 집합에서 실현 가능한 솔루션을 식별합니다. CP는 최적화 (최적의 솔루션 찾기)보다는 실현 가능성 (feasibility) (실현 가능한 솔루션 찾기)을 기반으로하며 목적 함수가 아닌 제약과 변수에 초점을 맞추고 있습니다. 그러나 CP는 모든 가능한 솔루션에 대한 목적 함수의 값을 단순히 비교함으로써 최적화 문제를 해결하는 데 사용될 수 있습니다.

 

제약 조건 최적화에 대해 자세히 알아보기

 

 

혼합 정수 최적화

 

 혼합 정수 최적화 문제는 일부 또는 모든 변수가 정수가되어야하는 문제입니다. 예를 들어 작업 그룹에 작업 그룹을 할당해야하는 할당 문제가 있습니다. 각 작업자와 작업에 대해 지정된 작업자가 지정된 작업에 할당되어 있으면 값이 1 인 변수를 정의하고 그렇지 않으면 0을 정의합니다. 이 경우 변수는 0 또는 1 값만 가질 수 있습니다.

 

혼합 정수 최적화에 대해 자세히 알아보기

 

 

빈 포장

 

 빈 포장 (Bin packing)은 서로 다른 크기의 물체를 서로 다른 용량의 용기에 포장하는 문제입니다. 목표는 컨테이너의 용량에 따라 최대한 많은 오브젝트를 패킹하는 것입니다. 특별한 경우는 하나의 컨테이너 만있는 배낭 문제입니다.

 

빈 포장에 대해 자세히 알아보십시오.

 

 

네트워크 흐름

 

 많은 최적화 문제는 노드와 노드 사이의 지시 된 호로 구성된 유향 그래프로 나타낼 수 있습니다. 예를 들어 철도 네트워크를 통해 상품이 운송되는 운송 문제는 호가 선로이고 노드가 유통 센터 인 그래프로 나타낼 수 있습니다. 최대 흐름 문제에서 각 호에는 최대 호이스트가 있으며이 호를 통과 할 수 있습니다. 문제는 운송되는 총 물량이 가능한 한 많아 지도록 각 호에 운송되는 물품의 양을 지정하는 것입니다.

 

네트워크 흐름에 대해 자세히 알아보기

 

 

할당

 

 할당 문제는 각 에이전트를 특정 작업에 할당하는 고정 비용이있는 작업 집합에 에이전트 그룹 (예 : 작업자 또는 시스템)을 할당하는 것과 관련됩니다. 문제는 총 비용이 가장 적은 과제를 찾는 것입니다. 할당 문제는 실제로 네트워크 흐름 문제의 특별한 경우입니다.

 

과제에 대해 자세히 알아보기

 

 

스케줄링

 

 스케줄링 문제에는 특정 시간에 작업 세트를 수행하기위한 자원 할당이 포함됩니다. 중요한 예는 여러 작업이 여러 시스템에서 처리되는 작업장 문제입니다. 각 작업은 지정된 순서로 수행되어야하는 일련의 작업으로 구성되며 각 작업은 특정 컴퓨터에서 처리되어야합니다. 문제는 모든 작업이 가능한 한 짧은 간격으로 완료되도록 일정을 지정하는 것입니다.

 

스케줄링에 대해 자세히 알아보기

 

 

라우팅

 

 라우팅 문제는 방향을 잡은 그래프로 정의 된 네트워크를 가로 지르는 차량의 차량을위한 최적의 경로를 찾는 것을 포함합니다. 최적화 문제 란?에서 설명한 배달 트럭에 패키지를 할당하는 문제는 라우팅 문제의 한 예입니다. 또 다른 것은 여행 세일즈맨 문제입니다.

 

라우팅에 대해 자세히 알아보기

 

 

 

 


Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 3.0 License, and code samples are licensed under the Apache 2.0 License. For details, see our Site Policies. Java is a registered trademark of Oracle and/or its affiliates.

 

※ 본 내용은 Google Optimization Tools 사이트에서 가져온 내용으로 구글 번역기를 통하여 한글로 게시하였습니다.

 

 

 

※ 쿠팡 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있습니다.