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.

Additional Metadata
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
Citation
Muter, I., Birbil, S.I., Bulbul, 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