@article{BlancoBorndoerferBrueckneretal., author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Br{\"u}ckner, Michael and Hoang, Nam-Dung and Schlechte, Thomas}, title = {On the Path Avoiding Forbidden Pairs Polytope}, series = {Electronic Notes in Discrete Mathematics}, volume = {50}, journal = {Electronic Notes in Discrete Mathematics}, doi = {10.1016/j.endm.2015.07.057}, pages = {343 -- 348}, abstract = {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.}, language = {en} } @inproceedings{BlancoBorndoerferHoangetal., author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Maristany de las Casas, Pedro and Schlechte, Thomas and Schlobach, Swen}, title = {Cost Projection Methods for the Shortest Path Problem with Crossing Costs}, series = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, volume = {59}, booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan}, abstract = {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 {\`a} posteriori error bounds.}, language = {en} } @inproceedings{BlancoBorndoerferHoangetal., author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Schienle, Adam and Schlechte, Thomas and Schlobach, Swen}, title = {Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind}, series = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, volume = {54}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, editor = {Marc, Goerigk}, doi = {10.4230/OASIcs.ATMOS.2016.12}, pages = {15}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferHoang2011, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Determining Fair Ticket Prices in Public Transport by Solving a Cost Allocation Problem}, series = {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}, booktitle = {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}, publisher = {Springer}, doi = {10.1007/978-3-642-25707-0_5}, year = {2011}, language = {en} } @article{BorndoerferHoang2014, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Fair ticket pricing in public transport as a constrained cost allocation game}, series = {Annals of Operations Research}, volume = {226}, journal = {Annals of Operations Research}, doi = {10.1007/s10479-014-1698-z}, pages = {51 -- 68}, year = {2014}, abstract = {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{\"o}rfer and Hoang 2012). This journal article introduces better model and algorithms.}, language = {en} } @incollection{BorndoerferHoangKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Karbstein, Marika and Koch, Thorsten and Martin, Alexander}, title = {How many Steiner terminals can you connect in 20 years?}, series = {Facets of Combinatorial Optimization; Festschrift for Martin Gr{\"o}tschel}, booktitle = {Facets of Combinatorial Optimization; Festschrift for Martin Gr{\"o}tschel}, editor = {J{\"u}nger, Michael and Reinelt, Gerhard}, publisher = {Springer}, doi = {10.1007/978-3-642-38189-8_10}, pages = {215 -- 244}, language = {en} } @incollection{GroetschelKochHoang2010, author = {Gr{\"o}tschel, Martin and Koch, Thorsten and Hoang, Nam-Dung}, title = {Lagenwechsel minimieren - oder das Bohren von L{\"o}chern in Leiterplatten}, series = {Besser als Mathe}, booktitle = {Besser als Mathe}, editor = {Biermann, Katja and Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, publisher = {Vieweg+Teubner}, doi = {10.1007/978-3-658-01004-1_19}, pages = {161 -- 174}, year = {2010}, language = {en} } @incollection{HeuvelineHoang2007, author = {Heuveline, Vincent and Hoang, Nam-Dung}, title = {On two numerical approaches for the boundary control stabilization of semi-linear parabolic systems: a comparison}, series = {Control of Coupled Partial Differential Equations, International Series of Numerical Mathematics, Vol. 155}, booktitle = {Control of Coupled Partial Differential Equations, International Series of Numerical Mathematics, Vol. 155}, editor = {Kunisch, Karl and Leugering, G{\"u}nter and Sprekels, J{\"u}rgen and Tr{\"o}ltzsch, Fredi}, publisher = {Birkh{\"a}user}, doi = {10.1007/978-3-7643-7721-2_5}, pages = {95 -- 118}, year = {2007}, language = {en} } @phdthesis{Hoang, author = {Hoang, Nam-Dung}, title = {Algorithmic Cost Allocation Games: Theory and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-28185}, language = {en} } @article{HoangKoch, author = {Hoang, Nam-Dung and Koch, Thorsten}, title = {Steiner tree packing revisited}, series = {Mathematical Methods of Operations Research}, volume = {76}, journal = {Mathematical Methods of Operations Research}, number = {1}, doi = {10.1007/s00186-012-0391-8}, pages = {95 -- 123}, abstract = {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.}, language = {en} }