TY - CHAP A1 - Heuveline, Vincent A1 - Hoang, Nam-Dung ED - Kunisch, Karl ED - Leugering, Günter ED - Sprekels, Jürgen ED - Tröltzsch, Fredi T1 - On two numerical approaches for the boundary control stabilization of semi-linear parabolic systems: a comparison T2 - Control of Coupled Partial Differential Equations, International Series of Numerical Mathematics, Vol. 155 Y1 - 2007 U6 - https://doi.org/10.1007/978-3-7643-7721-2_5 SP - 95 EP - 118 PB - Birkhäuser ER - TY - THES A1 - Hoang, Nam-Dung T1 - Algorithmic Cost Allocation Games: Theory and Applications Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-28185 ER - TY - CHAP A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Hoang, Nam-Dung ED - Biermann, Katja ED - Grötschel, Martin ED - Lutz-Westphal, Brigitte T1 - Lagenwechsel minimieren – oder das Bohren von Löchern in Leiterplatten T2 - Besser als Mathe Y1 - 2010 U6 - https://doi.org/10.1007/978-3-658-01004-1_19 SP - 161 EP - 174 PB - Vieweg+Teubner ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung T1 - Determining Fair Ticket Prices in Public Transport by Solving a Cost Allocation Problem T2 - Appeared in: Modeling, Simulation and Optimization of Complex Processes, Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam Y1 - 2011 U6 - https://doi.org/10.1007/978-3-642-25707-0_5 PB - Springer ER - 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 - CHAP A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Karbstein, Marika A1 - Koch, Thorsten A1 - Martin, Alexander ED - Jünger, Michael ED - Reinelt, Gerhard T1 - How many Steiner terminals can you connect in 20 years? T2 - Facets of Combinatorial Optimization; Festschrift for Martin Grötschel Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38189-8_10 SP - 215 EP - 244 PB - Springer 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 - TY - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Schienle, Adam A1 - Schlechte, Thomas A1 - Schlobach, Swen ED - Marc, Goerigk T1 - Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind T2 - 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) N2 - We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs. Y1 - 2016 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2016.12 VL - 54 ER - TY - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Maristany de las Casas, Pedro A1 - Schlechte, Thomas A1 - Schlobach, Swen ED - D'Angelo, Gianlorenzo ED - Dollevoet, Twan T1 - Cost Projection Methods for the Shortest Path Problem with Crossing Costs T2 - 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) N2 - Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds. Y1 - 2017 VL - 59 ER -