运筹学学报

负载均衡问题

张国川, 陈林

2019, 23(3): 1-14. doi:10.15960/j.cnki.issn.1007-6093.2019.03.001

摘要 ( 1792 )

PDF (668KB) ( 640 )

参考文献 | 相关文章 | 多维度评价

自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来，平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣，其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉，特别是作者所在团队在相关问题的研究进展，从算法和复杂性不同的视角分析经典问题的计算本质，并对未来的研究提出一些建议.

一类多商品设施选址问题的基于线性松弛解的启发式方法

杨沐明, 黄亚魁, 戴彧虹

2019, 23(3): 15-26. doi:10.15960/j.cnki.issn.1007-6093.2019.03.002

摘要 ( 1851 )

PDF (4129KB) ( 801 )

参考文献 | 相关文章 | 多维度评价

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中，顾客的需求可能包含不止一种商品.对于大规模问题，成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式，并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解，分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.

选择性维护决策的研究进展与挑战

陈一明, 姜涛, 刘宇

2019, 23(3): 27-46. doi:10.15960/j.cnki.issn.1007-6093.2019.03.003

摘要 ( 1600 )

PDF (2853KB) ( 367 )

参考文献 | 相关文章 | 多维度评价

在工业生产和军事领域中，生产设备或技术装备往往要求连续执行多个任务，并且在任务间隔期内需要对系统中老化或失效的部件进行维护以确保完成后续任务.然而，由于受有限的成本、时间、设备及人员等维护资源的限制，在任务间隔期内难以修复系统中的所有组成部件，决策者只能有策略地选择部分部件进行维护，从而最大程度地确保完成后续任务，这类维护决策问题被称为选择性维护.现主要介绍选择性维护决策的基本模型和特点，并从系统建模、维护程度、资源约束与资源消耗、任务特性与应用环境、优化算法五个方面综述国内外关于选择性维护决策的研究进展和发展动态，并讨论其发展趋势和挑战.

无线通信系统设计中的两个优化问题和相关优化方法

刘亚锋

2019, 23(3): 47-62. doi:10.15960/j.cnki.issn.1007-6093.2019.03.004

摘要 ( 1143 )

PDF (1384KB) ( 382 )

参考文献 | 相关文章 | 多维度评价

无线通信系统设计中的许多问题可建模为优化问题.一方面，这些优化问题常常具有高度的非线性性，一般情况下难于求解；另一方面，它们又有自身的特殊结构，例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法，包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出（Multi-Input Multi-Output，MIMO）检测问题，主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.

高阶优化算法分析简介

朱喜华, 常青青, 江波

2019, 23(3): 63-76. doi:10.15960/j.cnki.issn.1007-6093.2019.03.005

摘要 ( 1210 )

PDF (638KB) ( 291 )

参考文献 | 相关文章 | 多维度评价

高阶优化算法是利用目标函数的高阶导数信息进行优化的算法，是最优化领域中的一个新兴的研究方向.高阶算法具有更低的迭代复杂度，但是需要求解一个更难的子问题.主要介绍三种高阶算法，分别为求解凸问题的高阶加速张量算法和A-HPE框架下的最优张量算法，以及求解非凸问题的ARp算法.同时也介绍了怎样求解高阶算法的子问题.希望通过对高阶算法的介绍，引起更多学者的关注与重视.

图与超图中的彩色匹配综述

李瞳, 王光辉, 周文玲

2019, 23(3): 77-90. doi:10.15960/j.cnki.issn.1007-6093.2019.03.006

摘要 ( 1047 )

PDF (732KB) ( 406 )

参考文献 | 相关文章 | 多维度评价

超图H=（V，E）是一个二元组（V，E），其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图，超图也可以看作是一般图的推广.特别地，如果超边集E中的元素均是点集V的k元子集，则称该超图为k-一致的.通常情况下，为叙述简便，我们也会将超边简称为边.图（超图）中的匹配是指图（超图）中互不相交的边的集合.对于图（超图）中的彩色匹配，有两种定义方式：一为染色图（超图）中互不相交且颜色不同的边的集合；二为顶点集均为[n]的多个染色图（超图）所构成的集族中互不相交且颜色均不同的边的集合，且每条边均来自集族中不同的图（超图）.现主要介绍了图与超图中关于彩色匹配的相关结果.

交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式

侯丽娜, 孙海琳

2019, 23(3): 91-108. doi:10.15960/j.cnki.issn.1007-6093.2019.03.007

摘要 ( 1374 )

PDF (2975KB) ( 342 )

参考文献 | 相关文章 | 多维度评价

研究集生产、运输和销售为一体的多个制造商在随机市场环境下的两阶段随机非合作博弈问题.首先，建立了该两阶段随机非合作博弈问题的模型，然后将其转化为两阶段随机变分不等式（Stochastic VariationalInequality，简称SVI）.在温和的假设条件下，证明了该问题存在均衡解，并通过Progressive Hedging Method（简称PHM）进行求解.最后，通过改变模型中随机变量的分布和成本参数，分析与研究厂商的市场行为.

最优传输理论在图像处理中的应用

马丽涛, 边伟

2019, 23(3): 109-125. doi:10.15960/j.cnki.issn.1007-6093.2019.03.008

摘要 ( 1867 )

PDF (2991KB) ( 562 )

参考文献 | 相关文章 | 多维度评价

最优传输问题是寻找概率测度间的最优传输变换的一类特殊的优化问题，近年来在众多领域得到了广泛的关注.针对传统最优传输问题存在的计算量过大、正则性缺失等问题，学者们提出了多种改进的最优传输模型和算法，用于处理实际中的各种问题.简述最优传输问题的基本理论和方法，介绍Wasserstein距离的概念及其衍生出的Wasserstein重心，探讨离散化最优传输模型及其在正则化等方面的改进，讨论求解最优传输问题的算法进展，综述Wasserstein距离在图像处理领域的简单应用，并展望有待进一步研究的工作.

在线时间序列搜索的风险补偿模型

张文明, 程永席, 茹少峰

2019, 23(3): 126-134. doi:10.15960/j.cnki.issn.1007-6093.2019.03.009

摘要 ( 1116 )

PDF (3268KB) ( 169 )

参考文献 | 相关文章 | 多维度评价

对于在线时间序列搜索问题，在假设对未来信息有一定的预期下，提出了在线时间序列搜索的风险补偿模型，进一步研究了模型的求解，给出了模型的一个最优策略，并通过数值计算讨论了最优策略的补偿函数随参数变化规律.数值实验结果表明，随着风险容忍度的增大与预期区间下限的增大，补偿函数均增大且趋于收敛；随着预期概率的增大与预期区间上限的减少，补偿函数分别增大.研究结果丰富了在线时间序列搜索的理论且具有实际应用价值.

多块交替方向乘子法不收敛反例的几点注记

陈彩华

2019, 23(3): 135-140. doi:10.15960/j.cnki.issn.1007-6093.2019.03.010

摘要 ( 1378 )

PDF (469KB) ( 356 )

参考文献 | 相关文章 | 多维度评价

近年来，多块交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中，然而它的收敛性一直是一个悬而未决的公开问题；直至2016年，陈彩华等人给出了一个三维线性方程组构成的反例说明多块交替方向乘子法是可能发散的.结合陈等人的结果，现讨论了与此相关的三个问题：1）反例之所以发散是否由于初始点选择不够好?2）反例的发散是否因为它的可行域是单点集?3）是否能够在对偶变量更新中引入某一与问题无关的步长γ∈（0，1]使得小步长的交替方向乘子法变形收敛?从理论上对前两个问题给出了否定的回答，证明当初始点随机选取时，存在可行域不是单点集的例子，使得多块交替方向乘子法求解该问题时以概率1发散；从数值上否定了第三个问题，说明即使步长γ=10^-8，多块交替方向乘子法也可能发散.

当期目录