此页面由 Cloud Translation API 翻译。

适用于 Java 的 OR-Tools 使用入门

以下各部分将帮助您开始使用适用于 Java 的 OR-Tools：

什么是优化问题？
在 Java 中解决优化问题
更多 Java 示例
确定您想要解决的问题类型

什么是优化问题？

优化的目标是从大量可能的解决方案中找到问题的最佳解决方案。（有时，您会对找到任何可行的解决方案感到满意；OR-Tools 也可以做到。）

下面是一个典型的优化问题。假设一家货运公司使用卡车车队将包裹运送给客户。该公司每天都必须将包裹分配给卡车，然后为每辆卡车选择配送路线。每种可能的包裹和路线分配都具有费用，具体取决于卡车的总行程距离，可能还包括其他因素。问题在于选择费用最低的软件包和路由的分配。

与所有优化问题一样，此问题也具有以下元素：

目标 - 您要优化的数量。在上面的示例中，目标是最大限度地降低费用。若要设置优化问题，您需要定义一个函数，用于计算任何可能的解决方案的目标值。这称为目标函数。在前面的示例中，目标函数将计算任何套餐和路由分配的总费用。

最佳解决方案是指目标函数的值是最佳的解决方案。（“最佳”可以是上限值，也可以是下限值。）
限制条件 - 根据问题的具体要求，对一组可能的解决方案施加的限制。例如，如果货运公司无法将超过给定重量的包裹分配给卡车，则会对解决方案施加限制。

可行解决方案是指满足问题的所有给定约束条件（但不一定是最优的解决方案）。

解决优化问题的第一步是确定目标和限制。

解决使用 Java 的优化问题

接下来，我们将举例说明优化问题，说明如何在 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.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");
```
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 &leq; x ≤ 1 和 0 &leq; y ≤ 2) 已由变量的定义设置。以下代码定义了约束条件 x + y &leq; 2：

// Create a linear constraint, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 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 方法声明这是个最大化问题。

调用求解器并显示结果。

solver.solve();
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.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();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // 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());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 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();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  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

确定您希望解决的问题类型

全球优化问题的类型多种多样。每种类型的问题都有不同的方法和算法，可用于找到最优解决方案。

在开始编写用于解决优化问题的程序之前，您需要确定要处理的问题类型，然后选择合适的求解器（一种用于找到最佳解决方案的算法）。

下文简要介绍了 OR-Tools 可解决的问题类型，并提供了指向本指南中介绍如何解决每种问题类型的各个部分的链接。

线性优化
限制条件优化
混合整数优化
分配关系
时间安排
打包
转送
网络流

线性优化

如上一部分中所述，线性优化问题是指目标函数和约束条件是变量中的线性表达式的问题。

OR-Tools 中用于此类问题的主要求解器是线性优化求解器，它实际上是多个用于线性和混合整数优化的不同库（包括第三方库）的封装容器。

详细了解线性优化

混合整数优化

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

详细了解混合整数优化

限制条件优化

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

详细了解限制条件优化

分配

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

详细了解分配

打包

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

详细了解装箱

正在安排

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

详细了解时间安排

路线

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

详细了解路由

网络流

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

在最大流问题中，每条弧形都具有一个可在其间传输的最大容量。问题在于分配要在各个弧形区域装运的商品量，以便尽可能多地运输总数量。

详细了解网络流