乐趣区

关于算法:运筹优化工具ortools解读与实践概览

jiezi

背景

在咱们的工作和生存中，有十分多带有束缚的问题须要解决。例如，

  • 在估算无限的状况下，如何买到区位、学区、楼龄、户型都比较满意的房子？
  • 散布在北京各个地区的几个哥们要聚餐，抉择哪个餐厅能力让大家通行间隔比拟靠近，餐厅口味也不错？
  • 公司有一个由 10 辆车组成的车队，从仓库登程为 100 家企业配送物资，每家企业都有不同的收货工夫窗口，物资体积、分量也各不相同，同时，车辆有其最大载容、载重及最大行驶间隔。如何做车辆与企业匹配和门路布局，可能满足要求的同时最小化老本？

解决这类问题有比拟罕用的套路，即便不理解运筹优化底层原理，也可能疾速解决问题：

  1. 定义问题
  2. 建模问题
  3. 利用成熟的求解器求解问题

在求解器中，能够分为商业求解器和开源求解器。财大气粗的传统行业以购买商业求解器为主，通常解决的问题规模大、计算性能好；互联网公司以开源求解器为主，稍逊色，益处是收费，个别场景下也够用了。当然，如果问题比拟非凡（e.g. 时效要求较高），须要自行编码实现求解过程。

咱们接下来要介绍的 ortools 是 google 开源的一种运筹优化工具。之所以称为“工具”，是因为 ortools 不仅自研了 cpsat 求解器，也提供了对开源求解器（e.g.SCIP）、商业求解器（Gurobi、CPLEX）的反对。

须要补充一点，不同的求解器 / 工具有其善于之处。就算是开源工具，不同工具也各自优劣。例如，ortools 提供了线性规划、整数布局、束缚布局以及后续 VRP 问题、网络流问题等场景化利用，但 ortools API 非常匮乏，相干材料较少；jsprit 则聚焦在 VRP 问题，我的项目整体具备比拟好的设计理念，非常适合公司层面的我的项目开发，毛病也比拟显著，它只反对 VRP 问题。

本系列次要以 ortools 官网指南为底本，从理论利用的角度登程，解读 ortools 工具，并提供应用案例及代码解读。

外围模块

外围模块大体能够分为两局部，后面 3 个模块是根底性能：

  • 线性规划（Linear Optimization）
  • 整数布局（Integer Optimization）
  • 束缚布局（Constraint Optimization）

前面 5 个模块并重场景利用：

  • 调配（Assignment）
  • 门路布局（Routing）
  • 装箱（Bin Packing）
  • 网络流（Network Flows）
  • 调度（Scheduling）

根底性能

线性规划

线性规划问题指，指标函数和约束条件都为线性的优化问题。
例如，

$$
\begin{equation}
\begin{array}{r}
\operatorname{maximize} x_{1}+2 x_{2} \\
\text {subject to} x_{1}+x_{2} \leq 3 \\
x_{2} \leq 2 \\
x_{1} \geq 0 \\
x_{2} \geq 0
\end{array}
\end{equation}
$$

几何含意：在可行域内（4 条实线突围的蓝色区域）挪动指标函数（虚线），使得指标函数最大化。

整数布局

整数布局个别指 束缚变量含有整数 的优化问题。
例如，常见的背包问题

设有一个背包，其最大承重为 b，思考 n 件物品，其中第 j 件分量为 \(a_j \)，其价值为 \(c_j\)。问如何选取物品装入背包中，使得背包内物品的总价值最大？

设决策变量 \(x_j\)取值 0 或 1，示意是否抉择该物品。则背包问题能够示意为下列整数布局：

$$
\begin{array}{c}
\max _{x} \sum_{j=1}^{n} c_{j} x_{j} \\
\text {s.t.} \quad \sum_{j=1}^{n} a_{j} x_{j} \leq b \\
x \in\{0,1\}^{n}
\end{array}
$$

这类问题，决策变量通常是离散的。

整数布局大体能够分为以下几类。

  • 线性整数布局（Integer Linear Programming）：指标函数为线性，束缚为线性，决策变量只含有整数变量的整数布局问题。线性整数布局问题目前是整数布局问题中钻研最多，也是算法绝对比拟成熟一点的畛域。
  • 0- 1 线性规划（Binary Linear Programming）：指标函数为线性，束缚为线性，决策变量只含有 0 - 1 变量的整数布局问题。线性整数布局都能够转化为 0 - 1 线性规划问题。
  • 混合整数线性规划（Mixed-integer Linear Programming）：指标函数为线性，束缚为线性，决策变量既含有整数变量也含有连续变量的整数布局问题。
  • 非线性整数布局（Nonlinear Integer Programming）：指标函数和束缚中至多有一个是非线性的，决策变量只含有整数变量的整数布局问题。非线性整数布局的难度要比线性整数布局问题难很多。
  • 0- 1 非线性布局（Nonlinear Binary Programming）：指标函数和束缚中至多有一个是非线性的，决策变量只含有 0 - 1 变量的整数布局问题。
  • Mixed-integer Nonlinear Programming（0- 1 非线性混合整数布局）：指标函数和束缚中至多有一个是非线性的，决策变量既含有整数变量也含有连续变量的整数布局问题。
  • Polynomial Binary Programming（0- 1 多项式布局）：指标函数和束缚中都是多项式函数，决策变量只含有 0 - 1 变量的整数布局问题。

在工作中，为了疾速解决，通常会利用 trick 将各类问题简化为前 3 类整数布局问题。

束缚布局

束缚布局指求解满足各项束缚的可行解的问题。与线性规划、整数布局不同，束缚布局更加关注可行解，没有明确的优化指标。当然，束缚布局也能够求解最优化问题，将来会具体解读。

例如，后续章节中呈现的员工排班问题，就是十分典型的束缚布局问题。

利用模块

调配

调配问题即供需双方的匹配问题。特地的，最近几年 O2O 公司崛起，滴滴司机订单调配、外卖配送员订单调配等问题层出不穷，除了传统最优化的指标，时效性、高并发等性能要求更加被关注。

门路布局

门路布局是比拟常见的运筹优化问题，滴滴、美团、京东、顺丰等简直所有波及物流的公司都会与门路布局有千头万绪的分割。在 ortools 中，VRP 模块提供了简直全副的罕用变种，例如，TSP、VRP、VRPTW、CVRP 等。在前公司就已经利用 ortools 的门路布局模块解决车辆调度与门路布局问题。

装箱

装箱问题在工业界利用场景不多，然而一个十分难的算法问题。后续会比照背包问题与装箱问题的异同。如果有机会，会尝试分享物流行业外面装箱问题的利用。

网络流

网络流问题，实质是将网络关系的先验常识利用起来的过程，通常，解决同样的问题，网络流算法比传统整数布局或线性规划算法效率更高。

调度

调度问题由来已久，不论是经典的车间调度问题、传统的护士排班问题，还是外卖员排班、便当蜂员工排班、配送员排班，都能够归类到调度的领域。差别仅仅在于不同场景下，商业诉求不同，束缚也就不同。

结语

本文简略介绍 ortools 各模块的内容，在后续文章中将具体介绍如何应用 ortools 各模块。

参考

1.https://developers.google.cn/…
2. 图片参考自 https://zhuanlan.zhihu.com/p/…
3. 局部实践形容参考自 https://zhuanlan.zhihu.com/p/…

退出移动版