A note on “A LP-based heuristic for a time-constrained routing problem”
In their paper, Avella et al. (2006) investigate a time-constrained routing problem. The core of the proposed solution approach is a large-scale linear program that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this linear program optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate by using Lagrangian duality that this optimality condition is incorrect and may lead to a suboptimal solution at termination.
Highlights ► We identify a critical flaw in a column-and-row generation method in a recent paper in EJOR. ► A correction based on Lagrangian duality is proposed. ► The flaw and its correction are illustrated on an example.
|Keywords||Large-scale optimizationColumn generationColumn-and-row generationTime-constrained routing|
|Persistent URL||dx.doi.org/10.1016/j.ejor.2012.03.048, hdl.handle.net/1765/118007|
|Journal||European Journal of Operational Research|
Muter, I, Birbil, S.I, Bülbül, K, & Sahin, G. (2012). A note on “A LP-based heuristic for a time-constrained routing problem”. European Journal of Operational Research, 221(2), 306–307. doi:10.1016/j.ejor.2012.03.048