Solving the Lagrangian dual problem for some traffic coordination problems through linear programming
Solving the Lagrangian dual problem for some traffic coordination problems through linear programming
复制标题
DOI：
10.1109/cdc.2017.8264513
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
G. Daugherty;S. Reveliotis;G. Mohler
中科院分区：
文献类型：
--
作者：
G. Daugherty;S. Reveliotis;G. Mohler
在最近的一系列出版物中，我们已经解决了一类交通协调问题，可以制定为组合调度问题，我们已经开发了一个拉格朗日对偶方法获得（i）强下界相应的最优解，和（ii）潜在的“种子”的建设可行的，接近最优的解决方案，这些问题。在这些过去的作品中，相应的“对偶”问题通过定制的双上升算法来解决，该算法利用底层“对偶”函数的次微分的分布式表示，以便在优化过程中有效地计算上升方向。在本文中，我们表明，导致上述过去发展的基本见解也可以为所考虑的“对偶”问题提供有效的线性规划公式。
In a series of recent publications, we have addressed a class of traffic coordination problems that can be formulated as combinatorial scheduling problems, and we have developed a Lagrangian duality approach for obtaining (i) strong lower bounds for the corresponding optimal solution, and (ii) potential “seeds” for the construction of feasible, near-optimal solutions to these problems. In those past works, the corresponding “dual” problem was solved through a customized dual-ascent algorithm that took advantage of a distributed representation of the sub-differentials of the underlying “dual” function in order to compute efficiently ascending directions during the optimization process. In this paper we show that the fundamental insights that led to the aforementioned past developments, can also enable an efficient linear programming formulation for the considered “dual” problem.1