開始使用 C++ 適用的 OR-Tools

以下各節將協助您開始使用 OR-Tools，搭配 C++：

• 什麼是最佳化問題？
• 解決 C++ 中的最佳化問題
• 更多 C++ 範例
• 確定您想要解決的問題類型

什麼是最佳化問題？

最佳化的目標是透過眾多可能的解決方案找出最佳解決方案。(有時您會滿意找到任何可行的解決方案；或者，OR 工具也能滿足您的需求)。

這是常見的最佳化問題。假設某家貨運公司使用卡車運送給客戶，公司每天都必須將包裹指派給卡車，然後為每個卡車選擇路徑來遞送包裹。視卡車的總行駛距離和其他因素而定，每個可能的包裹和路線指派作業都會產生費用。問題是選擇費用最低的套件和路徑指派作業。

如同所有最佳化問題，這個問題具有下列要素：

• 目標：要最佳化的數量。在上述範例中，目標是盡可能降低費用。 如要設定最佳化問題，您必須定義函式，針對任何可能的解決方案計算目標值。這就是「目標函式」。在上述範例中，目標函式會計算任何套件和路徑指派作業的總費用。

  「最佳」解決方案是指目標函式的值最佳。(「最佳」可能是最大值或最小值)。

• 限制：根據問題的特定需求，限制一組可能的解決方案。舉例來說，如果貨運公司無法將指定權重以上的包裹指派給卡車，就會對解決方案設下限制。

  「可行」的解決方案是指能夠滿足問題的所有指定限制，卻又無法達到最佳狀態的方法。

解決最佳化問題的第一步，就是找出目標和限制。

解決 C++ 中的最佳化問題

接下來，我們會舉例說明最佳化問題，並示範如何在 C++ 中設定及解決問題。

線性最佳化範例

線性最佳化 (或線性程式設計) 是最舊且最廣泛使用的最佳化領域之一，其中目標函式與限制可以寫成線性運算式。以下是這類問題的簡單範例。

將 3x + y 最大化，但必須遵守下列限制：

1. 0 ≤ x ≤ 1
2. 0 ≤ y ≤ 2
3. x + y ≤ 2

本例中的目標函式為 3x + y。目標函式和限制都是由線性運算式提供，因此為線性問題。

解決問題的主要步驟

每種語言的基本步驟都是相同的：

1. 匯入必要的程式庫
2. 宣告解題工具。
3. 建立變數
4. 定義限制條件
5. 定義目標函式
6. 叫用解題工具
7. 顯示結果。

C++ 程式

本節逐步介紹如何設定並解決問題的 C++ 程式。

注意： 本章節結尾處會顯示完整的 C++ 程式以及執行程式的步驟。

步驟如下：

• 匯入必要程式庫。

  #include <cstdlib>
  #include <memory>
  
  #include "absl/flags/flag.h"
  #include "absl/log/flags.h"
  #include "ortools/base/init_google.h"
  #include "ortools/base/logging.h"
  #include "ortools/init/init.h"
  #include "ortools/linear_solver/linear_solver.h"

• 宣告解題工具。

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  MPSolver 包裝函式可用於解決任何線性程式設計或混合整數程式設計問題。
• 建立變數。

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");
  
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

• 定義限制。前兩個限制條件 0 ≤ x ≤ 1 和 0 ≤ y ≤ 2 已由變數的定義設定。以下程式碼定義了限制 x + y ≤ 2：

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);
  
  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  方法 SetCoefficient 會在限制條件的運算式中設定 x 和 y 的係數。
• 定義目標函式。

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  SetMaximization 方法宣告此情況是最大化問題。
• 叫用解題工具並顯示結果。

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();
  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }
  
  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

完成計畫

完整計畫如下所示。

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

執行 C++ 程式

您可以按照下列步驟執行上述程式：

1. 複製上述程式碼並貼到新檔案中，然後儲存為 program.cc。
2. 在安裝 OR-Tools 的目錄頂層開啟指令視窗，然後輸入：

   make run SOURCE=relative/path/to/program.cc

   ，其中 relative/path/to/ 是儲存程式的目錄路徑。

注意： 您必須在安裝 OR-Tools 的目錄頂層執行上述指令。

程式會傳回可將目標函式最大化的 x 和 y 值：

Solution:
x =  1.0
y =  1.0

如要在不執行程式的情況下直接編譯程式，請輸入：

make build SOURCE=relative/path/to/program.cc

在選擇模式下進行編譯

如要在 O3 模式中編譯：

make DEBUG='-O3' all

執行 C++ 執行檔

使用 make 編譯 OR-Tools C++ 程式時，系統會在 bin 目錄中建立執行檔。您可以按照下列步驟執行範例程式的執行檔：

cd bin && ./program

如果您對程式做出變更，必須如上所示重新編譯程式。

更多 C++ 範例

如需更多 C++ 範例，說明如何解決各種最佳化問題，請參閱範例。

確定您想要解決的問題類型

世上有許多不同類型的最佳化問題，每種問題都有不同的方法和演算法，能找出最佳解決方案。

在開始編寫能夠解決最佳化問題的程式之前，您需要先找出要解決的問題類型，然後選擇適當的「解決方案」；這是用來找出最佳解決方案的演算法。

以下簡單介紹 OR 工具本身的問題類型，並提供本指南中各問題的解決步驟連結。

• 線性最佳化
• 限制最佳化
• 混合整數最佳化
• 作業
• 排程
• 包裝
• 轉送
• 網路流程

線性最佳化

如上一節所述，線性最佳化問題是指目標函式和限制在變數中的線性運算式。

在 OR-Tools 中，這類問題的主要解題器是線性最佳化解題工具，它其實是數個不同程式庫的線性和混合整數最佳化包裝函式，包括第三方程式庫。

進一步瞭解線性最佳化

混合整數最佳化

混合整數最佳化問題是指部分或所有變數必須為整數。其中一個例子就是「指派問題」，其中一組工作站必須指派給一組工作。如果將指定的工作站指派給特定工作，您可以為每個工作站和工作定義一個變數，其值為 1，否則為 0。在本例中，變數只能採用 0 或 1 值。

進一步瞭解混合整數最佳化

限制最佳化

限制最佳化或限製程式設計 (CP) 會從極大量的候選項目中找出可行的解決方案，並根據任意限制來建模問題。CP 是以可行性 (尋找可行的解決方案) 為基礎，而不是最佳化 (尋找最佳解決方案)，其重心在於限制和變數，而非客觀功能。不過，CP 還是可以用來解決最佳化問題，只要比較所有可行解決方案的客觀函式值即可。

進一步瞭解限制最佳化

指派項目

「指派問題」是指指派一組代理程式 (例如工作站或機器) 給一組工作，並有固定的費用將每個代理程式指派給特定工作。問題是找出總費用最低的作業。指派問題其實是網路流問題的特殊案例。

進一步瞭解指派作業

打包

特徵分塊是指將一組不同大小的物件封裝到具有不同容量的容器中的問題。目標是依據容器的容量，盡可能封裝最多物件。這類的特殊情況是 Knapsack 問題，該問題只有一個容器。

進一步瞭解分裝包

排程

「排程問題」是指指派資源，以便在特定時間執行一組工作。其中一個重要的例子就是工作坊問題，在這個問題中，多項工作會在多部機器中處理。每個工作都是由一系列的工作組成，而這些工作必須依照特定順序執行，而且每個工作都必須在特定機器上處理。問題是指派時間表，讓所有工作盡可能在短時間內完成。

進一步瞭解排程功能

轉送

路徑問題是指為車輛機群找出最佳路線，以便週遊網路 (由有向圖定義)。如什麼是最佳化問題？一節所述，將套件指派給傳送貨車會產生問題。這是轉送問題的範例。另一個問題則是旅行的銷售人員問題。

進一步瞭解轉送功能

網路流

許多最佳化問題可以用有向圖表示，其中包含節點和各節點之間的有向弧線。舉例來說，如果交通問題 (商品透過鐵路網路的運送方式) 能以圖表表示，弧形為鐵線，節點則為配送中心。

在「最大流程問題」中，每個弧形內都有可傳輸的容量上限。問題是指派各弧形上的商品運送數量，盡可能讓總運送數量盡可能增加。

進一步瞭解網路流程