Layered graph approaches for combinatorial optimization problems
Layered graph approaches for combinatorial optimization problems
复制标题
DOI：
10.1016/j.cor.2018.09.007
复制
发表时间：
2019-02-01
影响因子：
4.6
通讯作者：
Ruthmair, Mario
中科院分区：
文献类型：
--
作者：
Gouveia, Luis;Leitner, Markus;Ruthmair, Mario
扩展了时空网络的概念，分层图将关于一个或多个资源状态值的信息与节点和弧相关联。虽然基于它们的整数规划公式允许相对容易地对复杂问题进行建模，但它们的大小使得它们对于非平凡的实例很难求解。我们详细介绍并分类了(最近)科学文献和回顾方法中使用的分层图建模技术，以成功解决由此产生的大规模、扩展公式。给出了用分解方法求解分层图公式的建模指导原则和重要观察结果，以及未来的几个研究方向。(C)2018爱思唯尔有限公司。保留所有权利。
Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that have been used in the (recent) scientific literature and review methods to successfully solve the resulting large-scale, extended formulations. Modeling guidelines and important observations concerning the solution of layered graph formulations by decomposition methods are given together with several future research directions. (C) 2018 Elsevier Ltd. All rights reserved.