运筹学学报

Select

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

袁藩, 徐大川, 张冬梅

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

摘要（7565）

HTML （825）

PDF（pc）（993KB）（1108）

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

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

Select

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

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

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

摘要（7577）

HTML （525）

PDF（pc）（1042KB）（933）

针对线上到线下(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

摘要（7325）

HTML （65）

PDF（pc）（3899KB）（700）

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

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

Select

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

张斌武, 关秀翠

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

摘要（7123）

HTML （45）

PDF（pc）（888KB）（508）

研究了单位$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): 57-74. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.005

摘要（2156）

HTML （296）

PDF（pc）（902KB）（178）

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。

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

Select

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

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

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

摘要（2191）

HTML （47）

PDF（pc）（1155KB）（298）

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

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

Select

7. 两台同类机排序问题SPT算法的最坏情况比

龚铭炀, 谈之奕, 严羽洁

运筹学学报 2022, 26 (3): 92-108. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.007

摘要（2103）

HTML （13）

PDF（pc）（821KB）（177）

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。

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

Select

8. 两台自私型机器上自私工件排序的PoA紧界

成夏炎, 何滢, 赵聪聪, 李荣珩

运筹学学报 2022, 26 (3): 109-119. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.008

摘要（2007）

HTML （13）

PDF（pc）（783KB）（97）

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。

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

Select

9. 新产品供应链下考虑顾客体验效应的制造商渠道返利策略研究

徐春明, 吴晨晨, 原白云

运筹学学报 2022, 26 (3): 120-132. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.009

摘要（2168）

HTML （22）

PDF（pc）（2172KB）（233）

随着体验经济的到来和新产品市场的竞争, 如何针对顾客体验进行渠道建设和品牌推广就显得尤为重要。本文针对新产品供应链的环境, 考虑顾客的体验效应及零售商对此所做的体验投入, 利用效用理论构建了线上和线下消费者的需求函数, 在此基础上分别探讨了批发价格模式和渠道返利模式制造商占优的供应链的决策行为, 分析了供应链各决策主体均衡解的特征, 并对渠道返利前后供应链节点企业的最优决策进行了比较, 最后用数值例子分析了制造商的返利点、零售商的体验投入水平、顾客的体验效应、旅行成本以及购买意愿等对供应链最优绩效的影响。

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

Select

10. 工件具有任意尺寸的混合分批平行机排序问题的近似算法

王冬, 李刚刚, 罗文昌

运筹学学报 2022, 26 (3): 133-142. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.010

摘要（2061）

HTML （18）

PDF（pc）（840KB）（221）

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。

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

Select

11. 一类一维在线单位聚类问题的随机近似算法

代宇波, 段懿红, 刘龙城, 王子豪

运筹学学报 2022, 26 (3): 143-150. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.011

摘要（2037）

HTML （10）

PDF（pc）（766KB）（113）

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。

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

Select

12. 极大化提前完工总量平行机排序问题的LPT算法

周萍, 季敏, 蒋义伟

运筹学学报 2022, 26 (3): 151-156. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.012

摘要（2115）

HTML （14）

PDF（pc）（744KB）（182）

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。

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

Select

13. 多示例学习问题研究进展综述

田英杰, 胥栋宽, 张春华

运筹学学报 2018, 22 (2): 1-17.

摘要（9710）

PDF（pc）（9313KB）（899）

多示例学习是一种特殊的机器学习问题，近年来得到了广泛的关注和研究，许多不同类型的多示例学习算法被提出，用以处理各个领域中的实际问题. 针对多示例学习的算法研究和应用进行了较为详细的综述, 介绍了多示例学习的各种背景假设, 从基于示例水平、包水平、嵌入空间三个方面对多示例学习的常见算法进行了描述, 并给出了多示例学习的算法拓展和若干领域的主要应用.

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

Select

14. 解一类结构变分不等式问题的非精确并行交替方向法

冯俊锴, 张海斌, 秦嫒, 张凯丽

运筹学学报 2018, 22 (2): 18-30. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.002

摘要（1511）

PDF（pc）（585KB）（227）

带线性约束的具有两分块结构的单调变分不等式问题, 出现在许多现代应用中, 如交通和经济问题等. 基于该问题良好的可分结构, 分裂型算法被广泛研究用于其求解. 提出新的带回代的非精确并行交替方向法解该类问题, 在每一步迭代中，首先以并行模式通过投影得到预测点, 然后对其校正得到下一步的迭代点. 在压缩型算法的理论框架下, 在适当条件下证明了所提算法的全局收敛性. 数值结果表明了算法的有效性. 此外, 该算法可推广到求解具有多分块结构的问题.

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

Select

15. k-均值算法的初始化方法综述

徐大川, 许宜诚, 张冬梅

运筹学学报 2018, 22 (2): 31-40. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.003

摘要（1217）

PDF（pc）（583KB）（244）

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注, 是经典的NP-难问题之一. 给定N个d维实向量构成的观测集, 目标是把这N个观测点划分到k(\leq N)个集合中, 使得所有集合中的点到对应的聚类中心距离的平方和最小, 一个集合的聚类中心指的是该集合中所有观测点的均值. k-均值算法作为解决k-均值问题的启发式算法，在实际应用中因其出色的收敛速度而倍受欢迎. k-均值算法可描述为: 给定问题的初始化分组, 交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解. 该算法通常被认为几乎是线性收敛的. 但缺点也很明显, 无法保证得到的是全局最优解, 并且算法结果好坏过于依赖初始解的选取. 于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量. 现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.

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

Select

16. 两个基于不同张量乘法的四阶张量分解

徐娇娇, 杨志霞

运筹学学报 2018, 22 (2): 41-54. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.004

摘要（1154）

PDF（pc）（651KB）（245）

提出了两个基于不同张量乘法的四阶张量分解. 首先, 在矩阵乘法的基础上, 定义第一种四阶张量乘法(F-乘), 基于F-乘提出了第一种四阶张量分解(F-TD). 其次, 基于三阶张量t-product给出了第二种四阶张量乘法(B-乘)和分解(FT-SVD). 同时, 利用两种分解方法, 分别给出两个张量逼近定理. 最后, 三个数值算例阐明提出的两种分解方法的准确性和可行性.

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

Select

17. 从支持向量机到非平行支持向量机

邵元海, 杨凯丽, 刘明增, 等

运筹学学报 2018, 22 (2): 55-65. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.005

摘要（9505）

PDF（pc）（1352KB）（573）

非平行支持向量机是支持向量机的延伸, 受到了广泛的关注. 非平行支持向量机构造允许非平行的支撑超平面, 可以描述不同类别之间的数据分布差异, 从而适用于更广泛的问题. 然而, 对非平行支持向量机模型与支持向量机模型之间的关系研究较少, 且尚未有等价于标准支持向量机模型的非平行支持向量机模型. 从支持向量机出发, 构造出新的非平行支持向量机模型, 该模型不仅可以退化为标准支持向量机, 保留了支持向量机的稀疏性和核函数可扩展性. 同时, 可以描述不同类别之间的数据分布差异, 适用于更广泛的非平行结构数据等. 最后, 通过实验初步验证了所提模型的有效性.

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

Select

18. 半监督距离度量学习内蕴加速投影梯度算法

仰迪, 白延琴, 李倩

运筹学学报 2018, 22 (2): 66-78. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.006

摘要（1089）

PDF（pc）（5001KB）（173）

考虑求解一类半监督距离度量学习问题. 由于样本集(数据库)的规模与复杂性的激增, 在考虑距离度量学习问题时, 必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius 范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.

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

Select

19. 线性约束两分块非凸优化的ADMM-SQP算法

简金宝, 劳译娴, 晁绵涛, 马国栋

运筹学学报 2018, 22 (2): 79-92. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.007

摘要（9806）

PDF（pc）（647KB）（673）

基于乘子交替方向法(ADMM)和序列二次规划(SQP)方法思想, 致力于研究线性约束两分块非凸优化的新型高效算法. 首先, 以SQP思想为主线, 在其二次规划(QP)子问题的求解中引入ADMM思想, 将QP分解为两个相互独立的小规模QP求解. 其次, 借助增广拉格朗日函数和Armijo线搜索产生原始变量新迭代点. 最后, 以显式解析式更新对偶变量. 因此, 构建了一个新型ADMM-SQP算法. 在较弱条件下, 分析了算法通常意义下的全局收敛性, 并对算法进行了初步的数值试验.

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

Select

20. 设施选址博弈问题的无支付机制设计研究

程郁琨, 梅丽丽

运筹学学报 2018, 22 (2): 93-104. DOI: 10.15960/j.cnki.issn.1007-6093.2018.02.008

摘要（1187）

PDF（pc）（560KB）（246）

选址博弈是目前国际相关学术领域的重要前沿课题之一. 在选址博弈问题中, 存在n个相互影响的``理性"居民, 他们的住址等信息是其私有信息；设计者需要设计选址机制, 以居民汇报的住址信息为输入, 输出设施位置. 在进行机制设计的过程中, 如何在没有金钱的刺激下, 保证所有居民``说真话", 设计出防策略性无支付机制是其中的重要研究内容. 设施选址博弈问题的无支付机制设计是组合优化和理论计算机科学的交叉学科课题, 在管理科学、信息科学以及社会经济学等领域有着重要的应用, 具有重要的理论意义和实际的应用价值. 现根据不同设施类型及个数、不同个人偏好、不同度量空间以及不同社会总体目标等条件, 介绍各种类型的设施选址博弈模型, 罗列相关的研究成果, 并总结其中尚待解决的问题.

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

推荐文章