整数格上的供应链库存优化流式算法

《Journal of Computer and System Sciences》：Streaming Algorithm for Supply Chain Inventory Optimization on the Integer Lattice

　　

•建立了多级供应链库存优化与整数格 DDRS 问题之间的新型联系。
•分别针对无约束和基数约束的 DDRS 场景提出了两种流式算法。
•通过严格的理论分析证明了所提算法具有可证明的近似保证。
•迄今为止，首次为整数格 DDRS 优化问题提供了理论保证。
引言
1921 年，奥地利数学家 Bergmann 首次提出了次模函数的定义。在此之前，组合优化领域的研究主要集中于受限线性集函数的优化。然而，学者们发现，在更多的优化场景中，元素在价值或成本方面存在依赖性，这种关系可以精确地由次模函数表示。例如，在经济领域，次模函数常被用于构建与项目成本相关的模型；在计算机科学领域，它们已成为研究机器学习、自动摘要、社交网络、用户偏好建模等应用的重要理论工具，因此具有广泛的应用价值。因此，次模函数的理论与算法研究引起了学者们的极大关注。无约束单调次模最大化问题可以在多项式时间内精确求解。然而，大多数次模最大化问题是 NP 难的。因此，国内外研究人员主要依靠设计近似算法或启发式算法来寻找此类问题的近似解。关于传统数据集上的集次模最大化问题，已取得丰富的研究成果，详见参考文献 [1]、[2]、[3]、[4]。Nemhauser 和 Wolsey [5] 表明，对于带有基数约束的单调次模函数，使用贪心算法可以达到 $(1-1/e)$-近似，时间复杂度为 $O(nk)$。1998 年，Feige [6] 证明，除非 P = NP，否则不存在优于 $(1-1/e)$-近似的算法。
随着信息技术的深度发展，在许多实际应用场景中，元素的选择需要满足多维耦合约束（如资源阈值约束、优先级排序约束、性能指标约束、鲁棒性约束等），而不再局限于 0-1 二元选择的离散决策范式。例如，在广告的最优预算分配问题 [8] 中，由于各种媒体渠道（如电视、报纸和互联网）的规模不同，其对应的成本也各不相同。此外，市场上存在竞争，我们需要根据竞争对手的决策来调整我们的分配策略。为了合理解决这一问题，我们通过允许模型中的节点多次选择，将次模函数的定义从集合扩展到整数格，并将该问题构建为整数格上的次模最大化模型，从而解决了如何选择媒体渠道及其相应分配策略的问题。其次，在监测空间现象时，传感器布设问题 [7] 是一项基本任务。鉴于不同能量级别的传感器收集的信息量和部署成本不同，项目通过将该问题建模为整数格上的次模最大化模型，来平衡信息增益与成本之间的关系。该模型不仅确定是否在每一点放置传感器，还决定放置何种类型的传感器。幸运的是，这种扩展也适用于解决文本摘要、多单元组合拍卖、社交网络影响力最大化等一系列实际问题。通过准确描绘边际收益递减的核心特征，整数格上的次模函数为这些复杂场景提供了更具实用性的数学建模框架和优化理论支持。由于实际问题的需要，次模函数的定义从集合扩展到了整数格 [9]、[10]、[11]、[12] 域。目前，关于带有多种复杂约束（如耦合约束、鲁棒约束和动态约束）的整数格次模最大化问题的高效近似算法设计，仍相对缺乏成果，特别是在工业级应用的工程转化和系统集成方面。这些不足之处使其难以满足数字经济时代大数据驱动的智能优化决策的迫切需求。传统的供应链库存优化方法主要依赖线性规划 (LP) 和凸优化框架，这些框架假设多级库存系统具有线性成本结构和恒定的边际回报。然而，实际库存管理通常表现出非线性的边际收益递减：随着库存水平的上升，补货、运输调整和库存分配的边际效益逐渐降低。这种非线性和次模特性无法被传统的基于 LP 的模型准确捕获，这往往导致复杂供应链场景下的系统描述过于简单化和库存策略次优。相比之下，本文从整数格 DR-次模的角度构建了多级库存优化问题。通过利用库存成本和效益函数的内在 DR-次模结构，所提出的流式算法自然地刻画了边际收益递减，并支持单遍在线优化，从而有效地克服了传统线性模型的局限性，为动态供应链库存调度提供了一个新颖且实用的优化框架。因此，将次模最大化问题从经典的集次模函数扩展到整数格次模函数，并开发适用于大数据场景的低复杂度、高近似比和强鲁棒性的算法，已成为国内外组合优化和运筹学领域的前沿研究方向和核心技术突破点。
然而，数据科学中的一些子集选择问题并非纯粹的次模优化问题，非次模函数是次模函数的自然扩展 [13]、[14]、[15]、[16]、[17]、[18]、[19]。根据其表征形式，非次模函数可分为参数化非次模函数和结构化非次模函数 [20]、[21]。我们可以利用这样一个事实：每个集函数都可以分解为两个次模函数之差的和 [22]、[23]。Wang 等人 [24] 考虑最大化非负归一化单调次模函数与非负线性函数之差，他们设计了一种双准则流式算法。Lu 等人 [25] 研究了两个集次模 (DS) 函数之差的最大化问题，他们设计了一种具有可证明近似保证的单遍流式算法，这是流式模型中 DS 最大化问题的首个理论保证。在本文中，我们研究整数格上两个 DR-次模函数之差 (DDRS) 的最大化问题。
小节片段
预备知识
在本节中，我们规定了一系列符号和概念定义。符号 $[k]$ 指定从 1 到 $k$ 的所有正整数集合。对于向量 $x$，与 $e_i \in E$ 关联的分量表示为 $x(e_i)$。零向量表示为 $\mathbf{0}$，而 $\chi_{e_i}$ 表示标准基向量，除第 $i$ 个分量取值为 1 外，其余所有分量均为零。对于任何子集 $X \subseteq E$，$\chi_X$ 代表 $X$ 的特征向量，$x(X)$ 定义为
算法
在本节中，我们针对前面提出的两个次模函数之差的最大化问题，设计了两种不同的组合优化算法。具体而言，第一种算法基于经典流算法构建，旨在通过简洁高效的求解框架快速生成问题的近似最优解，因此适用于对计算时效性要求严格的场景。第二种
数值实验
本节展示了我们的算法与社交网络利润最大化任务中的传统基线模型的性能对比，以验证我们提出的解决方案的优越性。
让我们考虑一个构建为 $G=(V_1;V_2,E)$ 的加权社交网络，其中 $V_1$ 代表源节点集，$V_2$ 代表目标节点集，$E$ 指的是连接这两个不相交节点集合的边集。用户 $i$ 和用户 $j$ 之间的每条边 $e_{ij}$ 反映了
结论
本文重点关注整数格上带有曲率的单调非负 DR-次模函数之差的最大化问题。它对组合近似算法进行了系统设计和理论分析，为这类 NP 难优化问题提供了高效且理论上可验证的解决方案，同时丰富了整数格环境下次模优化的算法理论体系。对于两种典型场景的
CRediT 作者贡献声明
Jingjing Tan: 撰写 – 初稿。Cuiping Ge: 撰写 – 审阅与编辑。Meixia Li: 形式分析。Meng Sun: 资源。Ruiqi Yang: 方法学。Hongyang Zhang: 数据整理。
致谢
第一作者受国家自然科学基金资助（项目编号：12301417）。第三作者受国家自然科学基金资助（项目编号：11571120）。第四作者受国家自然科学基金资助（项目编号：12101587）。
Jingjing Tan|Cuiping Ge|Meixia Li|Meng Sun|Ruiqi Yang|Hongyang Zhang