@misc{KroellerWessaely2003, author = {Kr{\"o}ller, Alexander and Wess{\"a}ly, Roland}, title = {Integrated Optimization of Hardware Configuration and Capacity. Dimensioning in SDH and opaque WDM networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7714}, number = {03-49}, year = {2003}, abstract = {We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved.}, language = {en} } @misc{FroylandKochMegowetal.2006, author = {Froyland, Gary and Koch, Thorsten and Megow, Nicole and Duane, Emily and Wren, Howard}, title = {Optimizing the Landside Operation of a Container Terminal}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9004}, number = {06-06}, year = {2006}, abstract = {This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas. A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most~8\\% above a lower bound on optimal RMG utilization.}, language = {en} } @misc{Koch2005, author = {Koch, Thorsten}, title = {Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8845}, number = {05-51}, year = {2005}, abstract = {Using the popular puzzle game of Sudoku, this article highlights some of the ideas and topics covered in ZR-04-58.}, language = {en} } @misc{AchterbergGroetschelKoch2006, author = {Achterberg, Tobias and Gr{\"o}tschel, Martin and Koch, Thorsten}, title = {Software for Teaching Modeling of Integer Programming Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9176}, number = {06-23}, year = {2006}, abstract = {Modern applications of mathematical programming must take into account a multitude of technical details, business demands, and legal requirements. Teaching the mathematical modeling of such issues and their interrelations requires real-world examples that are well beyond the toy sizes that can be tackled with the student editions of most commercial software packages. We present a new tool, which is freely available for academic use including complete source code. It consists of an algebraic modeling language and a linear mixed integer programming solver. The performance and features of the tool are in the range of current state-of-the-art commercial tools, though not in all aspects as good as the best ones. Our tool does allow the execution and analysis of large real-world instances in the classroom and can therefore enhance the teaching of problem solving issues. Teaching experience has been gathered and practical usability was tested in classes at several universities and a two week intensive block course at TU Berlin. The feedback from students and teachers has been very positive.}, language = {en} } @misc{MartinWeismantel1998, author = {Martin, Alexander and Weismantel, Robert}, title = {Conjunctive Cuts for Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3618}, number = {SC-98-18}, year = {1998}, abstract = {This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view.}, language = {en} } @misc{GeerdesKarl2003, author = {Geerdes, Hans-Florian and Karl, Holger}, title = {The Potential of Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7641}, number = {03-42}, year = {2003}, abstract = {Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\\% on average for concrete example networks are achievable.}, language = {en} } @misc{Geerdes2003, author = {Geerdes, Hans-Florian}, title = {Assessing Capacity Improvements by Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7651}, number = {03-43}, year = {2003}, abstract = {Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\\% on the average.}, language = {en} } @misc{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, year = {1998}, abstract = {Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.}, language = {en} } @misc{Koster2000, author = {Koster, Arie M.C.A.}, title = {Re-Optimization of Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5863}, number = {00-18}, year = {2000}, abstract = {In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.}, language = {en} } @misc{Koch2001, author = {Koch, Thorsten}, title = {ZIMPL User Guide}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6466}, number = {01-20}, year = {2001}, abstract = {{\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.}, language = {en} } @misc{BorndoerferScheltenSchlechteetal.2005, author = {Bornd{\"o}rfer, Ralf and Schelten, Uwe and Schlechte, Thomas and Weider, Steffen}, title = {A Column Generation Approach to Airline Crew Scheduling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8713}, number = {05-37}, year = {2005}, abstract = {The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.}, language = {en} }