Press "Enter" to skip to content

CIKM 2021 | UCL、华为、复旦提出超大规模建模系统Grassland,助力华为供应链快速决策

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

以线性规划为代表的数学规划方法在制造、交通、物流、能源、金融等领域有着广泛而深刻的应用,是现代工厂排产、物流调度等关键经济活动的基石。数学规划方法首先将问题建模并转换为标准的数学规划模型(如线性规划、整数规划等),然后使用对应的开源或商业求解器进行求解,从而输出较优的产品生产量、货物转运量等关键决策信息。这些决策信息经过排产员或调度员的进一步优化、确认后,以生产任务令、调度指令的方式下发到各个工厂车间、仓库、港口、集散中心等,从而以有限的资源尽可能多地完成客户的各种订单需求。可以说,数学规划方法是制造、物流等行业的大脑中枢,以经济、高效的方式指挥着产线、车辆等海量基础设施的协同运转。而完成整个数学规划方法,将实际业务数据转换为最优决策变量值的高层系统,我们称之为“代数建模系统”(Algebraic Modeling System, AMS)。

 

 

基于数学规划方法进行商业决策的流程图,虚线框内的部分即为代数建模系统

 

然而,随着商业场景的日益复杂和产业规模的不断扩大,其所对应的数学规划模型也变得极其繁琐和庞大。不仅数学模型的表达式非常复杂,决策变量和约束的规模也动辄以百万计。这对实际执行数学规划方法的代数建模系统提出了极高的要求:不仅要快速地将海量业务数据转换为标准数学规划模型,还要快速得到高质量的可行解,从而适应风云变幻、实时性高的市场变化,在商业竞争中取得先机。

 

华为的供应链场景便是这一挑战的范例之一。一方面,华为供应链包含一百多家自有及外协工厂,以及数万原材料、中间件和成品类型,共同支撑起华为横跨智能手机、物联网、电信基础设施等领域的庞大产品版图。这些元器件之间的加工依赖、替代和转运关系极其复杂,往往需要数以百万甚至千万计的决策变量和约束,才能较为精确地描述每天在每个工厂加工的各种元器件数量、工厂间元器件转运量、原材料采购量等多类关键排产决策, 单次建模及求解的复杂度巨大,往往需要数小时 。另一方面,在美国禁运制裁(供应商不确定性陡增)、原材料成本及产能波动、订单变化等多种动态因素影响下,华为供应链的供需情况瞬息万变。华为的供应链计划部门需要及时针对当前及未来预估情况,识别可能出现供应瓶颈的元器件,并对多种可能方案进行评估,从而最终做出采购、加工等决策,以最大程度满足世界各地数以百万计的订单需求,而这些决策的关键依据正是上述数学规划引擎给出的模拟排产结果。因此,数学规划引擎需要针对各种可能出现的情况(如原材料不足,产能受限等) 快速进行建模及求解,时间限制往往是分钟级 。另外,相对高效的数学规划建模软件和求解器(如 AMPL、Gurobi)作为美国商业软件,同样对华为禁售,这更使得华为的供应链决策雪上加霜。

 

 

华为供应链供需模拟场景,需要通过供需模拟对瞬息万变的供需情况及时做出分析和评估,从而辅助最终决策。这一过程需要对百万变量的数学规划模型进行分钟级的快速建模和求解,对代数建模系统提出了极高要求

 

在以上困难的情况下,来自伦敦大学学院(UCL)、华为诺亚方舟实验室、复旦大学的研究人员提出并开发了新型的超大规模数学规划建模系统 Grassland,为上述挑战提供了一个端到端的高效解决方案。

 

 

论文地址:https://arxiv.org/abs/2108.04586

 

首先,Grassland 包含一套极为高效的代数建模语言及模型转换算法,充分挖掘真实建模数据的稀疏性和建模过程的可并行性,可以在数秒钟内将海量原始业务数据转换为百万变量的标准优化模型,比当前最先进的商业方案快 6~10 倍。然后,Grassland 针对商业场景中常见的序列模型,给出了一套启发式的有损分解方案,可以以较小的最优性损失换来数十倍的求解加速,同时严格保证解的可行性,足以满足现实商业场景的最优性需求。Grassland 现已部署在华为的大规模实际生产计划场景中,使得供应链计划部门能够快速完成供需模拟等关键任务,在器件供应受限、波动剧烈的特殊时期快速对供需情况进行建模与仿真,辅助华为供应链最终决策。相关论文现已被 CIKM 2021 全文接收。

 

1. 高效建模:如何数秒内输出百万规模的线性约束

 

对于一组决策变量,一个完整的数学规划模型由目标f(x)和约束 两部分组成,即 . 在实际商业场景中,目标f(x)对应于希望达成的商业目标(例如,最大化订单满足率,最小化成本),而约束 对应于需要遵守的商业规则和现实限制(例如,仓库的出库量与入库量之差不能大于库存量)。在大规模场景中,虽然目标往往只有一行表达式,但约束的数量却可以数以百万计,从而成为建模过程的主要瓶颈。我们接下来以经典的网络流模型为例介绍这一问题。

 

 

如图所示,可以将有向图想象成水管网络,源点 1 和汇点 4 想象成水管网络的供水口和出水口,对于任意一条有向边(i,j),有流量 ,代表从顶点 i 流到 j 的水流量。网络流问题需要满足一个自然的约束,即对于所有中间顶点,其总流出量应当等于总流入量。而对于源点和汇点,其总流出量和总流入量应当等于一个定值,即网络的总流量(简单起见令其为 1)。我们将其写作

 

 

按照公式的字面意义,我们可以对顶点集合中的所有顶点进行遍历,从而输出实际的约束如下:

 

i=1 时,找到所有满足 的元素,分别为 (1,2), (1,3) 和空集,因此有

 

 

i=2 时,找到所有满足 的元素,分别为 (2,4) 和(1,2), (3,2),因此有

 

 

i=3 时,找到所有满足 的元素,分别为 (3,2), (3,4) 和(1,3),因此有

 

 

i=4 时,找到所有满足 的元素,分别为空集和(2,4),(3,4),因此有

 

 

然而容易看出,以上过程需要对顶点集合V中的每一个元素进行迭代,每次迭代时需要遍历边集E,本质是一个二重循环,时间复杂度是O(|V||E|) 的!如果我们有数以百万计的顶点和边,这种生成约束的方法就完全行不通了。虽然针对这里的简单例子可以有一些加速方案(例如对边集E做预先索引),但通用性差,需要根据问题定制,难以根本性地解决复杂商业场景建模效率低下的问题。

 

那幺,是否存在既方便通用,又足够高效的约束生成方法呢?

 

1.1 Grassland:约束生成的高效 “种草” 算法

 

答案是肯定的。为了说明这一点,我们将约束表达式和根据数据生成的四条约束整理如下:

 

 

我们使用红色和蓝色分别标记出第一个求和表达式(总流出量)和第二个求和表达式(总流入量)在四个约束中所对应的变量项x。我们会发现,它们恰好都在四个约束中分别出现了 5 次,且完整对应于边集数据E。这是一个巧合吗?并非如此!以总流出量为例,求和符号的条件是 ,而 作为约束的下标,会遍历所有可能的取值。因此当 i 的遍历完成后,E也会被不多不少恰好遍历一次,使得四个约束里一定会出现 5 个与E一一对应的变量项x。

 

受此启发,我们可以通过以下步骤来生成约束:

 

1. 将约束左侧表达式中的所有约束下标标记出来(本例中为 i)

 

 

2. 无视表达式后的约束下标 ,直接对第一个和第二个求和表达式中的分别进行遍历,得到总计 10 个变量项。同时,每个变量项对应的约束下标值进行额外标记(这里使用红色标出)。

 

 

3. 根据上一步对每个变量项额外标注的约束下标(红色标记),对变量项进行归类(可以使用哈希表)

 

 

4. 加入等号和等式右边的值,大功告成!

 

 

以上步骤其实很类似于一个 “种草” 的过程。如果我们将线性约束 的约束矩阵视作一片土地(Land),那幺我们其实是在第 1、2 步批量生成了所有要种在这片土地上的草苗(Grass),然后在第 3、4 步将这些草苗一棵棵地种在了约束矩阵A的适当位置。这也是本系统被命名为 “Grassland” 的由来。

 

不难看出,如果我们将第三步哈希表归类的单次时间复杂度视为O(1),那幺整个约束建模过程的时间复杂度是 的!也就是说,我们仅仅是将边集数据E扫描了常数次,就完成了约束的建模过程。同时值得注意的是,这种方案的通用性极高。只要约束是线性的(绝大多数可大规模求解的模型都要求约束为线性),且求和表达式的条件都写作 “下标∈数据” 的格式,就可以使用这一方法进行约束建模,在华为供应链不同场景下数十种超大规模复杂约束下均表现出色。论文中详细讨论了上述建模过程和直接按照公式建模的等价性。

 

1.2 “联合种草机”:建模过程并行化

 

通过上述简单高效的建模算法,我们已经可以在大规模线性约束上获得远胜大多数开源建模工具,媲美商业建模软件的效率。然而,面对近年来百万甚至千万规模大小的超大模型,即使是最出色的商业建模软件也需要数十秒甚至数分钟才能完成一次转换,这对于很多需要不断迭代或序列建模优化的场景而言依然是难以接受的。而 Grassland 真正的强大之处在于,如同矩阵计算的并行化加速一样,它可以从框架层面实现完全的并行化建模,从而彻底突破大规模线性规划建模的效率瓶颈。

 

我们依旧以前面的网络流场景

 

 

为例。假设我们有两个 CPU 核,可以互不干扰地并行处理子任务,那幺是否有一种方法可以将建模任务平均分配到两个 CPU 上呢?从公式的字面意义来看,这件事情并不难。我们只需将顶点集合 平分为 ,并让两个 CPU 核分别处理,生成 ,最后合并即可,我们将这个过程称为“对约束空间的切分”。然而,正如我们前面的分析所示,大规模场景下按照公式字面意义进行建模是完全不实际的,即使能将任务平分到多个 CPU 上也不例外。

 

而 Grassland 通过将对约束空间的切分转换为对数据的切分解决了这一问题。可以通过以下步骤在两个 CPU 上并行生成约束:

 

1. 将约束左侧表达式中的所有约束下标标记出来

 

 

2. 注意到第一个求和表达式(总流出量)的条件中约束下标在第一位,第二个求和符号(总流入量)中约束下标在第二位,于是我们准备两份的副本和,一个按数据首位排序,一个按数据第二位排序,即

 

 

同时我们将约束表达式改写为

 

 

由于E_out和E_in除了顺序外没有任何区别,所以结果并不会改变。

 

3. 将排序后的数据按照对应的排序维度,在 2 和 3 之间进行切分(可以使用二分查找找到切割点),并将切分后的数据分别分配给两个 CPU 进行上一节所介绍的约束生成。即

 

 

 

 

我们会发现,通过对数据进行切分所得到的结果,恰好相当于我们将四个约束按约束下标切成两份。这并不是巧合!论文中详细讨论了约束空间切分和数据切分的等价性。有了上述基于数据切分的并行化建模方法,我们便宛如有了一台大功率的 “联合种草机”,可以充分利用大型服务器的多核计算资源,在约束矩阵的“土地” 上,以数十个 CPU 核同时进行变量项 “草苗” 的生成和种植,数秒内生成上百万变量的数学规划模型丝毫不在话下。考虑到这样规模的模型往往需要占据数百兆的磁盘空间,Grassland 的模型输出速率甚至超越了大多数机械硬盘的写入速度。若要充分感受 Grassland 的性能,请务必为服务器准备一块固态硬盘或者 RamDisk。

 

1.3 作为代数建模系统的 Grassland:Show me the code!

 

为了让一线的模型开发和研究人员迅速上手 Grassland 的建模方法,我们为 Grassland 设计了一套高层的建模 API。只要使用这套 API 的语法进行模型开发,就可以让 Grassland 全程接管建模转换过程,而无需担心效率问题。这套 API 最大的特点,是无需建模人员显式编写任何的循环语句来生成约束。仅需将模型的目标及约束表达式以计算图节点连接的形式表示,并向定义好的计算图模型中送入实际业务数据,即可迅速进行建模转换。这点与我们熟知的基于计算图的开发框架——TensorFlow 十分类似。有 TensorFlow 基础的开发者可以迅速上手。

 

为了说明 Grassland 作为代数建模系统的使用特点,我们将其与 Coin-OR 推出的流行建模框架 PuLP(https://github.com/coin-or/pulp)进行对比。对于上述的网络流问题约束

 

 

使用 PuLP 建模代码如下(为了方便起见,下标改为从 0 开始):

 

<code>import pulp</code>
<code>V = [0, 1, 2, 3]</code>
<code>E = [(0, 1), (0, 2), (1, 3), (2, 1), (2, 3)]</code>
<code>S = [1, 0, 0, -1]</code>
<code>prob = pulp.Lp</code><code>Problem()</code>
<code>x = pulp.LpVariable.dicts('x', (range(len(V)), range(len(V))))</code>
<code>for v in V:</code><code>    </code>
<code>    flow_in = pulp.lpSum(x[i][j] for i, j in E if i == v)</code><code>    </code>
<code>    flow_out = pulp.lpSum(x[i][j] for i, j in E if j == v)</code><code>    </code>
<code>    prob += flow_in - flow_out == S[v]</code>
<code>print(prob)</code>

 

可见,我们的建模过程和约束表达式的字面意义基本一致。通过外层循环(for v in V:)遍历所有顶点,并在内层的列表生成式(x[i][j] for i, j in E if i == v)遍历所有边,构造总流入量 flow_in 和总流出量 flow_out 表达式后,得到单条约束表达式 flow_in – flow_out == S[v]并添加到模型。本质上是一个二重循环。虽然代码简洁,然而O(|V||E|)的时间复杂度不尽如人意,当 V 和 E 规模较大时便无法胜任建模任务。

 

而 Grassland 的建模过程代码如下:

 

<code>import grassland as gl</code>
<code>max_V = 4</code>
<code>model = gl.Model()</code>
<code>x = gl.Variable(name='x', shape=(max_V, max_V))</code>
<code>i = gl.IndexPlaceholder(range=(0, max_V))</code>
<code>E_in = gl.Constant(shape=(max_V, max_V))</code>
<code>E_out = gl.Constant(shape=(max_V, max_V))</code>
<code>S_ = gl.Constant(shape=(max_V,))</code>
<code>flow_out = gl.cond_sum(index_placeholders(i, 'j'),cond=E_out, </code><code> expr=gl.Expression(x[i, 'j']))</code>
<code>flow_in = gl.cond_sum(index_placeholders=('j', i), cond=E_in,</code><code>expr=gl.Expression(x[i, 'j']))</code>
<code>model.add_constraint(</code><code>gl.constraint(expr=flow_in - flow_out, sense='=', rhs=S,</code><code>axes=[i], parallel_axes[i])</code><code> )</code>
<code>V = gl.COO([0, 1, 2, 3])</code>
<code>E = gl.COO([(0, 1), (0, 2), (1, 3), (2, 1), (2, 3)])</code>
<code>E_T = gl.COO([(1, 0), (1, 2), (2, 0), (3, 1), (3, 2)])</code>
<code>S = gl.COO([1, 0, 0, -1])</code>
<code>model.generate_lp(feed_dict={E_out: E, E_in: E_T, S_: S}, </code><code>    num_workers=2, filename='network_flow.lp')</code>

 

这段代码首先定义计算图中所需要的变量 x 和待定常数 E_in,E_out(很类似于 TensorFlow 1.X 中的 tf.get_variable()和 tf.placeholder()。同时,我们使用 i = gl.IndexPlaceholder()这一 Grassland 中的特殊类型来定义约束下标。

 

接下来,构建总流入量 flow_in 和总流出量 flow_out 表达式,这一部分无需对约束下标 i 的所有可能取值进行循环遍历,而是使用 Grassland 中的计算图节点 gl.cond_sum 构造出表达式 。gl.cond_sum 包含三个参数:下标 index_placeholders、数据 cond 和表达式,即

 

 

下标 index_placeholders:传入一个 Python 元组,依次列出与数据对应的下标。其中,约束中出现的下标(例如前文中使用红色标识的下标 i,在论文中称为全局下标,global index placeholder)使用 gl.IndexPlaceholder()定义,而其他在求和符号中局部使用的下标(例如网络流约束中的下标 j,在论文中称为局部下标,local index placeholder)使用 python 字符串定义。例如,可以传入 描述 的下标部分(红色标出)。

 

数据 cond:传入一个 gl.Constant 对象,作为计算图的占位符以供后续传入实际数据。值得注意的是,Grassland 使用稀疏张量(Sparse Tensor)来表示数据。例如,E = [(0, 1), (0, 2), (1, 3), (2, 1), (2, 3)] 可以被视为一个 4×4 的布尔类型二维张量(矩阵)的稀疏表示形式。特别值得注意的是,稀疏张量数据默认按照第一个维度进行排序,因此对于总流出量 ,我们将其改写为 ,将数据的第二个维度和第一个维度交换,并按照交换后的第一个维度(原第二个维度)排序即可。

 

表达式 expr:传入一个 gl.Expression 对象,可以是经由其他计算节点处理后的表达式,也可以是一个叶子节点表达式,由变量和变量系数(默认为 1)表示。例如,可以传入叶子结点表达式 来描述 的表达式部分(红色标出)。

 

然后,构建约束对象 gl.constraint 并使用 model.add_constraint 方法添加到模型。约束需要指定约束公式的左表达式 expr、符号 sense( 或=)和右边的常数项 rhs。除此以外,还需指定约束下标 axes,列出所有在约束中使用的下标维度。例如,针对网络流约束的而指定 axes=[i]。在大规模排产模型中,约束往往至少有三维,即时刻 t – 工厂 p – 产品编号 i,此时需要指定 axes=[t, p, i]。为了进行并行化建模,还需指定用于进行数据切分的下标维度 parallel_axes,一般指定约束的第一个下标维度即可。

 

至此,我们已经完成了模型计算图的构建。我们可以在这一步导出模型留作后续使用(类似于 TensorFlow 中的 SavedModel), 也可以直接进行模型转换任务。当我们获得了实际的业务数据时(例如网络流约束中的 V、E 和 S),我们首先将其转换为 COO 格式(Coordinate List)的稀疏张量,然后执行模型的 generate_lp 方法并使用 feed_dict 参数传入数据(一个字典,键为计算图里的占位符,值为实际数据,非常类似于 TensorFlow 1.X 中 session.run 的 feed_dict 参数),指定并行线程数 num_workers 和输出文件名 filename。Grassland 将模型计算图和数据传入 C++ 实现的高效后端,并行执行前文所介绍的 “种草” 快速建模算法,即可得到标准的数学规划模型文件。尽管使用上相较 PuLP 稍显繁琐,然而其效率不可同日而语。即使数据规模达到百万级别,Grassland 也能在顷刻之间完成建模转换。

 

 

 

在部分经典数学规划模型上,使用百万规模数据进行的性能测试。可见 Grassland 具备数量级的优势。(PuLP 由于实在过于低效而不在此性能测试之列)

 

2. 高效求解:如何提升大规模商业数学规划模型的求解效率

 

当我们突破建模过程的效率瓶颈后,接下来的挑战便是如何快速获得较优的严格可行解。一个自然的想法是开发速度更快的数学规划求解器,然而这一领域自上世纪 80 年代起已经过了数十年的发展,想要在通用场景下大幅超过 Gurobi、Cplex 等高度成熟的商业求解器方案并不现实。不过,虽然当前成熟的求解器求解上百万规模的模型相当吃力(数十分钟甚至数小时),但求解数万至数十万变量的中小规模模型却是很轻松的(数十秒甚至数秒)。由此,我们考虑另一种思路,即分析大规模商业数学规划模型的特点,将复杂的大模型分解成若干易于求解的中小模型,从而减轻求解器负担,达到快速求解的目的。

 

商业场景下的数学规划模型之所以体量巨大,除去业务规模本身的因素以外,还有一个重要原因,是这类模型往往需要进行序列化的动态决策。例如,在供应链排产场景下,需要决策所有元器件在整个排产周期 T 内的生产量,周期内的每一个时刻 t 都需要有一个单独的决策变量。也就是说,决策变量的数目和决策周期 T 成正比。或许单个时刻内的决策变量并不多(上万或者数十万),但当决策周期 T 较大时,数学规划模型就会迅速膨胀,让求解器不堪重负。

 

那幺,我们是不是只要对决策周期 T 进行简单的切分就行呢?例如,对于 28 天的排产周期,我们将其分成 4 份,首先排产 1-7 天,然后排产 8-14 天,以此类推。这样每次排产时求解器只需要求解原先 1/4 规模的模型,如果我们根据经验性的求解时间复杂度 (N为决策变量数量)推断,分解后的求解时间会是直接求解的 ,不可谓不快。如果分解的块数更多,速度提升甚至会更加显着。我们将这种方式称之为“滚动时域求解”(Rolling Horizon,RH)。然而,这样做有一个致命的缺点,就是模型的决策将非常“短视”,每次决策都只关注于当前小的决策片段的局部最优性,而无法顾及全局。例如,若在排产周期的第 28 天对某物品有一个大的订单需求,且生产该物品需要 10 天,那幺第 1-7、8-14、15-21 天的决策中都不会考虑这一需求,从而不进行足量的生产,而等到第 22-28 天开工生产已为时晚矣。分块的数量越多,短视的现象就越严重,从而严重影响到模型决策的最优性。

 

为了改善决策的全局最优性,一个较为简单的方式是在当前的决策片段中加入 “聚合” 后的未来信息。例如,在求解第 1-7 天的排产模型时,我们将第 8-28 天的所有订单需求和供应信息进行聚合,作为 “虚拟” 的第 8 天加入到 1-7 天排产模型的末尾,形成一个 8 天的模型。在求解第 8-14 天的排产模型时也聚合第 15-28 天的信息,以此类推。通过这种方式,当前决策片段的模型可以在一定程度上感知到未来信息,从而提升全局最优性。

 

 

而在论文中,我们提出另一种改善全局最优性的方式,即 “基于粗粒度引导的滚动时域求解”。这种方式首先将数据分段聚合,并求解一个粗粒度的数学规划模型,然后使用粗粒度模型的解,对细粒度滚动时域求解的子问题进行“引导”,以让细粒度子问题求解结果的聚合值与粗粒度模型的解尽可能一致。还是以 28 天的排产模型为例,我们首先将数据按周(7 天)进行聚合,形成一个以周为单位,决策周期为 4 的聚合数据,并以此建立一个 4 周的“粗粒度模型”。由于数据被聚合,这个粗粒度模型决策周期仅为 4,远小于全规模模型。求解该模型后,我们得到了每个器件每一周应该进行的生产量。接下来,我们进行滚动时域求解,同时在求解第 1-7 天的排产模型时,加入额外的软性约束(惩罚项),要求第 1 天到第 7 天的生产量之和与粗粒度模型求解得到的“第 1 周总生产量” 尽可能接近(将距离的绝对值罚到目标函数上),以此类推。通过这种方式,我们让每个决策片段求解的时候同时考虑到粗粒度模型所包含的全局信息,从而提升全局最优性。

 

 

这两种改善全局最优性的方式在实际运用中各有千秋。然而细心的读者可能注意到,这两种方法并没有任何冲突的地方,即使同时使用也没有任何问题。正所谓,小孩子才做选择,成年人:我都要。

 

于是,我们将两种方法进行聚合,从而得到了最终方案。

 

 

值得一提的是,当我们使用上述方式求解完成并得到整个决策周期的一组可行解后,我们依然有方法进一步提升解的全局最优性。注意到在整个决策周期中,我们更关注较为靠前时刻的决策变量取值,因为这部分决策往往需要业务部门及时响应执行。因此,我们也更希望提升这部分决策变量的全局最优性。为了达成这一目的,我们可以 “释放” 前若干个时刻的求解结果,而固定后面所有时刻的解,从而在全决策周期的层面对模型进行重解。虽然这里需要求解全决策周期尺寸的模型,但由于其中大部分决策变量的值都已经固定,因此实际待求解的决策变量规模依然是可接受的。同时,由于原始解已经是问题的一组可行解,释放部分变量并重新求解的结果一定不会差于原始解。

 

 

我们将上述分解方案集成进 Grassland 建模系统,并在华为供应链 78 周的供需模拟场景(决策变量数约 600 万,约束数约 350 万)下对性能进行了端到端的测试,结果如下图所示。可见 Grassland 建模算法结合我们提出的分解方案(G-FRH),可以将建模 + 求解的端到端时间从原始的约 4000 秒缩减到 200 秒左右,而最优性的损失仅为千分之 3.6。若加入重解机制,损失还可以进一步压低到千分之 3.3。考虑到商业建模场景中有着许多更为决定性的误差来源(例如对未来的数据预测误差,建模本身简化问题带来的误差),在保证严格可行性的前提下,千分之三左右的最优性误差几乎可以忽略不计。而近 20 倍的速度提升意味着供应链部门能够以近乎实时的速度获取各种场景下的模拟排产结果,从而高效、快速地进行方案迭代和最终的生产、采购决策,从而在风云变幻的市场变化和商业竞争中取得先机。

 

 

Grassland 在华为 78 周供需模拟场景下的端到端性能测试结果。蓝色部分为建模时间,红色部分为求解时间。

 

以上分解算法的核心是将大问题拆分成多个小问题进行建模与求解,而 Grassland 中的高效建模算法能进一步加速上层分解算法在实施中的效率,建模与求解模块相辅相成。主要建模语言都拥有自己的算法库,Grassland 的算法库后续也会持续结合具体的序列化问题进行不断完善。

 

 

GrassLand软件架构

 

当前 Grassland 开发团队也在积极将此项工作作为软件部署在华为公有云上,预计将于今年年底前发布一个公开的版本,希望帮助广大开发者解决实际的优化问题。

 

作者简介

 

本研究由来自伦敦大学学院(UCL)汪军教授团队、华为诺亚方舟实验室企业智慧团队、复旦大学的研究人员共同完成。主要作者包括:

 

李锡涵,伦敦大学学院计算机系博士研究生,主要研究方向为学习优化,在 AAMAS、CIKM、COLING 发表学术论文。TensorFlow技术专家,开源技术手册《简明的 TensorFlow 2》(https://tf.wiki)作者。

 

韩雄威,研究生毕业于华中科技大学管理科学与工程专业,现任华为诺亚方舟实验室高级研究员,供应链高级算法科学家,主要研究方向为运筹学、学习优化等技术,致力将其运用于供应链领域的组合优化问题。

 

周之烁,本硕毕业于复旦大学大数据学院。硕士研究生期间师从江如俊副教授,研究方向为最优化算法、非凸优化。

 

*注:公开发布的 Grassland 在部分 API 名称,数据封装方式等细节上可能与本文中展示的 Grassland 示例代码有所差异,请以最终发布版本为准。

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注