Discrete Optimization
Heuristic and exact algorithms for minimum-weight non-spanning arborescences

https://doi.org/10.1016/j.ejor.2020.03.073Get rights and content

Highlights

  • New algorithms for finding minimum-weight rooted non-spanning arborescences.

  • Combinatorial and LP-based problem reduction rules.

  • A fast iterated local search heuristic using a modified Edmonds algorithm.

  • An exact branch-and-cut solver based on a cutset-based formulation.

  • An experimental study showing that existing instances can be solved exactly very fast.

Abstract

We address the problem of finding an arborescence of minimum total edge weight rooted at a given vertex in a directed, edge-weighted graph. If the arborescence must span all vertices the problem is solvable in polynomial time, but the non-spanning version is NP-hard. We propose reduction rules which determine vertices that are required or can be excluded from optimal solutions, a modification of Edmonds algorithm to construct arborescences that span a given set of selected vertices, and embed this procedure into an iterated local search for good vertex selections. Moreover, we propose a cutset-based integer linear programming formulation, provide different linear relaxations to reduce the number of variables in the model and solve the reduced model using a branch-and-cut approach. We give extensive computational results showing that both the heuristic and the exact methods are effective and obtain better solutions on instances from the literature than existing approaches, often in much less time.

Introduction

Let G=(V,A) be a directed graph with weights wa on arcs a ∈ A  and a set RV of required vertices (or terminals). A branching of G is a subset of arcs BA which contains no undirected cycle and such that every vertex has at most one entering arc; the vertices with no entering arc are its roots. A weakly connected branching is called an arborescence and has a single root. The minimum covering arborecence (MCA) problem is to find a subgraph G*=(V*,A*) of G such that A* is an arborescence of minimum total weight (or cost) w(A*)=aA*wa rooted at a given vertex r ∈ V such that RV*. The special case where R= is called the minimum-weight rooted arborescence (MWRA) problem. Both problems are strongly NP-hard (Venkata Rao & Mc Ginnis, 1984).

The MCA and MWRA problems generalize several other well-known problems and has direct applications. If we require the arborescence to be spanning, i.e.  R=V, then the problem is known as the Optimum Branching or Min-Sum Arborescence Problem and can be solved in polynomial time by the algorithms of Chu and Liu (1965), Edmonds (1967), and Bock (1971). Tarjan (1977) and Fischetti and Toth (1993) give efficient implementations that take time O(n2). Tarjan (1977) also gives an implementation that runs in time O(mlog n) which is better suited for sparse graphs.

Among the problems that may be reduced to the MWRA are the uncapacitated facility location (UFL) and the directed Steiner tree problems. In the UFL we need to assign a set of customers J to a set of facilities I, where each facility i ∈ I has an opening cost fi and assigning customer j ∈ J to facility i ∈ I costs cij ≥ 0. The problem can be reduced to the MWRA as follows. Introduce an artificial root r, arcs (r, i) for i ∈ I of weight fi, arcs (i, j) of weight cij for i ∈ I and j ∈ J, and artificial leafs lj with arcs (j, lj) of weight Mj ≤ 0 for j ∈ J. Negative weights Mj have to guarantee that all clients are included in an optimal solution of the MWRA. To achieve this, we can set Mj=fμjcμj,j1 where μj=argminiI{fi+cij} is the cheapest facility to attend customer j ∈ J alone.

In a similar way the MCA can be reduced to the MWRA. For each required vertex v ∈ R add a new vertex v′ and an arc (v, v′) of weight Mv ≤ 0. If we set, e.g., Mv=drv1 where drv is the distance of some path from the root to vertex v, then all required vertices will be part of an optimal solution. The MCA is a generalization of the Steiner arborescence problem (SAP), or the directed Steiner tree problem, which allows only non-negative arc weights.

Besides reductions of other problems, these problems have direct applications. Mateo, Blum, Fua, and Türetgen (2012) study the problem in the context of the reconstruction of tree structures from images, which has applications in medicine and neurology, while Venkata Rao and Mc Ginnis (1984) introduced a variant of the MWRA which occurs as a subproblem in a decomposition approach for a multi-stage lot sizing problem. It also occurs as a subproblem in solution approaches to other problems, e.g., in territory design (Mehrotra, Johnson, & Nemhauser, 1998), the asymmetric traveling salesman, or in k-cardinality minimum trees (Duhamel, Gouveia, & Moura, 2008).

The MWRA has been introduced by Venkata Rao and Mc Ginnis (1984) on directed acyclic vertex-weighted graphs. The authors show that the problem is NP-hard by reducing the NP-hard uncapacitated facility location problem to it, and introduce a greedy constructive heuristic and a branch-and-bound algorithm for solving it. The vertex weighted variant is easily seen to be a special case of the MWRA as defined here by noting that the weights on the vertices can be pushed to incoming arcs, since each vertex has at most one incoming arc in any solution. The arc-weighted case on directed acyclic graphs has been introduced by Venkata Rao and Sridharan (1992) with the additional restriction that the root has a single outgoing arc. This case has been studied further by Venkata Rao and Sridharan (2002), who introduce a mathematical model, Lagrangian relaxations, and two heuristic solution methods. The first heuristic is constructive and grows an arborescence repeatedly adding shortest paths to the root of the tree, and setting the corresponding arc weights to 0 for as long as the total weight of the tree decreases. The second is guided by the Lagrangian relaxation of the connectivity constraints, and applies the first heuristic in each iteration of the subgradient solver, with arcs of the relaxed solution fixed to be part of the solution.

Mateo et al. (2012) study the MWRA on directed acyclic graphs and propose an ant colony optimization (ACO) heuristic to solve it. The main idea is to construct a spanning arborescence by greedily selecting the cheapest outgoing arc from the currently spanned vertex set, starting from the root, and afterwards finding the optimal non-spanning subtree of the said tree by dynamic programming. This idea is applied directly to obtain a constructive heuristic as well as in the ACO heuristic, which evolves the arc preferences used during the construction.

Duhamel et al. (2008) introduce an unrooted variant of the MWRA on general graphs, and reduce it to the rooted version where the root is restricted to have out-degree 1. Note that this variant can be reduced to the MCA by introducing a root which is connected to all vertices by an arc of weight M, and a required vertex to which all vertices connect with weight 0, where M is a sufficiently large constant such that an optimal solution contains at most one outgoing arc from the root (e.g. M > ∑a ∈ Awa). As a consequence, this variant can also be reduced to the MWRA by reducing the MCA to the MWRA as explained in the introduction. The authors generalize connectivity constraints and flow formulations from the SAP to formulate mathematical models for the MWRA and introduce Lagrangian relaxations. They further propose two heuristics. The first finds the best arborescence rooted at some vertex v spanning the vertices reachable from v. The second is a local search heuristic, which repeatedly adds to the current tree a shortest path from the root to some leaf, prunes multiple incoming arcs to again obtain a tree, and prunes leaves connected by non-negative arcs.

Blum and Calvo (2015) propose a matheuristic to solve the MWRA on general, rooted graphs. The main idea is to heuristically sample spanning arborescences, and solve a mathematical model for the MWRA on the reduced graph defined by the union of their arcs. The sampling is done by a randomized greedy constructive algorithm similar to the one proposed by Mateo et al. (2012). When taking the union of the arcs, directed circuits are excluded, in order to use a mathematical model for the directed MWRA. This process is iterated and the best solution over all iterations is returned. Arcs sampled in an iteration are kept in subsequent iterations unless they have not contributed to some solution of the reduced problem for a given number of iterations.

The method of Blum and Calvo (2015) is currently the best performing heuristic method for the MWRA. The idea of sampling and solving a mathematical model has been generalized to a meta-heuristic called Construct, Merge, Solve & Adapt (CMSA) by Blum, Pinacho, López-Ibáñez, and Lorenzon (2016). The latter article also introduces the MCA and applies CMSA to it, with a method similar to the one proposed by Blum and Calvo (2015) for the MWRA. The main difference is that the mathematical model ensures that all required vertices are included in a solution.

As mentioned in the introduction, the MWRA generalizes the Steiner arborescence problem to negative weights. For the SAP there is a broad literature both as a problem itself (Charikar, Chekuri, Cheung, Dai, Goel, Guha, Li, 1999, Fischetti, 1991, Gamrath, Koch, Maher, Rehfeldt, Shinano, 2017, Johnston, Kelley, Crawford, Morton, Agarwala, Koch, Schäffer, Francomano, Biesecker, 2000, Watel, Weisser, 2016) or as a suitable model to solve other Steiner tree problems (Ljubić, Weiskircher, Pferschy, Klau, Mutzel, Fischetti, 2006, Wong, 1984). Note that most of the proposed algorithms for the SAP cannot be straightforwardly applied to the MWRA as they assume arcs with non-negative weights. However, Leitner, Ljubić, Luipersbeck, and Sinnl (2018) show that it is possible to reduce instances with negative weights into instances of the asymmetric prize-collecting Steiner tree problem (APCSTP) with non-negative weights, by converting negative arc weights into vertex prizes. We will compare to such approaches in Section 6.

In this paper we propose a heuristic and an exact algorithm for the MWRA and the MCA problems. In Section 2 we propose some rules to reduce the problem. Section 3 presents a mathematical model and exact approaches to the problem. In Section 4 we show how Edmonds algorithm can be modified to consider a set of vertices that are required in the resulting arborescence and embed this procedure into an iterated local search algorithm, and in Section 5 we give a detailed account of the overall structure of the combined approach as well as some implementation details. Computational results on existing and new instances are presented in Section 6, and we conclude in Section 7.

Section snippets

Problem reductions

To simplify problem instances, we apply some reduction rules before solving them. Additional problem reductions based on lower and upper bounds are described in the next section.

This section focuses on reduction rules that apply to instances with negative weights, and thus are applicable to the MWRA and the MCA. To the best of our knowledge, no reduction rules for instances with negative weights are available in the literature. For non-negative weights, i.e. reduction rules for the related

An integer programming formulation

The first formulation for the MWRA for general graphs that we are aware of is due to Duhamel et al. (2008). It uses a flow-based model to ensure that a unique path between the root and every connected vertex is selected. While the formulation has a polynomial number of variables and constraints, it failed to solve large-size instances in our experiments. Consequently, an alternative formulation is proposed hereafter.

The proposed formulation for the MCA is derived from the classical cut

An algorithm for constructing r-aborescences spanning a subset of vertices

In this section we describe a modification of the algorithm of Edmonds (1967) for finding minimum-weight spanning r-arborescences. We first briefly explain Edmonds algorithm, then describe the modifications made to span subsets R of required vertices. The modified algorithm will be heuristic and not necessarily returns the minimum-weight arborescence containing vertices R.

The modified algorithm is shown in Algorithm 2.Our implementation and presentation of the algorithm follows Fischetti and

Structure of the proposed method and implementation details

The performance of the proposed rules and algorithms depend on the availability of lower and upper bounds. Consequently, the order in which the different algorithmic components are applied influences the overall performance of the method, both in terms of solution quality and computing requirements. We proceed to describe the implementation.

The basic motivation behind the proposed order is to delay the time-consuming procedures. For instance, the problem reduction rules are fast and provide

Computational results

In this section we present the results of computational experiments on existing and new instances for the MWRA and the MCA. We first evaluate the effectiveness of the instance reduction rules. In further experiments we evaluate the ILS heuristic and the exact algorithm on the MWRA and the MCA.

Conclusions

In this work we have proposed different solution approaches for the minimum covering arborescence (MCA) problem and the related minimum weighted rooted arborescence (MWRA) problem. These problems aim at finding a least cost arborescence considering the existence of both positive and negative weight arcs. The major contributions of this work are three-fold: (1) we put forward several relaxations and reduction procedures to reduce the size of the instances, (2) we provide an iterated local search

Acknowledgments

Our research has been supported by CNPq (grant 420348/2016-6), Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001, by Google Research Latin America (grant 25111) and by the Chilean Council of Scientific and Technological Research (CONICYT) through Fondecyt (grant 1180670).

References (35)

  • Y. Chu et al.

    On the shortest arborescence of a directed graph

    Scientia Sinica

    (1965)
  • E.A. Dinic

    Algorithm for solution of a problem of maximum flow in a network with power estimation

    Soviet Doklady Mathematics

    (1970)
  • C. Duhamel et al.

    Models and heuristics for a minimum arborescence problem

    Network

    (2008)
  • J. Edmonds

    Optimum branchings

    Journal of Research of the National Bureau of Standards, Section B

    (1967)
  • M. Fischetti

    Facets of two steiner arborescence polyhedra

    Mathematical Programming

    (1991)
  • M. Fischetti et al.

    An efficient algorithm for the min-sum arborescence problem on complete digraphs

    ORSA Journal Computer

    (1993)
  • Z.-H. Fu et al.

    Swap-vertex based neighborhood for steiner tree problems

    Mathematical Programming Computation

    (2017)
  • Cited by (0)

    View full text