运筹学学报

Select

1. k-均值问题的差分隐私算法综述

袁藩, 徐大川, 张冬梅

运筹学学报 2022, 26 (3): 1-16. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.001

摘要（7581）

HTML （826）

PDF（pc）（993KB）（1125）

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息，同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

2. 以商圈为中心的O2O动态外卖配送路径优化模型与算法

周成昊, 吕博轩, 周翰宇, 鲁海燕

运筹学学报 2022, 26 (3): 17-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.002

摘要（7590）

HTML （526）

PDF（pc）（1042KB）（950）

针对线上到线下(Online to Offline，O2O) 外卖路径优化问题，综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件，将商圈看作配送中心，将快递员数量与快递员总行驶时间作为最小化目标，提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题，设计了一种分阶段启发式实时配送路径优化算法框架，并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上，以商圈为中心生成测试算例，对本文算法进行仿真实验，并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送，并优化其配送路径，有效减少了快递员数量与快递员总行驶时间。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

3. 一个基于张量火车分解的张量填充方法及在图像恢复中的应用

谢文蕙, 凌晨, 潘晨健

运筹学学报 2022, 26 (3): 31-43. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.003

摘要（7332）

HTML （65）

PDF（pc）（3899KB）（705）

低秩张量填充在数据恢复中有广泛应用, 基于张量火车(TT) 分解的张量填充模型在彩色图像和视频以及互联网数据恢复中应用效果良好。本文提出一个基于三阶张量TT分解的填充模型。在模型中, 引入稀疏正则项与时空正则项, 分别刻画核张量的稀疏性和数据固有的块相似性。根据问题的结构特点, 引入辅助变量将原模型等价转化成可分离形式, 并采用临近交替极小化(PAM) 与交替方向乘子法(ADMM) 相结合的方法求解模型。数值实验表明, 两正则项的引入有利于提高数据恢复的稳定性和实际效果, 所提出方法优于其他方法。在采样率较低或图像出现结构性缺失时, 其方法效果较为显著。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

4. 单位无穷范数下边权有界的最小支撑树逆最优值问题

张斌武, 关秀翠

运筹学学报 2022, 26 (3): 44-56. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.004

摘要（7129）

HTML （45）

PDF（pc）（888KB）（512）

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

5. 布德施恩运筹策怀瑾握瑜滋蕙兰——庆祝姚恩瑜教授八十华诞

运筹学学报 2022, 26 (3): 0-0.

摘要（2000）

HTML （392）

PDF（pc）（1750KB）（496）

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

6. 经典一维装箱问题近似算法的研究进展

陈婳, 张国川

运筹学学报 2022, 26 (1): 69-84. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.005

摘要（2642）

HTML （52）

PDF（pc）（946KB）（464）

自20世纪70年代开始，随着计算复杂性理论的建立，近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象，装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强，广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外，装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天，对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型，简述若干经典Fit算法的发展历程，分析基于线性规划松弛的近似方案的主要思路，总结当前的研究现状并对未来的研究提供一些参考建议。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

7. 电商生态系统四方演化博弈研究

王辛辛, 程郁琨, 田晓明, 许智琪, 陈瑾冕

运筹学学报 2022, 26 (1): 23-42. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.002

摘要（2542）

HTML （29）

PDF（pc）（1491KB）（432）

受启发于近些年频繁曝出的消费者权益保护问题，为探析消费者行为对电商生态系统中其他群体策略选择的影响，本文基于演化博弈理论，考虑消费者的投诉行为，构建由政府、电商平台、商家以及消费者组成的四方演化博弈模型；讨论各方主体的策略选择，分析策略组合稳定点，并应用MATLAB工具进行仿真模拟实验。经上述研究，本文得出结论：消费者的投诉行为有利于促进政府严格监管、电商平台严格管理、商家诚信经营。由此，建议政府和电商平台充分发挥监督管理作用，以更好地保障消费者的合法权益，并遏制消费者的恶意投诉行为，从而实现电商生态系统的稳定可持续发展。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

8. 小批量随机块坐标下降算法

胡佳, 郭田德, 韩丛英

运筹学学报 2022, 26 (1): 1-22. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.001

摘要（2431）

HTML （408）

PDF（pc）（986KB）（420）

针对机器学习中广泛存在的一类问题：结构化随机优化问题（其中“结构化”是指问题的可行域具有块状结构，且目标函数的非光滑正则化部分在变量块之间是可分离的），我们研究了小批量随机块坐标下降算法（mSBD）。按照求解非复合问题和复合问题分别给出了基本的mSBD和它的变体，对于非复合问题，分析了算法在没有一致有界梯度方差假设情况下的收敛性质。而对于复合问题，在不需要通常的Lipschitz梯度连续性假设条件下得到了算法的收敛性。最后通过数值实验验证了mSBD的有效性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

9. 求解应急医疗设施分层递进式选址问题的改进免疫算法

周宇阳, 张惠珍, 马良

运筹学学报 2021, 25 (2): 15-34. DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.002

摘要（3843）

HTML （16）

PDF（pc）（3103KB）（393）

针对应急医疗设施的特点，提出分层递进式选址方法，对应急医疗设施进行合理选址。首先，通过熵权法对选址所需要考虑的因素进行权重计算，并进行初步选址；其次，考虑设施点的服务容量、重大公共卫生事件下轻重症患者的治疗与转移的实际情况，建立双层级整数规划模型；再次，根据模型的具体特点，设计改进的免疫优化算法对其进行求解；最后，以湖北省孝感市针对突发公共卫生事件的应急医疗设施选址问题为案例进行分析，给出相应的合理选址方案，验证了模型与算法的可行性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

10. 修正PRP共轭梯度方法求解无约束最优化问题

张慧玲, 赛·闹尔再, 吴晓云

运筹学学报 2022, 26 (2): 64-72. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.006

摘要（2953）

HTML （22）

PDF（pc）（823KB）（376）

基于著名的PRP共轭梯度方法，利用CG_DESCENT共轭梯度方法的结构，本文提出了一种求解大规模无约束最优化问题的修正PRP共轭梯度方法。该方法在每一步迭代中均能够产生一个充分下降的搜索方向，且独立于任何线搜索条件。在标准Wolfe线搜索条件下，证明了修正PRP共轭梯度方法的全局收敛性和线性收敛速度。数值结果展示了修正PRP方法对给定的测试问题是非常有效的。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

11. 一种单位化的增量梯度算法

钱晓慧, 王湘美

运筹学学报 2021, 25 (2): 81-92. DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.006

摘要（3979）

HTML （9）

PDF（pc）（707KB）（360）

研究目标函数是若干光滑函数和的可分离优化问题，提出了一种单位化增量梯度算法。该算法每次子迭代只需要计算一个（或几个）分量函数的单位负梯度方向作为迭代方向。在一定条件下，证明了采用发散步长的单位化增量梯度算法的收敛性。作为应用，新算法和Bertsekas D P，Tsitsikils J N提出的（没有单位化）增量梯度算法分别用来求解稳健估计问题和源定位问题。数值例子表明，新算法优于（没有单位化）增量梯度算法。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

12. 随机二阶锥二次规划逆问题的SAA方法

王博, 初丽, 张立卫, 张宏伟

运筹学学报 2022, 26 (2): 31-44. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.003

摘要（2741）

HTML （60）

PDF（pc）（829KB）（359）

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

13. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

吕袈豪, 罗洪林, 杨泽华, 彭建文

运筹学学报 2022, 26 (2): 16-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.002

摘要（2711）

HTML （59）

PDF（pc）（895KB）（336）

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法，在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

14. 面向城市交通信号优化的多智能体强化学习综述

华贇, 王祥丰, 金博

运筹学学报 2023, 27 (2): 49-62. DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.003

摘要（1029）

HTML （7）

PDF（pc）（3398KB）（330）

随着近年来国民经济水平的快速提高, 人民的出行需求快速增长, 给当前由传统非智能信号控制主导的道路交通信号系统带来了日趋严峻的压力。交通路网复杂程度的显著提升促使交通信号控制从单点问题向系统工程问题发展, 而人工智能技术的兴起, 使得城市交通信号优化有了更多的处理手段。以多智能体强化学习为代表的群体智能方法在最近几年被广泛应用于交通信号控制与优化, 其中包括交通信号灯控制、自动驾驶、车路协同等。多智能体强化学习方法相比于传统方法, 可以赋予交通信号系统智能化的同时实现大规模交通信号系统协作, 以提升城市交通运行效率。未来智慧城市交通愿景下, 参与城市交通的各个部分互相协作是至关重要的, 多智能体强化学习在城市交通信号优化具有极大研究价值。本文将系统介绍面向城市交通信号优化的多智能体强化学习的基本理论及其应用于城市交通信号优化领域的现状, 从智能体协作的角度对已有方法进行归纳, 并分析各类方法优缺点。此外, 本文总结多智能体强化学习方法在城市交通信号优化领域所面临的挑战, 并指出该领域未来潜在研究方向, 以促进多智能体强化学习方法在智能城市交通信号优化领域的发展。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

15. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法

白富生, 冯丹, 张柯

运筹学学报 2021, 25 (2): 1-14. DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.001

摘要（3988）

HTML （17）

PDF（pc）（3166KB）（317）

针对昂贵黑箱全局优化问题，提出了可以在迭代中进行自适应采样的组合响应面方法。在响应面方法的框架下，采用三次径向基函数和薄板样条径向基函数的凸组合作为响应面。在算法的初始迭代阶段，将响应面模型和距离指示函数的幂的乘积构成的辅助函数的全局最优点作为新采样点。在接下来的迭代中，如果连续两次迭代中响应面模型的全局最优点之间的距离小于预先给定的阈值，则将当前响应面的全局最优点作为下一个采样点，否则将采用初始迭代阶段的采样策略得到新采样点。分别在7个标准测试问题上和22个标准测试问题上进行了数值实验，计算结果说明了所提算法的有效性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

16. 双层规划在城市交通领域研究与应用的系统综述

魏贺, 刘昊飞, 许丹丹, 韩雪华, 王良, 张晓东

运筹学学报 2023, 27 (2): 1-26. DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.001

摘要（1006）

HTML （42）

PDF（pc）（14197KB）（310）

双层规划是约束条件中含有优化问题，具有上下双层递阶结构的非凸优化问题，是典型的NP-Hard问题。本文系统性综述双层规划在城市交通领域的研究与应用，聚焦交通网络设计和OD(origin destination)反推调整两类问题。首先，利用文献计量法概述国内外研究主题与演变历程。其次，以开创性研究为线索溯源首次系统综述、首篇博士论文、首个TR-B专题和首篇中文综述关键研究。再次，梳理道路、公交、多模式网络设计问题与静态、动态OD反推问题的近期发展。从次，总结通用求解方法，讨论求解方法发展动向，阐述双层规划与平衡约束数学规划的关系。最后，指出未来发展的机遇与挑战：智慧交通探索揭示、建模架构模式优选和计算平台互动共享。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

17. 谱图理论中的未解决问题

刘乐乐, 宁博

运筹学学报 2023, 27 (4): 33-60. DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.003

摘要（496）

HTML （18）

PDF（pc）（779KB）（305）

谱图理论是图论中一个迷人的领域, 其利用与图相关的矩阵的特征值和特征向量来研究图的性质.本文收集了谱图理论中的若干公开问题和猜想, 按照内容的相关性将其分为20个主题.本文主要关注图的邻接矩阵中的相关问题, 并对这些问题和猜想的研究进展做了简要的梳理.

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

18. 最小化碳排放的共享单车迁移问题

苏兵, WyattCarlson, 范佳彬, GAO Arthur, 邵艳君, 林国辉

运筹学学报 2022, 26 (3): 75-91. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.006

摘要（2194）

HTML （47）

PDF（pc）（1155KB）（303）

本文考虑共享单车迁移问题, 它可看作是经典旅行售货商问题的一个新颖变形, 不同的是其目标函数为最小化碳排放。其中, 碳排放利用单车负载与其行驶路程的乘积进行刻画。我们提出了两个启发式算法：贪心和基于TSP的算法, 每个算法的核心思想均是优先减少单车负载。从理论上证明算法的可行性并给出数据实验以验证算法的实际性能。数据实验结果表明贪心算法优于基于TSP的算法, 这为共享单车企业进行日常单车分配提供了理论依据。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

19. 突发公共卫生事件中地方政府与社会公众间的演化博弈研究

许智琪, 程郁琨, 姚双良

运筹学学报 2021, 25 (4): 1-14. DOI: 10.15960/j.cnki.issn.1007-6093.2021.04.001

摘要（3047）

HTML （456）

PDF（pc）（1010KB）（298）

近年来，突发公共卫生事件频发，社会公众与地方政府相互配合是及时、高效解决突发公共卫生事件的必然选择。本文以全球抗击新冠肺炎疫情为背景，讨论在突发公共卫生事件中社会公众与地方政府之间的博弈关系，基于有限理性假设，构建演化博弈模型，分析博弈双方决策行为的动态调整过程，得到在不同条件下社会公众和地方政府的演化稳定策略。同时，利用MATLAB进行仿真实验，分析在博弈过程中政府的奖惩、上级部门的处罚等主要因素对博弈双方策略选择的影响。研究结果表明，完善相关的补贴政策，普及疫情防控的相关法律法规，加大对社会公众随意流动、违反疫情相关规章制度的惩罚力度，提高对地方政府宽松防疫的处罚等措施可以有效促进社会公众和地方政府之间的相互协作，最终实现共同积极防疫。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

20. 拍卖机制设计在区块链中的应用与挑战

陈宏崟, 程郁琨, 邓小铁, 姚章豪

运筹学学报 2023, 27 (1): 1-29. DOI: 10.15960/j.cnki.issn.1007-6093.2023.01.001

摘要（2470）

HTML （89）

PDF（pc）（1261KB）（295）

区块链是新一代信息技术的重要组成部分，是分布式网络、加密技术、智能合约等多种技术集成的新型数据库软件。过去的十多年，区块链技术在全球范围内产生广泛影响。如今的区块链技术，已从最初的关注于解决货币和支付的去中心化问题，转入到解决市场的去中心化问题。智能合约的出现使得基于区块链技术的去中心化金融进入高速发展状态，也涌现出区块链环境下的各类拍卖场景。本文首次从机制设计角度，以区块链交易费机制，非同质化代币(Non-Fungible Token，NFT)拍卖和矿工可提取价值(Miner-Extractable Value，MEV)交易位置拍卖为主要对象，总结和剖析近些年来区块链上特有的拍卖机制；并针对区块链特性，提出区块链上拍卖机制设计所面临的挑战和未来亟待解决的问题。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

全文下载排行