## 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**

**Abstract:**

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 *P*_{1} and *P*_{2}, the following relation holds *c(P*_{1} \cup P_{2}) ≥ c(P_{1}) + c(P_{2}). 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**

**Abstract:**

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

**Abstract:**

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.