dc.creatorPereira, Dilson Lucas
dc.creatorCunha, Alexandre Salles da
dc.date2019-03-29T12:24:41Z
dc.date2019-03-29T12:24:41Z
dc.date2018-10
dc.date.accessioned2023-09-28T20:08:10Z
dc.date.available2023-09-28T20:08:10Z
dc.identifierPEREIRA, D. L.; CUNHA, A. S. da. Reformulations and branch-and-price algorithm for the Minimum Cost Hop-and-root Constrained Forest Problem. Computers & Operations Research, New York, v. 98, p. 38-55, Oct. 2018.
dc.identifierhttp://repositorio.ufla.br/jspui/handle/1/56621321
dc.identifierhttps://www.sciencedirect.com/science/article/pii/S0305054818301369#!
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/9045312
dc.descriptionThe Minimum Cost Hop-and-root Constrained Forest Problem (MCHCFP) is a combinatorial optimization problem that arises in the design of energy efficient wireless sensor networks with mobile sinks. It aims at providing a communication topology that minimizes energy consumption while controlling network latency and message loss due to communication failure. The problem is defined in terms of a mixed graph with set of vertices V (representing the sensor nodes), edges E, arcs A, and parameters and . Each edge has an associated length, and each arc has an associated cost. The MCHCFP aims at finding a rooted spanning forest of (V, A) with minimum total cost. The solution must be hop constrained, in the sense that the path from any leaf to its root in the forest does not have more than H arcs, as well as distance constrained, so that one must be able to find K routes of length at most D, visiting exactly once the chosen roots of the forest. We study four integer programming formulations, two of them are new, the other two come from the literature. The first formulation coming from the literature is a multicommodity flow based model. The second is a Dantzig–Wolfe reformulation of the first. The two new formulations, which are equivalent with respect to their linear programming bounds, arise when the problem is formulated over a layered graph. To evaluate the bounds implied by the formulations other than the network flow model, we develop algorithms based on delayed column and/or row generation. We provide computational experiments showing that the best lower bounds are given by the formulations based on the layered graph. The reformulation coming from the literature provides lower bounds that are very close to those provided by the layered graph formulations, but in significantly less computational time. As it provides the best trade-off between lower bound quality and computational effort, that reformulation is thus chosen as the basis for a branch-and-price algorithm introduced here. Such an algorithm managed to solve instances with up to 60 vertices, a significant improvement over the previous approach in the literature, which systematically solves instances with up to 20 vertices.
dc.languageen_US
dc.publisherElsevier
dc.rightsrestrictAccess
dc.sourceComputers & Operations Research
dc.subjectRow and column generation
dc.subjectWireless sensor networks
dc.subjectVehicle routing
dc.subjectParallel heuristics
dc.subjectGeração de linha e coluna
dc.subjectRedes de sensores sem fio
dc.subjectRoteamento de veículos
dc.subjectHeurística paralela
dc.titleReformulations and branch-and-price algorithm for the Minimum Cost Hop-and-root Constrained Forest Problem
dc.typeArtigo


Este ítem pertenece a la siguiente institución