@misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9212}, number = {06-27}, abstract = {We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is \$4K/2+K\$-competitive, where \$K\$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9599}, number = {07-16}, abstract = {In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{Harks, author = {Harks, Tobias}, title = {Nash Equilibria in Online Sequential Routing Games}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9376}, number = {06-43}, abstract = {In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game \$i\$, future games \$i+1,\dots,n\$ are not known, and, once players of game \$i\$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm \$\sl {SeqNash}\$ consisting of the sequence of Nash equilibria is \$\frac{4n}{2+n}\$-competitive for affine linear latency functions. For \$n=1\$, this result contains the bound on the price of anarchy of \$\frac{4}{3}\$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of \$\frac{4n}{2+n}\$ on the competitive ratio of \$\sl {SeqNash}\$. We further prove a lower bound of \$\frac{3n-2}{n}\$ of \$\sl {SeqNash}\$ showing that for \$n=2\$ our upper bound is tight.}, language = {en} } @misc{Wolf, author = {Wolf, Thomas}, title = {A Study of Genetic Algorithms solving a combinatorial Puzzle}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3445}, number = {SC-98-01}, abstract = {The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings.}, language = {en} } @misc{BertholdHeinzPfetschetal., author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc and Vigerske, Stefan}, title = {Large Neighborhood Search beyond MIP}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12989}, number = {11-21}, abstract = {Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.}, language = {en} } @misc{Sagnol, author = {Sagnol, Guillaume}, title = {Approximation of a Maximum-Submodular-Coverage problem involving spectral functions, with application to Experimental Design}, volume = {151}, number = {1--2}, issn = {1438-0064}, doi = {10.1016/j.dam.2012.07.016}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14956}, pages = {258 -- 276}, abstract = {We study a family of combinatorial optimization problems defined by a parameter \$p\in[0,1]\$, which involves spectral functions applied to positive semidefinite matrices, and has some application in the theory of optimal experimental design. This family of problems tends to a generalization of the classical maximum coverage problem as \$p\$ goes to \$0\$, and to a trivial instance of the knapsack problem as \$p\$ goes to \$1\$. In this article, we establish a matrix inequality which shows that the objective function is submodular for all \$p\in[0,1]\$, from which it follows that the greedy approach, which has often been used for this problem, always gives a design within \$1-1/e\$ of the optimum. We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors. We prove an inequality which generalizes a classical result from the theory of optimal designs, and allows us to give a rounding procedure with an approximation factor which tends to \$1\$ as \$p\$ goes to \$1\$.}, language = {en} } @misc{BorndoerferOmontSagnoletal., author = {Bornd{\"o}rfer, Ralf and Omont, Bertrand and Sagnol, Guillaume and Swarat, Elmar}, title = {A Stackelberg game to optimize the distribution of controls in transportation networks}, issn = {1438-0064}, doi = {10.1007/978-3-642-35582-0_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14995}, abstract = {We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of \$N\$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways.}, language = {en} } @misc{HillerKlugTuchscherer, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups}, issn = {1438-0064}, doi = {10.1007/s10696-013-9175-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16485}, abstract = {The task of an elevator control is to schedule the elevators of a group such that small waiting and travel times for the passengers are obtained. We present an exact reoptimization algorithm for this problem. A reoptimization algorithm computes a new schedule for the elevator group each time a new passenger arrives. Our algorithm uses column generation techniques and is, to the best of our knowledge, the first exact reoptimization algorithms for a group of passenger elevators. To solve the column generation problem, we propose a Branch \& Bound method.}, language = {en} } @misc{HillerVredeveld, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Stochastic dominance analysis of Online Bin Coloring algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16502}, abstract = {This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.}, language = {en} } @misc{WessaelyWernerEckeletal., author = {Wess{\"a}ly, Roland and Werner, Axel and Eckel, Klaus and Seibel, Julia and Orlowski, Sebastian and Louchet, Hadrien and Patzak, Erwin and Bentz, Winfried}, title = {Sch{\"a}tze heben bei der Planung von FTTx-Netzen: optimierte Nutzung von existierenden Leerrohren - eine Praxisstudie}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14861}, abstract = {Das vom BMBF gef{\"o}rderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu k{\"o}nnen. Wir zeigen anhand einer Praxisstudie in Zusammenarbeit mit der Regensburger R-KOM, wie ein Planer von diesen Verfahren profitieren kann, um die Auswirkungen bestimmter Entscheidungen auf die Netzstruktur und -kosten zu untersuchen. Wir illustrieren dies am Beispiel eines FTTB/FTTH-Vergleichs, der Variation von Kundenanbindungsraten und der gezielten Ausnutzung existierender Leerrohre, um Tiefbau zu vermeiden.}, language = {de} }