乐趣区

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

背景

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

  • 在估算无限的状况下,如何买到区位、学区、楼龄、户型都比较满意的房子?
  • 散布在北京各个地区的几个哥们要聚餐,抉择哪个餐厅能力让大家通行间隔比拟靠近,餐厅口味也不错?
  • 公司有一个由 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/…

退出移动版