A node-based layered graph approach for the Steiner tree problem with revenues,budget and hop-constraints

The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large-scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the underlying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints

The incomplete hub location problem with and without hop-constraints is modeled using a Leontief substitution system approach. The Leontief formalism provides a set of important theoretical properties and delivers formulations with tight linear bounds that can explicitly incorporate hop constraints for each origin-destination pair of demands. Furthermore, the proposed formulations are amenable to a Benders decomposition technique which can solve large scale test instances. The performance of the devised algorithm is primarily due to a new general scheme for separating Benders feasibility cuts. The novel cuts render a stabilizing effect that is directly responsible for the solution of instances up to 80 nodes.     

IP modeling of the survivable hop constrained connected facility location problem

We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least λ edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for finding its solution. Finally, we report computational results.     

Some topological properties of star graphs: The surface area and volume

The star graph, as an interesting network topology, has been extensively studied in the past. In this paper, we address some of the combinatorial properties of the star graph. In particular, we consider the problem of calculating the surface area and volume of the star graph, and thus answering an open problem previously posed in the literature. The surface area of a sphere with radius i in a graph is the number of nodes in the graph whose distance from a given node is exactly i. The volume of a sphere with radius i in a graph is the number of nodes within distance i from the given node. In this paper, we derive explicit expressions to calculate the surface area and volume in the star graph.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Given an undirected network with positive edge costs and a natural number p, the Hop-Constrained Minimum Spanning Tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991).     

Minimal spanning trees with a constraint on the number of leaves

In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a “degree-1” terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in “degree-1” terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of “degree-1” terminals. We present two different formulations for this problem and some lower bounding schemes derived from them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer Linear Programming formulations for related problems are also discussed at the end.     

The Hirsch Conjecture for the fractional stable set polytope

The edge formulation of the stable set problem is defined by two-variable constraints, one for each edge of a graph \(G\) , expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. These results lead us to prove that the combinatorial diameter of the fractional stable set polytope is at most the number of nodes of the given graph. As a corollary, the Hirsch bound holds for this class of polytopes.     

Allocation strategies in hub networks

In this paper, we study allocation strategies and their effects on total routing costs in hub networks. Given a set of nodes with pairwise traffic demands, the p-hub median problem is the problem of choosing p nodes as hub locations and routing traffic through these hubs at minimum cost. This problem has two versions; in single allocation problems, each node can send and receive traffic through a single hub, whereas in multiple allocation problems, there is no such restriction and a node may send and receive its traffic through all p hubs. This results in high fixed costs and complicated networks. In this study, we introduce the r-allocation p-hub median problem, where each node can be connected to at most r hubs. This new problem generalizes the two versions of the p-hub median problem. We derive mixed-integer programming formulations for this problem and perform a computational study using well-known datasets. For these datasets, we conclude that single allocation solutions are considerably more expensive than multiple allocation solutions, but significant savings can be achieved by allowing nodes to be allocated to two or three hubs rather than one. We also present models for variations of this problem with service quality considerations, flow thresholds, and non-stop service.     

Computing a graph's period quadratically by node condensation

A condensation algorithm for finding the period and cyclic classes of an n node strongly connected graph (or equivalently, the period of an n state irreducible Marcov chain) is given for which an upper bound on the number of operations is proportional to n². This substantially improves upon the upper bounds of the two existing algorithms known to us, both of which are proportional to n⁴. The idea of our method is this. The set of nodes accessible in one step from some node 1, say, belong to a common cyclic class and so can be “condensed” into a single node. Similarly, the set of nodes accessible in one step from that condensed node belong to a common cyclic class and so can be condensed into a single node. After at most 2n?2 repetitions of this procedure, the resulting graph is a circuit whose length is the period of the original graph and each of whose nodes is a condensation of a cyclic class in the original graph.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added). This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational results using the extended formulations are performed.     

Mathematical programming approach to the Petri nets reachability problem

This paper focuses on the resolution of the reachability problem in Petri nets, using the mathematical programming paradigm. The proposed approach is based on an implicit traversal of the Petri net reachability graph. This is done by constructing a unique sequence of Steps that represents exactly the total behaviour of the net. We propose several formulations based on integer and/or binary linear programming, and the corresponding sets of adjustments to the particular class of problem considered. Our models are validated on a set of benchmarks and compared with standard approaches from IA and Petri nets community.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (γ_q) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

On the complexity of recognizing directed path families

A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G such that each word in the language is the set of arcs of some path in G, is a polynomial-time solvable problem.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Some formulations for the group steiner tree problem

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V(G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.     

Multicommodity flow models for spanning trees with hop constraints

In this paper we compare the linear programming relaxations of undirected and directed multicommodity flow formulations for the terminal layout problem with hop constraints. Hop constraints limit the number of hops (links) between the computer center and any terminal in the network. These constraints model delay constraints since a smaller number of hops decreases the maximum delay transmission time in the network. They also model reliability constraints because with a smaller number of hops there is a lower route loss probability. Hop constraints are easily modelled with the variables involved in multicommodity flow formulations. We give some empirical evidence showing that the linear programming relaxation of such formulations give sharp lower bounds for this hop constrained network design problem. On the other hand, these formulations lead to very large linear programming models. Therefore, for bounding purposes we also derive several lagrangean based procedures from a directed multicommodity flow formulation and present some computational results taken from a set of instances with up to 40 nodes.