TP1 - Plénière 3 / Plenary 3

Dynamic programming algorithms for shortest path problems with resource constraints (SPPRC) are frequently employed in conjunction with Lagrange relaxation algorithms and algorithms based on column generation for variants of the vehicle routing problem. In the q-route relaxation, paths are required to satisfy a capacity constraint while the elementarity constraint is relaxed, i.e., paths may contain cycles. The ng-path relaxations are defined by a family of neighborhoods, one for each vertex of the underlying network, that restrict cycling [1]. These relaxations result in sub-problems that are practically solvable, albeit difficult, given that they must be solved multiple times with different (reduced) costs. An analogous structure to q-routes for tree optimization problems is q-arbs, a structure that relaxes elementarity for arborescences [2]. We introduce ng-arb relaxations for constrained arborescences, applicable to a broad class of constrained tree-based problems. To illustrate this point, we consider the capacitated minimum spanning tree problem (CMST), which can be defined as the problem of covering a set of weighted nodes by a set of capacitated sub-trees, each rooted at a given source (a structure analogous to the well-known capacitated vehicle routing problem, where routes are replaced by rooted sub-trees). We have integrated the novel dynamic programming approach into a branch-and-price algorithm for the CMST, wherein ng-arb relaxations are solved within the column-generation process. A milestone in the field of vehicle routing was the introduction of subset-row inequalities (SRIs). SRIs strengthen the linear relaxation of the column generation master program. We demonstrate that SRIs can be integrated into the aforementioned approach for the CMST, thereby resulting in a full branch-price-and-cut (BPC) algorithm. Computational results for the standard CMST benchmark problems indicate that the resulting relaxations are often very tight, leading to small branch-and-bound search trees and reduced overall computation times in the BPC algorithm. The presented techniques have wide-ranging applications in constrained tree optimization problems, including those with time window, hop, and diameter constraints.

References:
[1] R. Baldacci, A. Mingozzi, and R. Roberti. "New route relaxation and pricing strategies for the vehicle routing problem", Operations Research, 59(5):1269–1283, 2011. doi: https://doi.org/10.1287/opre.1110.0975.

[2] E. Uchoa, R. Fukasawa, J. Lysgaard, A. Pessoa, M. P. de Arag˜ao, and D. Andrade. "Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation", Mathematical Programming, 112(2):443–472, 2006. doi: https://doi.org/10.1007/s10107-006-0043-y.

[3] M. Jepsen, , B. Petersen, S. Spoorendonk, and D. Pisinger. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows", Operations Research 56(2):497-511, 2008. doi: https://doi.org/10.1287/opre.1070.0449