Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem
详细信息 查看全文
- 作者：Adam N. Letchforda ; A.N.Letchford@lancaster.ac.uk" class="auth_mail" title="E-mail the corresponding author ; Juan-José ; Salazar-Gonzá ; lez ; b ; jjsalaza@ull.es" class="auth_mail" title="E-mail the corresponding author
- 关键词：Sequential ordering ; Travelling salesman problem with precedence constraints ; Multi-commodity flows ; Metrics ; Polyhedral combinatorics
- 刊名：European Journal of Operational Research
- 出版年：2016
- 出版时间：16 May 2016
- 年：2016
- 卷：251
- 期：1
- 页码：74-84
- 全文大小：423 K
文摘
- •
We present several new formulations for the classical “Sequential Ordering Problem”.
- •
Two interesting families of equations are useful to strengthen the linear programming relaxations.
- •
We prove that the linear programming relaxations of the new formulations give good bounds.
- •
We analyse computational results to compare the known and new formulations.
- •
The paper also addresses the capacitated variant of the problem.