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

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

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

什麼是最佳化問題？

最佳化的目標是從一組可能的解決方案中找出「最佳」解決方案。(有時您一定可以找到任何可行的解決方案，「或工具」也可以滿足您的需求)。

下列是常見的最佳化問題。假設某間運輸公司透過一批卡車將包裹送到客戶。公司每天都必須指派包裹給卡車，然後為每個卡車選擇路線來運送包裹。每項可能的套裝行程和路線指派都會產生費用，根據卡車的總行駛距離，也可能還有其他因素。問題是選擇費用最低的套件和路徑指派作業。

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

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

  「最佳」解決方案是指最適合目標函式的值。(「最佳」可以是上限或下限)。

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

  「可行」解決方案可滿足問題的所有指定限制，且無須達到最佳狀態。

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

在 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 <memory>
  #include <ostream>
  
  #include "ortools/linear_solver/linear_solver.h"

• 宣告求解器。

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));

  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 &leq；x ≤ 1 和 0 &leq；y ≤ 2) 已由變數的定義設定。以下程式碼定義了 x + y &leq 限制；2：

  // Create a linear constraint, 0 <= x + y <= 2.
  MPConstraint* const ct = solver->MakeRowConstraint(0.0, 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 宣告這是最大化問題。
• 叫用解題工具並顯示結果。

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

完成計畫

完整計畫如下所示。

#include <memory>
#include <ostream>

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));

  // 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, 0 <= x + y <= 2.
  MPConstraint* const ct = solver->MakeRowConstraint(0.0, 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();

  solver->Solve();

  LOG(INFO) << "Solution:" << std::endl;
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();
}
}  // namespace operations_research

int main() {
  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++ 範例，說明如何解決各種最佳化問題，請參閱「範例」。

確定想要解決的問題類型

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

在開始編寫程式以解決最佳化問題之前，您需要先確定自己正在處理的問題類型，然後選擇適當的「solver」，也就是用於找出最佳解決方案的演算法。

下方將簡要介紹 OR 工具本身的問題類型，並提供本指南章節的連結，說明如何解決每種問題類型。

• 線性最佳化
• 限制最佳化
• 混合整數最佳化
• 指派
• 排程
• 封裝
• 轉送
• 網路流程

線性最佳化

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

就這類問題而言，OR-Tools 中的主要解題工具是線性最佳化解題工具，實際上是數個不同程式庫的包裝函式，用於線性和混合整數最佳化，包括第三方程式庫。

進一步瞭解線性最佳化

混合式整數最佳化

「混合整數最佳化」問題是指部分或所有變數需要為整數。舉例來說，指派問題就是需要將一組工作站指派給一組工作。對於每個工作站和工作，您可以定義一個變數，若指定的 worker 已指派給指定工作，該變數的值會是 1，反之則定義為 0。在這種情況下，變數只能採用 0 或 1 的值。

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

限制最佳化

限制最佳化或限製程式設計 (CP) 會從非常大量的候選內容中找出可行的解決方案，其中可根據任意限制條件模擬問題。CP 是以可行性 (尋找可行的解決方案) 為主，而非最佳化 (尋找最佳解決方案)，並著重在限制和變數，而非目標函式。不過，只要比較所有可行解決方案的目標函式值，CP 就可以用來解決最佳化問題。

進一步瞭解限制最佳化

指派項目

指派問題涉及將一組代理程式 (例如工作站或機器) 指派給一組工作，其中每個代理程式指派給特定工作都有固定費用。問題是找出總費用最低的指派。指派問題實際上是發生網路流程問題的特殊情況。

進一步瞭解作業

打包

特徵分裝是將一組不同大小的物件封裝到具有不同容量的容器時發生的問題。我們的目標是根據容器的大小，盡可能封裝更多物件。其中一個特殊情況是 Knapsack 問題，其中只有一個容器。

進一步瞭解分裝箱

排程

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

進一步瞭解如何排程

路線

轉送問題涉及為車隊尋找最佳路線，以周遊網路 (以方向圖定義)。按照「什麼是最佳化問題？」所述，將套件指派給遞送貨車的問題是轉送問題的其中一個例子。另一個則是旅行銷售人員問題。

進一步瞭解轉送功能

網路流程

許多最佳化問題都可以透過包含節點和兩者之間的有向弧形的有向圖表示。舉例來說，交通問題透過鐵路網路出貨時，可透過圖表呈現，其中弧形為軌道，節點是配線中心。

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

進一步瞭解網路流程