TY - JOUR A1 - Hoang, Nam-Dung A1 - Koch, Thorsten T1 - Steiner tree packing revisited JF - Mathematical Methods of Operations Research N2 - The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some “classical” STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality. Y1 - 2012 U6 - https://doi.org/10.1007/s00186-012-0391-8 VL - 76 IS - 1 SP - 95 EP - 123 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung T1 - Fair ticket pricing in public transport as a constrained cost allocation game JF - Annals of Operations Research N2 - Ticket pricing in public transport usually takes a welfare maximization point of view. Such an approach, however, does not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and linear and integer programming. The ticket pricing problem is considered to be a constrained cost allocation game, which is a generalization of cost allocation games that allows to deal with constraints on output prices and on the formation of coalitions. An application to pricing railway tickets for the intercity network of the Netherlands is presented. The results demonstrate that the fairness of prices can be improved substantially in this way. A preliminary version of this paper appeared in the Proceedings of HPSC 2009 (Borndörfer and Hoang 2012). This journal article introduces better model and algorithms. Y1 - 2014 U6 - https://doi.org/10.1007/s10479-014-1698-z VL - 226 SP - 51 EP - 68 ER - TY - JOUR A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Brückner, Michael A1 - Hoang, Nam-Dung A1 - Schlechte, Thomas T1 - On the Path Avoiding Forbidden Pairs Polytope JF - Electronic Notes in Discrete Mathematics N2 - Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair. Y1 - 2015 U6 - https://doi.org/10.1016/j.endm.2015.07.057 VL - 50 SP - 343 EP - 348 ER -