An active set algorithm for robust combinatorial optimization based on separation oracles

Abstract:
We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the Lagrangian dual of the continuous relaxation, where the feasible set of the combinatorial problem is supposed to be given by a separation oracle. The method benefits from the closed form solution of the active set subproblems and from a smart update of pseudo-inverse matrices. We present numerical experiments on randomly generated instances and on instances from different combinatorial problems, including the shortest path and the traveling salesman problem, showing that our new algorithm consistently outperforms the state-of-the art mixed-integer SOCP solver of Gurobi.
Author Listing: Christoph Buchheim;Marianna De Santis
Volume: None
Pages: 1-35
DOI: 10.1007/s12532-019-00160-8
Language: English
Journal: Mathematical Programming Computation

Mathematical Programming Computation

MATH PROGRAM COMPUT

影响因子:4.3 是否综述期刊:否 是否OA:否 是否预警:不在预警名单内 发行时间:- ISSN:1867-2949 发刊频率:4 issues per year 收录数据库:SCIE/Scopus收录 出版国家/地区:- 出版社:Springer Nature

期刊介绍

Mathematical Programming Computation (MPC) publishes original research articles advancing the state of the art of practical computation in Mathematical Optimization and closely related fields. Authors are required to submit software source code and data along with their manuscripts (while open-source software is encouraged, it is not required). Where applicable, the review process will aim for verification of reported computational results. Topics of articles include: New algorithmic techniques, with substantial computational testing New applications, with substantial computational testing Innovative software Comparative tests of algorithms Modeling environments Libraries of problem instances Software frameworks or libraries.Among the specific topics covered in MPC are linear programming, convex optimization, nonlinear optimization, stochastic optimization, integer programming, combinatorial optimization, global optimization, network algorithms, and modeling languages.MPC accepts manuscript submission from its own editorial board members in cases in which the identities of the associate editor, reviewers, and technical editor handling the manuscript can remain fully confidential. To be accepted, manuscripts submitted by editorial board members must meet the same quality standards as all other accepted submissions; there is absolutely no special preference or consideration given to such submissions.

数学规划计算(MPC)发表原创研究文章,推进数学优化和密切相关领域的实际计算的技术水平。作者必须提交软件源代码和数据沿着他们的手稿(虽然鼓励使用开源软件,但并不要求)。在适用情况下,审查过程旨在验证报告的计算结果。文章的主题包括:新的算法技术,大量的计算测试新的应用程序,大量的计算测试创新软件算法的比较测试建模环境问题实例库软件框架或库。MPC涵盖的具体主题包括线性规划,凸优化,非线性优化,随机优化,整数规划,组合优化,全局优化,网络算法,和建模语言。MPC接受自己的编辑委员会成员提交的稿件,前提是处理稿件的副编辑、审稿人和技术编辑的身份可以完全保密。编辑委员会成员提交的稿件必须达到与所有其他被接受稿件相同的质量标准,才能被接受;这些意见书绝对不会获得特别优待或考虑。

年发文量 19
国人发稿量 -
国人发文占比 0%
自引率 4.7%
平均录取率 -
平均审稿周期 -
版面费 US$2890
偏重研究方向 OPERATIONS RESEARCH & MANAGEMENT SCIENCE-
期刊官网 https://www.springer.com/12532/?utm_medium=display&utm_source=letpub&utm_content=text_link&utm_term=null&utm_campaign=MPSR_12532_AWA1_CN_CNPL_letpb_mp
投稿链接 https://mpc.msubmit.net/cgi-bin/main.plex

质量指标占比

研究类文章占比 OA被引用占比 撤稿占比 出版后修正文章占比
100.00% 50.00% - -

相关指数

{{ relationActiveLabel }}
{{ item.label }}

期刊预警不是论文评价,更不是否定预警期刊发表的每项成果。《国际期刊预警名单(试行)》旨在提醒科研人员审慎选择成果发表平台、提示出版机构强化期刊质量管理。

预警期刊的识别采用定性与定量相结合的方法。通过专家咨询确立分析维度及评价指标,而后基于指标客观数据产生具体名单。

具体而言,就是通过综合评判期刊载文量、作者国际化程度、拒稿率、论文处理费(APC)、期刊超越指数、自引率、撤稿信息等,找出那些具备风险特征、具有潜在质量问题的学术期刊。最后,依据各刊数据差异,将预警级别分为高、中、低三档,风险指数依次减弱。

《国际期刊预警名单(试行)》确定原则是客观、审慎、开放。期刊分区表团队期待与科研界、学术出版机构一起,夯实科学精神,打造气正风清的学术诚信环境!真诚欢迎各界就预警名单的分析维度、使用方案、值得关切的期刊等提出建议!

预警情况 查看说明

时间 预警情况
2024年02月发布的2024版 不在预警名单中
2023年01月发布的2023版 不在预警名单中
2021年12月发布的2021版 不在预警名单中
2020年12月发布的2020版 不在预警名单中

JCR分区 WOS分区等级:Q1区

版本 按学科 分区
WOS期刊SCI分区
WOS期刊SCI分区是指SCI官方(Web of Science)为每个学科内的期刊按照IF数值排 序,将期刊按照四等分的方法划分的Q1-Q4等级,Q1代表质量最高,即常说的1区期刊。
(2021-2022年最新版)
MATHEMATICS, APPLIED Q1
COMPUTER SCIENCE, SOFTWARE ENGINEERING Q1
OPERATIONS RESEARCH & MANAGEMENT SCIENCE Q1

关于2019年中科院分区升级版(试行)

分区表升级版(试行)旨在解决期刊学科体系划分与学科发展以及融合趋势的不相容问题。由于学科交叉在当代科研活动的趋势愈发显著,学科体系构建容易引发争议。为了打破学科体系给期刊评价带来的桎梏,“升级版方案”首先构建了论文层级的主题体系,然后分别计算每篇论文在所属主题的影响力,最后汇总各期刊每篇论文分值,得到“期刊超越指数”,作为分区依据。

分区表升级版(试行)的优势:一是论文层级的主题体系既能体现学科交叉特点,又可以精准揭示期刊载文的多学科性;二是采用“期刊超越指数”替代影响因子指标,解决了影响因子数学性质缺陷对评价结果的干扰。整体而言,分区表升级版(试行)突破了期刊评价中学科体系构建、评价指标选择等瓶颈问题,能够更为全面地揭示学术期刊的影响力,为科研评价“去四唯”提供解决思路。相关研究成果经过国际同行的认可,已经发表在科学计量学领域国际重要期刊。

《2019年中国科学院文献情报中心期刊分区表升级版(试行)》首次将社会科学引文数据库(SSCI)期刊纳入到分区评估中。升级版分区表(试行)设置了包括自然科学和社会科学在内的18个大类学科。基础版和升级版(试行)将过渡共存三年时间,推测在此期间各大高校和科研院所仍可能会以基础版为考核参考标准。 提示:中科院分区官方微信公众号“fenqubiao”仅提供基础版数据查询,暂无升级版数据,请注意区分。

中科院分区 查看说明

版本 大类学科 小类学科 Top期刊 综述期刊
数学
2区
MATHEMATICS, APPLIED
应用数学
2区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机:软件工程
2区
OPERATIONS RESEARCH & MANAGEMENT SCIENCE
运筹学与管理科学
3区
2022年12月
最新升级版
数学
1区
MATHEMATICS, APPLIED
应用数学
1区
COMPUTER SCIENCE, SOFTWARE ENGINEERING
计算机:软件工程
1区
OPERATIONS RESEARCH & MANAGEMENT SCIENCE
运筹学与管理科学
2区