×

On the complexity of the separation problem for rounded capacity inequalities. (English) Zbl 1387.90278

Summary: In this paper, we are interested in the separation problem for the so-called rounded capacity inequalities which are valid for the CVRP (Capacitated Vehicle Routing Problem) polytope. Rounded capacity inequalities, as well as the associated separation problem, are of particular interest for solving the CVRP, especially when dealing with the two-index formulation of the CVRP and Branch-and-Cut algorithms based on this formulation. To the best of our knowledge, it is not known in the literature whether this separation problem is NP-hard or polynomial (see for instance [P. Augerat et al., Eur. J. Oper. Res. 106, No. 2–3, 546–557 (1998; Zbl 0991.90028)] and [A. N. Letchford and J.-J. Salazar-González, ibid. 244, No. 3, 730–738 (2015; Zbl 1346.90615)]), and it has been conjectured that the problem is NP-hard. In this paper, we prove this conjecture. We also show that the separation problem for rounded capacity inequalities is strongly NP-hard when the considered solution belongs to a particular relaxation of the problem and the clients have all the same demand.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research

Software:

VRP; CVRPSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baldacci, R.; Mingozzi, A.; Roberti, R., Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, European J. Oper. Res., 218, 1-6 (2012) · Zbl 1244.90001
[2] Cordeau, J.-F.; Laporte, G.; Savelsbergh, M. W.P.; Vigo, D., Vehicle routing, (Handbooks on Operations Research and Management Science, Vol. 14 (2007))
[3] Letchford, A.; Salazar, J.-J., Stronger multi-commodity flow formulations of the capacitated vehicle routing problem, European J. Oper. Res., 244, 730-738 (2015) · Zbl 1346.90615
[4] Toth, P.; Vigo, D., The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, vol. 9 (2002) · Zbl 0979.00026
[5] Toth, P.; Vigo, D., (The Vehicle Routing: Problems, Methods, and Applications. The Vehicle Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization (2014)) · Zbl 1305.90012
[6] Cornuejols, G.; Harche, F., Polyhedral study of the capacitated vehicle routing problem, Math. Program., 60, 1, 21-52 (1993) · Zbl 0790.90029
[7] Lysgaard, J.; Letchford, A.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math. Program. Ser. A, 100, 423-445 (2004) · Zbl 1073.90068
[8] Ralphs, T. K.; Kopman, L.; Pulleyblank, W. R.; Trotter, L. E., On the capacitated vehicle routing problem, Math. Program., 94, 2-3, 343-359 (2003) · Zbl 1030.90131
[9] Wolsey, L. A., (Integer Programming. Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization (1998))
[10] Augerat, P.; Belenguer, J. M.; Benavent, E.; Corberán, A.; Naddef, D., Separating capacity constraints for the CVRP using tabu search, European J. Oper. Res., 106, 546-557 (1998) · Zbl 0991.90028
[11] Thomas McCormick, S.; Rao, M. R.; Rinaldi, Giovanni, Easy and difficult objective functions for max cut, Math. Program. B, 94, 459-466 (2003) · Zbl 1030.90130
[13] Diarrassouba, I., The separation problem of rounded capacity inequalities: some polynomial cases, Discrete Optim. (2016), in press · Zbl 1387.90261
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[15] Barahona and, F.; Conforti, M., A construction for binary matroids, Discrete Math., 66, 213-218 (1987) · Zbl 0644.05017
[16] Padberg, M. W.; Rao, M. R., Odd minimum cut-sets and b-matchings, Math. Oper. Res., 7, 67-80 (1982) · Zbl 0499.90056
[17] Diarrassouba, I.; Kutucu, H.; Mahjoub, A. R., Two node-disjoint hop-constrained survivable network design and polyhedra, Networks, 67, 4, 316-337 (2016) · Zbl 1390.90156
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.