Contributed Session Tue.1.H 3004

Tuesday, 10:30 - 12:00 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Generalizing shortest paths, cycles, and Steiner trees


Chair: Stefano Gualandi



Tuesday, 10:30 - 10:55 h, Room: H 3004, Talk 1

Stefano Gualandi
Resource constrained shortest paths with a super additive objective function

Coauthor: Federico Malucelli


We present an exact solution approach to the constrained shortest path problem with a super additive objective function. This problem generalizes the constrained shortest path problem by considering a cost function c(·) such that, given two consecutive paths P1 and P2, the following relation holds c(P1 \cup P2) ≥ c(P1) + c(P2). Since super additivity invalidates the Bellman optimality conditions, known resource constrained shortest path algorithms must be revisited. Our exact solution algorithm is based on a two stage approach: first, the size of the input graph is reduced as much as possible using a Lagrangian reduced-cost fixing algorithm. Then, since the Lagrangian relaxation provides a tight lower bound, the optimal solution is computed using a near-shortest path enumerative algorithm that exploits such lower bound. We present two alternative algorithms to solve the Lagrangian relaxation, and compare their behaviors in terms of reduction of the input graph, quality of the lower bounds, and computation time. Computational results show that the constrained shortest path with a super additive objective function is indeed a challenging problem.



Tuesday, 11:00 - 11:25 h, Room: H 3004, Talk 2

Hiroshige Dan
Finding the shortest cycle in directed graphs under some constraints on passing vertices and paths

Coauthor: Tatsuya Shigetou


In this research, we propose a problem to find the shortest cycle in directed graphs under some constraints on passing vertices and paths.
The proposed problem is as follows: The origin and designated vertices are given. We want to find the shortest cycle which starts from the origin and passes all the designated vertices. Also, the cycle has a state which depends on the path from the origin and the transition along the cycle changes it. Each vertex has acceptable states, and the path can reach a vertex when the current state is acceptable for it.
This kind of problem occurs from the maintenance of large machinery. For example, when an elevator is under maintenance, a worker has to do the predetermined operations. Also, he/she has to do some operations for ensuring his/her safety during the maintenance. However, he/she can skip some operations as long as the safety is ensured. Moreover, a state of an elevator is transiting by operations. We can deal with such situations by our proposed problem.
For this problem, we propose a method which is based on a method for the asymmetric traveling salesman problem. We will show computational results in our presentation.



Tuesday, 11:30 - 11:55 h, Room: H 3004, Talk 3

Marika Karbstein
Approximation and min-max results for the Steiner connectivity problem


The Steiner connectivity problem is to connect a set of terminal nodes in a graph by a cost minimal set of paths; it generalizes the Steiner tree problem to hypergraphs.
The problem is known to be approximable within a factor of log k if all nodes are terminals. We discuss its approximability if all paths contain at most k edges and provide, in particular, a k+1 approximation if
all paths contain at most k terminals.
The two terminal case gives rise to a TDI description; this yields a combinatorial companion theorem to Menger's theorem for hypergraphs and characterizes paths and cuts in hypergraphs as a blocking pair.


  signature loans . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.