适用于 C++ 的 OR-Tools 使用入门

以下部分将帮助您开始在 C++ 中使用 OR 工具：

• 什么是优化问题？
• 解决使用 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 工具中用于此类问题的主要求解器是线性优化求解器，它实际上是多个用于线性和混合整数优化（包括第三方库）的不同库的封装容器。

详细了解线性优化

混合整数优化

混合整数优化问题是指部分或全部变量必须为整数。例如分配问题，需要将一组工作器分配给一组任务。您可以为每个工作器和任务定义一个变量，如果将指定工作器分配给了给定任务，则该变量的值为 1，否则为 0。在本例中，变量只能采用 0 或 1 的值。

详细了解混合整数优化

限制条件优化

约束优化或约束编程 (CP)，可在大量候选集合中确定可行的解决方案，根据任意约束条件对问题进行建模。CP 基于可行性（找到可行的解决方案）而非优化（找到最佳解决方案），并且侧重于约束条件和变量，而非目标函数。不过，CP 可用于解决优化问题，只需比较所有可行解决方案的目标函数值即可。

详细了解限制条件优化

分配

分配问题涉及将一组代理（例如工作器或机器）分配给一组任务，将每个代理分配给特定任务具有固定的费用。问题在于找到总费用最低的分配。分配问题实际上是网络流问题的特殊情况。

详细了解分配

打包

装箱是指将一组不同大小的对象打包到具有不同容量的容器中的问题。目标是根据容器的容量来打包尽可能多的对象。这种特殊情况是 Knapsack 问题，其中只有一个容器。

详细了解装箱

调度

调度问题涉及分配资源以在特定时间执行一组任务。一个重要的示例是求职招聘问题，即在多台机器上处理多个作业。 每个作业都由一系列任务组成，这些任务必须按给定顺序执行，并且每个任务都必须在特定的机器上处理。问题在于如何分配时间表，以便在尽可能短的时间间隔内完成所有作业。

详细了解时间安排

路由

路线规划问题涉及为车队寻找遍历网络的最佳路线，由有向图定义。什么是优化问题？中描述的将包裹分配给送货卡的问题就是路线问题的一个示例。另一个是旅行推销员问题。

详细了解路由

网络流

许多优化问题都可以由由节点和有向弧线组成的有向图表示。例如，运输问题（其中商品通过铁路网运）可以用图表表示，其中弧线是铁路线，节点是配送中心。

在“最大流”问题中，每条弧形都有可以跨越传输的最大容量。问题是分配要在各个弧形运输的商品量，使运输总量尽可能大。

详细了解网络流